写在最前

数组 / 字符串

交替合并字符串

  • 方式一：交替添加字符。如果其中一个字符串比另一个长，会将多余的字符追加到合并后字符串的末尾。
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 (前缀树)

搜索推荐系统

区间集合

无重叠区间

用最少数量的箭引爆气球

单调栈

每日温度

股票价格跨度