写在最前

数组 / 字符串

交替合并字符串

  • 方式一：交替添加字符。如果其中一个字符串比另一个长，会将多余的字符追加到合并后字符串的末尾。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public static String mergeAlternately(String word1, String word2) {
            int l1 = word1.length();
            int l2 = word2.length();
            int minLen = Math.min(l1, l2);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < minLen; i++) {
                sb.append(word1.charAt(i));
                sb.append(word2.charAt(i));
            }
            if (minLen == l1)
                sb.append(word2.substring(minLen));
            else
                sb.append(word1.substring(minLen));
            return sb.toString();
        } 
    }
  • 方式二：使用两个指针i和j分别指向两个字符串的当前字符位置。通过一个循环，不断将对应位置的字符添加到结果字符串中，直到其中一个字符串遍历完。然后将剩余未遍历完的字符串直接追加到结果字符串末尾。这种方法避免了substring操作，可以稍微提高性能。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public static String mergeAlternately(String word1, String word2) {
            int l1 = word1.length();
            int l2 = word2.length();
            int i = 0;
            int j = 0;
            StringBuilder sb = new StringBuilder();
            while (i < l1 || j < l2) {
                if (i < l1)
                    sb.append(word1.charAt(i++));
                if (j < l2)
                    sb.append(word2.charAt(j++));
            }
            return sb.toString();
        } 
    }

字符串的最大公因子

  • 题目找str1和str2的最大公子串，那么str1和str2都是n个子串组成的，那么如果不满足(str1 + str2).equals(str2 + str1)，那么直接返回空字符串（例如示例三），反之如果满足，则str1和str2长度的最大公因子就是子串长度，我们用substring()可以获取到子串。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
        // 求最大公因子
        public static int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

        public String gcdOfStrings(String str1, String str2) {
            // 不满足条件，返回空字符串
            if (!(str1 + str2).equals(str2 + str1)) return "";
            // 满足条件，求str1和str2的最大公因子
            return str1.substring(0, gcd(str1.length(), str2.length()));
        }
    }

拥有最多糖果的孩子

  • 找出最多糖果的数量，其余孩子糖果数 + 额外糖果数 >= 最多糖果数，结果为true
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        ArrayList<Boolean> res = new ArrayList<>();
        int max = 0;
        for (int candy : candies) {
            max = Math.max(max, candy);
        }
        for (int i = 0; i < candies.length; i++) {
            res.add(candies[i] + extraCandies >= max);
        }
        return res;
    }
}

种花问题

  • 贪心：当前位置为0，前面为0，后面为0，那就能种。需要注意判断一下边界条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0
                    // 右边界
                    && (i + 1 == flowerbed.length || flowerbed[i + 1] == 0)
                    // 左边界
                    && (i == 0 || flowerbed[i - 1] == 0)) {
                flowerbed[i] = 1;
                count++;
            }
        }
        return count >= n;
    }
}

反转字符串中的元音字母

  • 双指针，首尾遍历元音字母，找到后交换位置
    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 String reverseVowels(String s) {
            int l = 0, r = s.length() - 1;
            char[] str = s.toCharArray();
            while (l < r) {
                while (l < s.length() && !isTarget(str[l]))
                    l++;
                while (r > 0 && !isTarget(str[r]))
                    r--;
                if (l < r) {
                    swap(str, l, r);
                    l++;
                    r--;
                }
            }
            return new String(str);
        }

        boolean isTarget(char c) {
            return "AEIOUaeiou".indexOf(c) >= 0;
        }

        void swap(char[] str, int i, int j) {
            char tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
        }
    }

反转字符串中的单词

  • 先去除首尾空格，然后正则匹配连续空格切分，最后翻转列表，加入空格拼接，返回结果
1
2
3
4
5
6
7
class Solution {
    public String reverseWords(String s) {
        String[] res = s.trim().split("\\s+"); 
        Collections.reverse(Arrays.asList(res));
        return String.join(" ", res);
    }
}

除自身以外数组的乘积

  • 不让用除法，且要在O(n)的时间复杂度内完成，那就只能一层循环，可以通过计算前缀积和后缀积最后使其相乘得出结果
nums 1 2 3 4
pre 1 1 2 6
suf 24 12 4 1
res 24 12 8 6 
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[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 前缀积计算
        int[] pre = new int[n];
        pre[0] = 1;
        for (int i = 1; i < n; i++) {
            pre[i] = nums[i - 1] * pre[i - 1];
        }
        // 后缀积计算
        int[] suf = new int[n];
        suf[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        // 结果计算
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = pre[i] * suf[i];
        }
        return res;
    }
}
  • 降低到O(1)的空间复杂度：用res数组代替pre数组，用一个suf变量代替suf数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public int[] productExceptSelf(int[] nums) {
            int n = nums.length;
            int[] res = new int[n];
            res[0] = 1;
            for (int i = 1; i < n; i++) {
                res[i] = nums[i - 1] * res[i - 1];
            }
            int suf = 1;
            for (int i = n - 1; i >= 0; i--) {
                res[i] *= suf;
                suf *= nums[i];
            }
            return res;
        }
    }

递增的三元子序列

压缩字符串

双指针

移动零

  • 方式一：双指针遍历，快指针遍历不为0的元素，赋值给慢指针，快指针遍历到末尾结束，慢指针将剩余元素设0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public void moveZeroes(int[] nums) {
            if (nums == null || nums.length == 0)
                return;
            int fast = 0, slow = 0;
            // 快指针遍历不为0的元素
            for (; fast < nums.length; fast++) {
                if (nums[fast] != 0) {
                    // 赋值给慢指针
                    nums[slow++] = nums[fast];
                }
            }
            // 慢指针将剩余元素设0
            for (; slow < nums.length; slow++) {
                nums[slow] = 0;
            }
        }
    }
  • 方式二
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public void moveZeroes(int[] nums) {
            if (nums == null || nums.length == 0)
                return;
            int fast = 0, slow = 0;
            for (; fast < nums.length; fast++) {
                if (nums[fast] != 0) {
                    int tmp = nums[fast];
                    nums[fast] = nums[slow];
                    nums[slow++] = tmp;
                }
            }
        } 
    }

判断子序列

  • 双指针遍历，如果s是t的子序列，那么s中的所有元素都会按顺序在t中依次出现，一个指针遍历s，另一个指针遍历t，最终判断指针是否遍历到了s的末尾
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
        public boolean isSubsequence(String s, String t) {
            int m = s.length(), n = t.length();
            int i = 0, j = 0;
            while (i < m && j < n) {
                if (s.charAt(i) == t.charAt(j)) {
                    i++;
                }
                j++;
            }
            return i == m;
        }
    }

盛最多水的容器

  • 设双指针i, j分别指向height[0], height[n - 1]，并逐渐向内收缩，那么面积S(i, j) = (j - i) * min(height[i], height[j])，此时的面积取决于min(height[i], height[j])
    • 如果向内移动短板，那么min(height[i], height[j])是可能增大的（也有可能变小），即移动短板面积可能会增大
    • 如果向内移动长板，那么min(height[i], height[j])是减小或不变的，即移动长板面积一定会变小
  • 所以为了求出最大面积，肯定是不能移动长板的，只能移动短板赌一波，每次移动短板之后更新最大值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        // 双指针一首一尾
        int i = 0, j = height.length - 1;
        while (i < j) {
            // 移动短板，更新最大值
            ans = height[i] < height[j] ?
                    Math.max(ans, (j - i) * height[i++]) :
                    Math.max(ans, (j - i) * height[j--]);
        }
        return ans;
    }
}

K 和数对的最大数目

滑动窗口

子数组最大平均数 I

  • 计算固定长度区间内数的最大平均值，采用滑动窗口的思想，即维护一个长度为k的滑动窗口，先计算长度为k的窗口初值，然后每次窗口向右移动的时候，加上最右边的元素，减掉最左边的元素，更新窗口最大值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public static double findMaxAverage(int[] nums, int k) {
            int sum = 0;
            // 计算长度为k的窗口的初值
            for (int i = 0; i < k; i++) {
                sum += nums[i];
            }
            int res = sum;
            // 每次向右移动时
            for (int i = k; i < nums.length; i++) {
                // 加上最右端元素，减去最左端元素
                sum = sum + nums[i] - nums[i - k];
                // 更新最大值
                res = Math.max(res, sum);
            }
            // 取平均
            return 1.0 * res / k;
        }
    }

定长子串中元音的最大数目

  • 一样的套路，唯一一点区别就是需要判断新加入元素和剔除元素是否为元音字母
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public int maxVowels(String s, int k) {
            int current = 0;
            char[] chars = s.toCharArray();
            for (int i = 0; i < k; i++) {
                current += isVowel(chars[i]);
            }
            int res = current;
            for (int i = k; i < chars.length; i++) {
                current = current + isVowel(chars[i]) - isVowel(chars[i - k]);
                res = Math.max(res, current);
            }
            return res;
        }

        int isVowel(char c) {
            return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') ? 1 : 0;
        }
    }

最大连续1的个数 III

  • 将问题转换为：找一个最长子数组，该子数组最多包含k个0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int longestOnes(int[] nums, int k) {
            int res = 0, count = 0, left = 0, right = 0, n = nums.length;
            // 右边界遍历到结尾
            while (right < n) {
                // 右边界右移，如果遇到0，则计数+1
                if (nums[right] == 0)
                    count++;
                // 如果此时left ~ right的子数组中的0已经超过了k个
                while (count > k) {
                    // 左边界右移，如果左边界遇到了0，则将其移除，计数-1
                    if (nums[left++] == 0)
                        count--;
                }
                // 每次操作完毕更新结果
                res = Math.max(res, right - left + 1);
                // 右边界右移
                right++;
            }
            return res;
        }
    }

删掉一个元素以后全为1的最长子数组

  • 与上题类似，将其转换为：找一个最长子数组，最多只包含1个0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int longestSubarray(int[] nums) {
            int res = 0, count = 0, left = 0, right = 0, n = nums.length;
            while(right < n) {
                if(nums[right] == 0) {
                    count++;
                }
                while(count > 1) {
                    if(nums[left++] == 0) {
                        count--;
                    }
                }
                res = Math.max(res, right - left + 1);
                right++;
            }
            return res - 1;
        }
    }

前缀和

找到最高海拔

  • 简单的前缀和
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
        public int largestAltitude(int[] gain) {
           int res = 0, sum = 0;
           for(int x : gain) {
               sum += x;
               res = Math.max(res, sum);
           }
           return res;
        }   
    }

寻找数组的中心下标

  • 求前缀和和后缀和，然后从左往右遍历，找到第一个前缀和和后缀和相等的下标
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int pivotIndex(int[] nums) {
            int n = nums.length;
            int[] preSum = new int[n];
            preSum[0] = 0;
            int[] extSum = new int[n];
            extSum[n - 1] = 0;
            for (int i = 1; i < n; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
                extSum[n - 1 - i] = extSum[n - i] + nums[n - i];
            }
            for (int i = 0; i < n; i++) {
                if (preSum[i] == extSum[i])
                    return i;
            }
            return -1;
        }
    }
  • 优化思路：如果有符合条件的中心下标，则有左求和 × 2 + 中心下表值 = 总和
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
        public int pivotIndex(int[] nums) {
            int sum = Arrays.stream(nums).sum();
            int leftSum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (leftSum * 2 + nums[i] == sum) {
                    return i;
                }
                leftSum += nums[i];
            }
            return -1;
        }
    }

哈希表 / 哈希集合

找出两数组的不同

  • 请叫我API侠
    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 List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
            HashSet<Integer> set1 = new HashSet<>();
            HashSet<Integer> set2 = new HashSet<>();
            for (int n : nums2) {
                set2.add(n);
            }
            for (int n : nums1) {
                set1.add(n);
            }
            for (int n : nums2) {
                set1.remove(n);
            }
            for (int n : nums1) {
                set2.remove(n);
            }

            List<List<Integer>> res = new ArrayList<>();
            res.add(set1.stream().toList());
            res.add(set2.stream().toList());
            return res;
        }
    }
  • 更方便的API
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
            HashSet<Integer> set1 = new HashSet<>();
            HashSet<Integer> set2 = new HashSet<>();
            for (int n : nums2) {
                set2.add(n);
            }
            for (int n : nums1) {
                set1.add(n);
                set2.remove(n);
            }
            for (int n : nums2) {
                set1.remove(n);
            }
            
            return List.of(List.copyOf(set1), List.copyOf(set2));
        }
    }

独一无二的出现次数

  • 哈希表存储每个数字出现的次数，判断value是否有重复值，把value存入HashSet，观察value的个数会不会减少即可
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution {
        public boolean uniqueOccurrences(int[] arr) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int n : arr) {
                map.put(n, map.get(n) == null ? 0 : map.get(n) + 1);
            }
            return new HashSet<>(map.values()).size() == map.size();
        }
    }

确定两个字符串是否接近

相等行列对

栈

从字符串中移除星号

行星碰撞

字符串解码

队列

最近的请求次数

Dota2 参议院

链表

删除链表的中间节点

奇偶链表

反转链表

链表最大孪生和

二叉树 - 深度优先搜索

二叉树的最大深度

叶子相似的树

统计二叉树中好节点的数目

路径总和 III

二叉树中的最长交错路径

二叉树的最近公共祖先

二叉树 - 广度优先搜索

二叉树的右视图

最大层内元素和

二叉搜索树

二叉搜索树中的搜索

删除二叉搜索树中的节点

图 - 深度优先搜索

钥匙和房间

省份数量

重新规划路线

除法求值

图 - 广度优先搜索

迷宫中离入口最近的出口

腐烂的橘子

堆 / 优先队列

数组中的第K个最大元素

无限集中的最小数字

最大子序列的分数

雇佣 K 位工人的总代价

二分查找

猜数字大小

咒语和药水的成功对数

寻找峰值

爱吃香蕉的珂珂

回溯

电话号码的字母组合

组合总和 III

动态规划 - 一维

第 N 个泰波那契数

使用最小花费爬楼梯

打家劫舍

多米诺和托米诺平铺

动态规划 - 多维

不同路径

最长公共子序列

买卖股票的最佳时机含手续费

编辑距离

位运算

比特位计数

只出现一次的数字

或运算的最小翻转次数

前缀树

实现 Trie (前缀树)

搜索推荐系统

区间集合

无重叠区间

用最少数量的箭引爆气球

单调栈

每日温度

股票价格跨度