LeetCode刷题91-110

LeetCode刷题
Word count: 7.4k   |   Reading time≈ 33 min

①682.棒球比赛

2024.2.7 周三
题目：
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
整数 x - 表示本回合新获得分数 x
“+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
输入：ops = [“5”,”2”,”C”,”D”,”+”]
输出：30
解释：
“5” - 记录加 5 ，记录现在是 [5]
“2” - 记录加 2 ，记录现在是 [5, 2]
“C” - 使前一次得分的记录无效并将其移除，记录现在是 [5].
“D” - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
“+” - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30

83.16%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int calPoints(String[] operations) {
        int res = 0;
        List<Integer> list = new ArrayList<>();

        for(String op:operations){
            int n = list.size();
            switch(op){
                case "+":
                res += list.get(n-1) + list.get(n-2);
                list.add(list.get(n-1) + list.get(n-2));
                break;

                case "D":
                res += list.get(n-1)*2;
                list.add(list.get(n-1)*2);
                break;

                case "C":
                res -= list.get(n-1);
                list.remove(n-1);
                break;

                default:
                res += Integer.parseInt(op);
                list.add(Integer.parseInt(op));
                break;
            }
        }
        return res;
    }

②697.数组的度

2024.2.8 周四
题目：
给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

思路：
需要知道原数组每个数组出现的次数 ——> 得到原数组的度
需要得知每一个数字最开始出现的位置and最后出现的位置 ——> 得到度相同的最短字数组的长度
Map< Integer,int[]> ——> 值是一个数组

HashMap 68.97%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int findShortestSubArray(int[] nums) {
        Map<Integer,int[]> map = new HashMap<>();
        int n = nums.length;
        //得到需要的原始数据
        for(int i = 0; i < n; i++){
            if(map.containsKey(nums[i])){
                //已包含该数字
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            }else{
                //还不包含该数字
                map.put(nums[i],new int[]{1,i,i});
            }
        }

        int maxDu = 0;
        int minLen = 0;
        for(Map.Entry<Integer,int[]> entry : map.entrySet()){
            int[] value = entry.getValue();
            if(value[0] > maxDu){
                maxDu = value[0];
                minLen = value[2] - value[1] + 1;
            }else if(value[0] == maxDu){
                minLen = Math.min(minLen,value[2] - value[1] + 1);
            }
        }
        return minLen;
    }

③704.二分查找

2024.2.9 周五
题目：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int search(int[] nums, int target) {
        //二分查找法
        int n = nums.length;
        int left = 0;
        int right = n-1;
        while(left <= right){
            int mid = (left + right)/2;
            if(target == nums[mid]){
                return mid;
            }else if(target < nums[mid]){
                right = mid - 1;
            }else if(target > nums[mid]){
                left = mid + 1;
            }
        }
        return -1;
    }

④705.设计哈希集合

2024.2.10 周六
题目：
不使用任何内建的哈希表库设计一个哈希集合（HashSet）
实现 MyHashSet 类：
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
输入：
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]
解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

思路1：
直接使用一个 boolean 数组记录某个 key 是否存在，key 直接对应 boolean 的下标。
通常在设计哈希集合时，会选择一个较大的素数作为数组的长度，这样可以减少哈希冲突的概率，提高哈希集合的效率。
选择一个素数作为数组长度也可以更好地分布数据，减少碰撞的发生。因此，选择1000009可能是为了在一定程度上提高哈希集合的性能。

简单数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MyHashSet {
    boolean[] nodes = new boolean[1000009];

    public MyHashSet() {

    }
    
    public void add(int key) {
        nodes[key] = true;
    }
    
    public void remove(int key) {
        nodes[key] = false;
    }
    
    public boolean contains(int key) {
        return nodes[key];
    }
}

思路2：
链地址法处理冲突
开辟大小为base的数组，数组的每个位置是一个链表

链地址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class MyHashSet {
    private static final int BASE = 769; //数组的大小
    private LinkedList<Integer>[] base; //声明

    public MyHashSet() {
        base = new LinkedList[BASE];//初始化
        //该数组的每个位置都是一个链表集合
        for(int i = 0; i < BASE; i++){
            base[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        int h = hash(key);
        //HashSet要确保元素唯一
        //迭代器遍历集合
        Iterator<Integer> iterator = base[h].iterator();
        while(iterator.hasNext()){
            Integer element = iterator.next();
            if(element == key) return;
        }
        base[h].offerLast(key);//无重复则将该元素插入到列表末尾
    }
    
    public void remove(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = base[h].iterator();
        while(iterator.hasNext()){
            Integer element = iterator.next();
            if(element == key){
                base[h].remove(element);
                return;
            }
        }
    }
    
    public boolean contains(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = base[h].iterator();
        while(iterator.hasNext()){
            Integer element = iterator.next();
            if(element == key){
                return true;
            }
        }
        return false;
    }

    //哈希函数，确定该元素存储的位置
    public static int hash(int key){
        return key % BASE;
    }
}

⑤706.设计哈希映射

2024.2.11 周日
题目：
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value)。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class MyHashMap {
    private class Pair {
        private int key;
        private int value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }

    private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashMap() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i) {
            data[i] = new LinkedList<Pair>();
        }
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.getKey() == key) {
                pair.setValue(value);
                return;
            }
        }
        data[h].offerLast(new Pair(key, value));
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.getKey() == key) {
                return pair.value;
            }
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.key == key) {
                data[h].remove(pair);
                return;
            }
        }
    }

    private static int hash(int key) {
        return key % BASE;
    }
}

⑥717.1比特与2比特字符

2024.2.12 周一
题目：
有两种特殊字符：
第一种字符可以用一比特 0 表示；
第二种字符可以用两比特（10 或 11）表示。
给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。
输入: bits = [1, 0, 0]
输出: true
解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。
所以最后一个字符是一比特字符。

思路：
第一种字符一定以0开头，第二种字符一定以1开头，我们从左往右遍历数组，如果遇到了0则跳到下一个位置bites[i+1] (当前遇到的是第一种字符)，如果遇到了1则跳到下下个位置bites[i+2] (当前遇到的是第二种字符)。直到如果可以遍历到n-1则表示最后一个字符一定是第一种字符。

正序遍历

1
2
3
4
5
6
7
8
public boolean isOneBitCharacter(int[] bits) {
        int n = bits.length;
        int i = 0;
        while(i < n-1){
            i += bits[i]+1; //当前是0则跳1，当前是1则跳2
        }
        return i == n-1;
    }

⑦724.寻找数组的中心下标

2024.2.13 周二
题目：
给你一个整数数组 nums，请计算数组的中心下标。
数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。

思路：
sum = leftSum * 2 + i 则 i 满足条件

前缀和

1
2
3
4
5
6
7
8
9
10
11
public int pivotIndex(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int leftSum = 0;
        for(int i = 0; i < nums.length; i++){
            if(sum == 2 * leftSum + nums[i]){
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }

⑧733.图像渲染

2024.2.14 周三
题目：
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr，sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。
为了完成上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像。

二维数组

当目标颜色和初始颜色相同时，我们无需对原数组进行修改。

思路1：
进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。

深度优先搜索 100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    //深度优先搜索

    //得到起始格子上下左右的数
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        //起始位置可能会被更改，需要记录开始值
        int startColor = image[sr][sc];
        if(startColor != color){
            dfs(image,sr,sc,startColor,color);
        }
    
        return image;
    }

    public void dfs(int[][] image, int x, int y, int startColor,int color){
        if(image[x][y] == startColor){
            //染色
            image[x][y] = color;
            //遍历周围的四个格子
            for(int k = 0; k < 4; k++){
                int mx = x + dx[k];
                int my = y + dy[k];
                //如果还在规定范围之内就继续递归
                if(mx >= 0 && mx < image.length && my >= 0 && my < image[0].length){
                    dfs(image,mx,my,startColor,color);
                }
            }
        }
    }
}

思路2：
我们从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。

广度优先 58.33%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    //得到起始格子上下左右的数
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int startColor = image[sr][sc];
        if(startColor == color){
            return image;
        }

        int m = image.length;
        int n = image[0].length;

        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{sr,sc});
        
        while(!queue.isEmpty()){
            int[] inter = queue.poll();
            int x = inter[0];
            int y = inter[1];
            image[x][y] = color;//染色
            //得到四周
            for(int k = 0; k < 4; k++){
                int mx = x + dx[k];
                int my = y + dy[k];
                //满足条件则offer且染色
                if(mx >= 0 && mx < m && my >= 0 && my < n && image[mx][my] == startColor){
                    queue.offer(new int[]{mx,my});
            }
        }
        return image;
    }
}

⑨744.寻找比目标字母大的最小字母

2024.2.15 周四
题目：
给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。
letters 里至少有两个不同的字符。
返回 letters 中大于 target 的最小的字符。
如果不存在这样的字符，则返回 letters 的第一个字符。

线性查找

1
2
3
4
5
6
7
8
9
public char nextGreatestLetter(char[] letters, char target) {
        int m = letters.length;
        for(int i = 0; i < m; i++){
            if(letters[i] > target){
                return letters[i];
            }
        }
        return letters[0];
    }

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public char nextGreatestLetter(char[] letters, char target) {
        int m = letters.length;
        if(target >= letters[m-1]){
            return letters[0];
        }
        int low = 0;
        int high = m-1;
        while(low < high){
            int mid = (high - low)/2 + low;
            if(letters[mid] > target){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return letters[low];
    }

⑩746.使用最小花费爬楼梯

2024.2.16 周五
题目：
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 ：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

  • 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。

思路：
下标： 0 1 2 … n-1
转化为：到下标 n 的最小花费
可以用一个数组dp[n]记录到达每一个台阶所需要的费用是多少
dp长度为 n + 1 (要包含最顶部)
因为可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯，所以
dp[0] == 0
dp[1] == 0
当2 ≤ i ≤ n 时 dp[i] == Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])

动态规划 100%

1
2
3
4
5
6
7
8
9
public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        for(int i = 2; i < n+1; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }

使用滚动数组优化空间

1
2
3
4
5
6
7
8
9
10
11
12
public int minCostClimbingStairs(int[] cost) {
        //使用滚动数组进行优化
        int n = cost.length;
        int pre = 0;
        int curr = 0;
        for(int i = 2; i < n+1; i++){
            int next = Math.min(curr + cost[i-1],pre + cost[i-2]);
            pre = curr;
            curr = next;
        }
        return curr;
    }

⑪747.至少是其他数字两倍的最大数

2024.2.17 周六
题目：
给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

思路1：
使用排序找最大值和次大值
copy[n-1] >= copy[n-2] * 2即可

self 19.33%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int dominantIndex(int[] nums) {
        int n = nums.length;
        int[] copy = Arrays.copyOf(nums,n);

        Arrays.sort(copy);
        if(copy[n-1] >= copy[n-2]*2){
            for(int i = 0; i < n; i++){
                if(nums[i] == copy[n-1]){
                    return i;
                }
            }
        }
        return -1;
    }

思路2：
使用遍历，直接找数组的最大值和次大值

100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int dominantIndex(int[] nums) {
        //直接找最大值和次大值
        int n = nums.length;
        int max1 = -1;
        int max2 = -1;
        int index = -1;
        for(int i = 0; i < n; i++){
            if(nums[i] > max1){
                max2 = max1;
                max1 = nums[i];
                index = i;
            }else if(nums[i] > max2){
                max2 = nums[i];
            }
        }
        return max1 >= max2 * 2 ? index : -1;
    }

⑫748.最短补全词

2024.2.18 周日
26个字母相关
题目：
给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有字母的单词。
忽略 licensePlate 中的 数字和空格 。不区分大小写。
如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
例如：licensePlate = “aBc 12c”，那么它的补全词应当包含字母 ‘a’、’b’ （忽略大写）和两个 ‘c’ 。
可能的 补全词 有 “abccdef”、”caaacab” 以及 “cbca” 。
请返回 words 中的 最短补全词 。
题目数据保证一定存在一个最短补全词。
当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。

思考：
需要得到字符串中每个字母出现的次数，可以用一个26长的数组记录
char[] toCharArray() ：将一个字符串转化为字符数组。
isLetter(char c) ： 判断字符是否是字母
toLowerCase(char c) - 将字符转换为小写 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] count = getCount(licensePlate);
        String result = null; //结果

        //遍历字符串数组中的每个字符串
        for(String str : words){
            int[] curCount = getCount(str);
            boolean ok = true; //记录当前字符串是否满足条件
            //对比这26个字母出现的次数
            for(int i = 0; i < 26; i++){
                if(curCount[i] < count[i]){
                    //不符合条件
                    ok = false;
                }
            }
            //更新结果
            if(ok && (result == null || str.length() < result.length())){
                result = str;
            }
        }
        return result;
    }

    //得到每个字符串中26个字母出现的次数
    public int[] getCount(String str){
        int[] count = new int[26];
        for(char s : str.toCharArray()){
            //如果是字母则记录
            if(Character.isLetter(s)){
                count[Character.toLowerCase(s) - 'a'] ++;
            }
        }
        return count;
    }
}

⑬766.托普利茨矩阵

2024.2.19 周一
二维数组
题目：
给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

思路：
由左上到右下的对角线上的元素都相同才可，可以从matrix[1][1]开始遍历，绕开第一行和第一列，只要保证matrix[i]
[j] == matrix[i-1][j-1]即可

遍历 100%

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] != matrix[i-1][j-1]){
                    return false;
                }
            }
        }
        return true;
    }

⑭804.唯一摩尔斯密码词

2024.2.20 周二
26个字母相关
题目：
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如:
‘a’ 对应 “.-“ ，
‘b’ 对应 “-…” ，
‘c’ 对应 “-.-.” ，以此类推。
为了方便，所有 26 个英文字母的摩尔斯密码表如下：
[“.-“,”-…”,”-.-.”,”-..”,”.”,”..-.”,”–.”,”….”,”..”,”.—“,”-.-“,”.-..”,”–”,”-.”,”—“,”.–.”,”–.-“,”.-.”,”…”,”-“,”..-“,”…-“,”.–”,”-..-“,”-.–”,”–..”]
给你一个字符串数组 words ，每个单词可以写成每个字母对应摩尔斯密码的组合。
例如，”cab” 可以写成 “-.-..–…” ，(即 “-.-.” + “.-“ + “-…” 字符串的结合)。
我们将这样一个连接过程称作 单词翻译 。
对 words 中所有单词进行单词翻译，返回不同 单词翻译 的数量。
输入: words = [“gin”, “zen”, “gig”, “msg”]
输出: 2
解释:
各单词翻译如下:
“gin” -> “–…-.”
“zen” -> “–…-.”
“gig” -> “–…–.”
“msg” -> “–…–.”
共有 2 种不同翻译, “–…-.” 和 “–…–.”.

思路：
要得到每个单词对应的摩斯密码，统计不同的样式，使用HashSet集合存储

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public static final String[] MORSE = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    
    public int uniqueMorseRepresentations(String[] words) {
        Set<String> set = new HashSet<>();
        for(String word:words){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                //组合摩斯密码
                sb.append(MORSE[c - 'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }
}

⑮806.写字符串需要的行数

2024.2.21 周三
26个字母相关
题目：
我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。
我们给定了一个数组 widths ，这个数组 widths[0] 代表 ‘a’ 需要的单位， widths[1] 代表 ‘b’ 需要的单位，…， widths[25] 代表 ‘z’ 需要的单位。
现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。
输入:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = “abcdefghijklmnopqrstuvwxyz”
输出: [3, 60]
解释:
所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
我们需要2个整行和占用60个单位的一行。

思考：
一个字母只能在同一行出现，需要判断何时换行

直接遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int line = 1; //行数
        int width = 0; //当前行宽
        
        for(int i = 0; i < s.length(); i++){
            //得到每一个字母对应的单位长度
            char c = s.charAt(i); 
            int charWidth = widths[c - 'a'];
            
            if(charWidth + width > 100){//需要换行
                line++;
                width = charWidth;
            }else{//不需要换行
                width += charWidth;
            }
        }
  
        return new int[]{line,width};
    }
}

⑯812.最大三角形面积

2024.2.22 周四
二维数组(取不同的三个点的坐标)
题目：
给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。
从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。
与真实值误差在 10的-5次方 内的答案将会视为正确答案。

思路：
从给出的坐标点中取3个点，用三个坐标点求三角形的面积
S = =1/2∗[x1(y2−y3)+x2(y3−y1)+x3(y1−y2)] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double res = 0;
        for(int i = 0; i < n-2; i++){
            for(int j = i+1; j < n-1;  j++){
                for(int k = j+1; k < n; k++){
                    int[] point1 = points[i];
                    int[] point2 = points[j];
                    int[] point3 = points[k];
                    int x1 = point1[0], y1 = point1[1];
                    int x2 = point2[0], y2 = point2[1];
                    int x3 = point3[0], y3 = point3[1];
                    res = Math.max(res,0.5 * Math.abs(x1*(y2-y3)+ x2*(y3-y1)+x3*(y1-y2)));
                }
            }
        }
        return res;
    }

⑰819.最常见的单词

2024.2.23 周五
题目：
给你一个字符串 paragraph 和一个表示禁用词的字符串数组 banned ，返回出现频率最高的非禁用词。
题目数据 保证 至少存在一个非禁用词，且答案 唯一 。
paragraph 中的单词 不区分大小写 ，答案应以 小写 形式返回。

思考：
需要统计paragraph中每个不是禁用单词出现的次数，得到次数最多的非禁用词

从字符串句子中摘出字符串单词：如果当前不是字母且该字符的前一个字符是字母，即为一个单词的结束

如果段落的最后一个字符是字母，则当遍历结束时需要对段落中的最后一个单词判断是否为禁用单词，如果不是禁用单词则将次数加 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        //将banned以HashSet形式存储 方便后续判断是否是禁用词
        Set<String> ban = new HashSet<>();
        for(String word : banned){
            ban.add(word);
        }
        //遍历paragraph统计非禁用词出现的次数
        Map<String,Integer> map = new HashMap<>();
        int maxCount = 0; //记录出现最多的次数
        StringBuilder sb = new StringBuilder(); //拼接单词
        int n = paragraph.length();
        for(int i = 0; i <= n; i++){
            if(i < n && Character.isLetter(paragraph.charAt(i))){
                //当前字符是字母，换成小写字母再进行拼接
                sb.append(Character.toLowerCase(paragraph.charAt(i)));
            }else if(sb.length()>0){ //到达顶端(包含最后一个字符也是字母的情况)
                //①当前不是字母 且字符拼接器中已存在字母 ②到达末尾
                String word = sb.toString();
                //如果不是禁用词则添加到map中，并统计其出现的次数
                if(!ban.contains(word)){
                    int count = map.getOrDefault(word,0) + 1;
                    map.put(word,count);
                    maxCount = Math.max(maxCount,count);
                }
                //将字符拼接器清空
                sb.setLength(0);
            }
        }

        //根据maxCount得到对应出现次数最多的单词
        //遍历map
        String res = "";
        Set<Map.Entry<String,Integer>> entries = map.entrySet();
        for(Map.Entry<String,Integer> entry : entries){
            String key = entry.getKey();
            int value = entry.getValue();
            if(maxCount == value){
                res = key;
                break;
            }
        }
        return res;
    }
}

⑱821.字符的最短距离

2024.2.24 周六
题目：
给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
返回一个整数数组 answer，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

思路：
分别找到每一个 i 左边和右边离得最近的 c ，得到最小距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] res = new int[n];
        Arrays.fill(res,n+1);

        //左
        for(int i = 0,j = -1; i < n; i++){
            //j记录索引
            if(s.charAt(i) == c) j = i;
            if(j != -1) res[i] = i-j;
        }

        //右
        for(int i = n - 1, j = -1; i >= 0; i--){
            if(s.charAt(i) == c) j = i;
            if(j != -1) res[i] = Math.min(res[i],j-i);
        }
        return res;
    }
}

⑲832.翻转图像

2024.2.25 周日
二进制
二维数组

题目：
给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。
例如，水平翻转 [1,1,0] 的结果是 [0,1,1]。
反转图片的意思是图片中的 0 全部被 1 替换，1 全部被 0 替换。
例如，反转 [0,1,1] 的结果是 [1,0,0]。

思考：
进行翻转：image[i][left] 和 image[i][right]的元素的值会互换
反转：image[i][left] 和 image[i][right]的元素的值会改变
left right
0 0 -> 1 1
1 1 -> 0 0
(当left = right时改变)
**按位异或(^)**：二进制位按位相异或，相同为0，不同为1。
1 0 -> 1 0
0 1 -> 0 1
(当left ≠ right时不变)

相同时要换，不同时不用改变

模拟优化 + 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;

        //遍历一遍即可
        for(int i = 0; i < n; i++){
            int left = 0;
            int right = n-1;
            while(left < right){
                if(image[i][left] == image[i][right]){
                    image[i][left] ^= 1;
                    image[i][right] ^= 1;
                }
                left++;
                right--;
            }
            if(left == right){
                image[i][left] ^= 1;
            }
        }
        return image;
    }
}

先反转再翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;
        //左右翻转
        for(int i = 0; i < n; i++){
            int[] temp = image[i].clone();
            for(int j = 0; j < n; j++){
                image[i][j] = temp[n-1-j];
            }
        }
        //翻转
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                image[i][j] ^= 1;
            }
        }
        return image;
    }
}

⑳860.柠檬水找零

2024.2.26 周一
题目：
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

思路：
5美元 不操作
10美元 找一张5美元
20美元 找一张10美元和一张5美元(优先) / 找三张5美元

贪心 一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;

        for(int bill : bills){
            if(bill == 5){
                five++;
            }else if(bill == 10){
                if(five == 0){
                    return false;
                }
                five--;
                ten++;
            }else{
                if(five > 0 && ten > 0){
                    five --;
                    ten --;
                }else if(five >= 3){
                    five -= 3;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信