刷穿力扣（1~30）

本文最后更新于 446 天前，其中的信息可能已经有所发展或是发生改变。

1. 两数之和

哈希表
遍历数组，同时用 HashMap 维护已出现过的数及其下标
若当前的数 nums[i] 满足 target - nums[i] 曾经出现过，则直接返回
否则将其加入到哈希表中。

class Solution {
     public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> st = new HashMap<>();
        for (int i = 0; i < nums.length; i ++) {
            if (st.containsKey(target - nums[i])) {
                return new int[]{st.get(target - nums[i]), i};
            }
            else st.put(nums[i], i);
        }
        return null;
    }
}

2. 两数相加

链表
使用 res 维护链表，ans 指向 res 头结点
遍历链表 l1 和 l2，取得当前节点的值分别为 a，b ，并用 base 记录进位
则，新的 res 节点为 a + b + base % 10，base = (a + b + base) / 10
不断将 res 更新为 res.next，最后若 base != 0 则补上进位即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode();
        ListNode ans = res;
        int base = 0;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int sum = a + b + base;

            base = sum / 10;
            res.next = new ListNode(sum % 10);
            res = res.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (base != 0) res.next = new ListNode(base);
        return ans.next;
    }
}

3. 无重复字符的最长子串

滑动窗口
维护一个集合或布尔数组，保存当前出现过的字符
设窗口左边界为 i，右边界为 j，当前字符为 s[j]
当出现重复字符时窗口左边界 i 向右移动，并不断将 vis[i] 移除，直到 vis[i] === s[j] 被排除
持续更新窗口最大长度 j - i + 1 即为答案

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        HashSet<Character> st = new HashSet<>();
        for (int i = 0, j = 0; i < s.length(); i++) {
            while (st.contains(s.charAt(i)) && j < i) {
                st.remove(s.charAt(j++));
            }
            st.add(s.charAt(i));
            ans = Math.max(ans, st.size());
        }
        return ans;
    }
}

优化：

上述两种实现滑窗的方式都需要“持续性地移动边界”这个操作
不如换一种思路——使用 HashMap 来更新每个字符最近一次出现的索引
当我们遍历字符串 s 时，仍使用 i 和 j 来表示当前无重复字符子串的起始位置和结束位置，初始时 i = j = 0。
在每一步迭代中，检查当前字符 s[j] 是否已经在 HashMap 中存在：
- 如果存在，则更新左指针 i 移动到重复字符的下一个位置，保证左指针 i 始终指向当前无重复字符子串的起始位置。
将 s[j] 其加入 HashMap 中，并更新窗口最大长度 j - i + 1。
最后，右指针 j 向右移动一位，继续遍历字符串 s，直到右指针 j 到达字符串的末尾
这样只需更新字符出现的索引即可，无需重复遍历。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        HashMap<Character, Integer> vis = new HashMap<>();
        int n = s.length();
        int i = 0, j = 0;
        while (i < n && j < n) {
            if (vis.containsKey(s.charAt(j))) {
                i = Math.max(vis.get(s.charAt(j)) + 1, i);  // 更新索引，取较大值为新的左指针位置
            }
            vis.put(s.charAt(j), j);  
            ans = Math.max(ans, j - i + 1);
            j ++;
        }
        return ans;
    }
}

4. 寻找两个正序数组的中位数

暴力
合并两个有序数组，然后取中位数即可

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] nums = new int[n + m];
        int idx = 0, idx1 = 0, idx2 = 0;
        while (idx1 < n && idx2 < m) {
            if (nums1[idx1] < nums2[idx2]) nums[idx ++] = nums1[idx1 ++];
            else nums[idx ++] = nums2[idx2 ++];
        }
        while (idx1 < n) nums[idx ++] = nums1[idx1 ++];
        while (idx2 < m) nums[idx ++] = nums2[idx2 ++];
        if (((n + m) & 1) == 1) return nums[(n + m) >> 1];
        else return (double)(nums[(n + m) >> 1] + nums[(n + m - 1) >> 1]) / 2;
    }
}

5. 最长回文子串

dp
在这种情况下，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从索引 i 到索引 j 的子串是否是回文。
根据回文的定义，我们可以得出以下状态转移方程：
- dp[i][j] = true，如果 i == j（单个字符是回文）
- dp[i][j] = true，如果 s[i] == s[j] 且 dp[i + 1][j - 1] == true（首尾字符相等且去掉首尾后的子串是回文）
- dp[i][j] = false，其他情况
基于这个状态转移方程，我们可以使用动态规划来填充 dp 数组。然后，我们可以根据dp数组找到最长回文子串。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";

        // // 单个字符或相同的两个是回文
        for (int i = 0; i < n; i++) {
            if (ans.length() <= 1) ans = s.substring(i, i + 1);
            dp[i][i] = true;
            if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                ans = s.substring(i, i + 2);
            }
        }

        // 长度大于2的子串
        for (int len = 3; len <= n; len ++) {
            for (int i = 0; i <= n - len; i ++) {
                int j = i + len - 1;
                if (j - 1 >= 0 && s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    ans = s.substring(i, j + 1);
                }
            }
        }

        return ans;
    }
}

6. N 字形变换

模拟
首先排除特殊情况，当 numRows <= 1 || s.length() <= numRows 直接返回 s
其他情况可以利用偏移量对字符坐标进行模拟，将结果存到二维数组中

若使用 StringBuilder 来构造模拟结果集，此时发现仅需要行数变化即可
则最终将结果集转换为字符串返回即可

class Solution {
    public String convert(String s, int numRows) {
        int n = s.length();
        if (numRows <= 1 || n <= numRows) return s;  // 特殊情况直接返回
        int l = 0, d = 0;  // l 记录当前所在行数，d 记录当前的方向
        StringBuilder mp[] = new StringBuilder[numRows];  // 结果集
        for (int i = 0; i < numRows; i ++) {              // 初始化结果集，每一行都是一个 StringBuilder
            mp[i] = new StringBuilder();
        }
        mp[0].append(s.charAt(0));      // 将第一个字符先加入
        for (int i = 1; i < n; i ++) {  // 从第二个字符开始遍历
            if ((d == 0 && l == numRows - 1) || (d == 1 && l == 0)) d = 1 - d;  // 判断方向改变条件
            l += d == 0 ? 1 : -1; 
            mp[l].append(s.charAt(i));
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder st : mp) {
            ans.append(st.toString());
        }
        return ans.toString();
    }
}

7. 整数反转

模拟
循环倒除得到每一位，再反向乘加即可
最大值通过 Integer.MAX_VALUE 获取，最小值可以通过 Integer.MIN_VALUE 获取
当 ans 大于最值除以 $10$ 的时候，下一步计算会溢出
由于输入的数在 Integer 范围内，可以证明，在计算结束前，不存在 ans 超过最值的情况

class Solution {
    public int reverse(int x) {
        int ans = 0;
        int maxn = Integer.MAX_VALUE / 10;
        int minn = Integer.MIN_VALUE / 10;
        while (x != 0) {
            if (ans > maxn || ans < minn) return 0;
            int t = x % 10;
            ans = ans  * 10 + t;
            x /= 10;
        }
        return ans;
    }
}

8. 字符串转换整数 (atoi)

模拟
首先去除空格，然后判断起始字符是否为 + 或 -
判断溢出时，最大值通过 Integer.MAX_VALUE 获取，最小值可以通过 Integer.MIN_VALUE 获取
当 ans 大于最值除以 $10$ 的时候，下一步计算会溢出
当 ans 等于最值除以 $10$ 的时候，用最值模 $10$ 的余数判断下一步计算是否溢出

class Solution {
    public int myAtoi(String s) {
        String st = s.trim();
        int ans = 0;
        boolean flag = false;  // 结果符号： false 为 +，true 为 -
        // 计算最值 / 10
        int maxn = Integer.MAX_VALUE / 10;
        int minn = Integer.MIN_VALUE / 10;
        // 计算最值 % 10
        int maxt = Integer.MAX_VALUE % 10;
        int mint = Integer.MIN_VALUE % 10;
        for (int i = 0; i < st.length(); i ++) {
            char p = st.charAt(i);
            if (p == '-' && i == 0) flag = true;
            else if (p == '+' && i == 0) continue;
            else if (p >= '0' && p <= '9') {
                int t = p - '0';
                // 判断是否溢出
                if (flag && (- ans < minn || (- ans == minn && - t < mint))) return Integer.MIN_VALUE;
                if (!flag && (ans > maxn || (ans == maxn && t > maxt))) return Integer.MAX_VALUE;  
                ans = ans * 10 + t;
            }
            else break;
        }
        if (flag) ans *= -1;
        return ans;
    }
}

9. 回文数

暴力

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        int ans = 0;
        int y = x;
        while(x != 0) {
            ans = ans * 10 + (x % 10);
            x /= 10;
        }
        return y == ans;
    }
}

10. 正则表达式匹配

dp
状态表示：
- 状态 dp[i][j] 表示字符串 s 的前 i 个字符和字符规律 p 的前 j 个字符是否匹配。
状态计算：
- 当 s 的第 i 个字符和 p 的第 j 个字符相等，或者 p 的第 j 个字符为 . 时说明当前字符匹配，即 dp[i][j] = dp[i-1][j-1] 。
- 当 p 的第 j 个字符为 * 时，需要考虑两种情况，满足其一即匹配：
  1. * 匹配零个前面的元素，即 dp[i][j] = dp[i][j-2] 。
  2. * 匹配一个或多个前面的元素时，要满足 s.charAt(i) == p.charAt(j - 1) || s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'，即 dp[i][j] = dp[i-1][j]。
初始化：
- 两者为空也为匹配，即 dp[0][0] = true
- 对于 p ，若 p.charAt(i) == '*' 说明当前星号可以匹配前面的字符零次，即 dp[0][i] = dp[0][i - 2]。

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i ++) {
            if (p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 2];
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                // i, j 从 1 开始，s, p 需要偏移 -1
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
                }
            }
        }
        return dp[n][m];
    }
}

11. 盛最多水的容器

双指针
设 l 为容器的左边界，r 为右边界，初始化 l = 0, r = height.length - 1
当 height[l] < height[l + 1] 或 height[r] < height[r - 1] 时，容器体积可能增大

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0, r = n - 1;
        int ans = Math.min(height[l], height[r]) * (n - 1);
        while(l < r) {
            // 优化：通过两个 while 快速找到大于等于当前最低边界的 l 和 r 所在位置，减少不必要的计算
            int t = Math.min(height[l], height[r]);
            while (l < r && height[l] <= t) l ++;
            while (r > l && height[r] <= t) r --;
            ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
        }
        return ans;
    }
}

12. 整数转罗马数字

模拟
按照题目规则转换
每次都选择尽量大的位数进行转换即可

public class Solution {
    public String intToRoman(int num) {
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            while (num >= nums[i]) {
                stringBuilder.append(romans[i]);
                num -= nums[i];
            }
        }
        return stringBuilder.toString();
    }
}

13. 罗马数字转整数

模拟
反过来模拟即可
从右至左，若当前罗马字母比右边的小，则说明需要减去，否则做加法即可

class Solution {
    public int romanToInt(String s) {
        int[] nums = {1000, 500, 100, 50, 10, 5, 1};
        char[] romans = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};

        int n = s.length();
        int flag = getIdx(s.charAt(n - 1), romans);
        int num = nums[flag];
        for (int i = n - 2; i >= 0; i --) {
            int t = getIdx(s.charAt(i), romans);
            if (nums[t] < nums[flag]) num -= nums[t];
            else num += nums[t];
            flag = t;
        }
        return num;
    }

    private static int getIdx(char p, char[] romans) {
        for (int i = 0; i < romans.length; i ++) {
            if (p == romans[i]) return i;
        }
        return -1;
    }
}

14. 最长公共前缀

模拟
初始化公共前缀为 res = strs[0]
从 i = 1 循环枚举 strs[i] 判断是否满足 strs[i].startsWith(res)
若不满足则循环找到 res 的字串，直到满足为止

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String res = strs[0];
        for (int i = 1; i < strs.length; i ++) {
            while (!strs[i].startsWith(res)){
                res = res.substring(0, res.length() - 1);
            }
        }
        return res;
   }
}

15. 三数之和

双指针
首先将数组从小到大排序，使得数组单调
则要寻找三数之和为 $0$，必须保证 nums[i] < 0，左指针 j = i + 1，右指针k = n - 1，即 sum = nums[i] + nums[j] + nums[k]
当 sum < 0 说明 nums[j] 太小，则指针 j ++
当 sum > 0 说明 nums[k] 太大，则指针 k --
当 sum == 0 说明满足条件，此时需要将重复的 nums[j] 和 nums[k] 排除，即两个指针收缩，直到不再重复。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 排除特殊情况
        if (n < 3) return ans;
        Arrays.sort(nums);
        for (int i = 0; i < n; i ++) {
            // nums[i] > 0 之后不再存在满足条件的结果，直接返回
            if (nums[i] > 0) return ans;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) j ++;
                else if (sum > 0) k --;
                else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]); list.add(nums[j]); list.add(nums[k]);
                    ans.add(list);
                    // 收缩指针，去重
                    while (j + 1 <= k && nums[j] == nums[j + 1]) j ++; 
                    while (j + 1 <= k && nums[k] == nums[k - 1]) k --;
                    j ++; k --;
                }
            }
            // 去除重复的 nums[i]
            while (i + 1 < n && nums[i + 1] == nums[i]) i ++;
        }
        return ans;
    }
}

16. 最接近的三数之和

双指针
和上一题思路相近，不同的是我们需要维护一个 sum = nums[i] + nums[j] + nums[k] 和 target 差值的最小值

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int flag = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                int t = Math.abs(sum - target);
                if (t < flag) {
                    flag = t;
                    ans = sum;
                }
                if (sum < target) j ++;
                else k --;
            }
            while (i + 1 < n && nums[i] == nums[i + 1]) i ++;
        }
        return ans;
    }
}

17. 电话号码的字母组合

DFS
递归的每一层视作对 digits[0] 所对应映射 "xxx" 的枚举
每一层中，利用循环枚举 "xxx" 的每一位，然后继续递归
当递归的层数 u == digits.length() 时将当前累计的字符串加入答案列表并回溯

class Solution {
    private static String vis[] = new String[]{
        "", "",  // 空出 0, 1 的位置
        "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) return ans;
        // res 记录当前累计的字符
        StringBuilder res = new StringBuilder();
        dfs(digits, 0, res, ans);
        return ans;
    }

    private void dfs(String digits, int u, StringBuilder res, List<String> ans) {
        // 满足长度 ans 添加 res 并返回
        if (u == digits.length()) {
            ans.add(res.toString());
            return ;
        }
        int digit = digits.charAt(u) - '0';
        String letters = vis[digit];
        for (int i = 0; i < letters.length(); i ++) {
            res.append(letters.charAt(i));       // 将枚举的 xxx 的第 i 个字符累计
            dfs(digits, u + 1, res, ans);        // 递归到 u + 1 层
            res.deleteCharAt(res.length() - 1);  // 恢复现场
        }
    }
}

18. 四数之和

双指针
三数之和基础上，枚举第一个数 nums[i]，剩下三个数计算三数之和为 target - nums[i]
注意数据范围会爆 int
有意思吗力扣出题人出这种脑瘫题目😅😅😅😅😅😅😅😅😅😅😅😅😅😅😅😅😅

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        // 排除特殊情况
        if (n < 4) return ans;
        Arrays.sort(nums);
        for (int i = 0; i < n; i ++) {
            int ftarget = target - nums[i];
            for (int j = i + 1; j < n; j ++) {
                int k = j + 1, l = n - 1;
                while (k < l) {
                    long sum = (long)nums[j] + nums[k] + nums[l]; // 使用 long 类型存储和
                    if (sum < ftarget) k ++;
                    else if (sum > ftarget) l --;
                    else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); list.add(nums[l]);
                        ans.add(list);
                        while (k + 1 <= l && nums[k] == nums[k + 1]) k ++;
                        while (k + 1 <= l && nums[l] == nums[l - 1]) l --;
                        k ++; l --;
                    }
                }
                while (j + 1 < n && nums[j + 1] == nums[j]) j ++;
            }  
           while (i + 1 < n && nums[i + 1] == nums[i]) i ++;
        }
        return ans;
    }
}

19. 删除链表的倒数第 N 个结点

模拟
遍历一遍链表得到链表长度 size
特判：当 size <= 1 或 n - size == 0 时返回 null
遍历链表，当 idx == n - size - 1 说明下一个节点即为要删除的节点，直接修改指向即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int size = 0;
        for (ListNode i = head; i != null; i = i.next) size ++;
        if (size <= 1) return null;
        if (n - size == 0) return head.next;
        int idx = 0;
        for (ListNode i = head; i != null; i = i.next) {
            if (idx == size - n - 1) {
                i.next = i.next.next;
            }
            idx ++;
        }
        return head;
    }
}

优化：

双指针
为防止删除头结点的情况出现，利用 ListNode ans 指向 head
设 ListNode 指针 l 和 r 都指向 ans
将 r 先移动 n + 1 的距离，然后再让 l 和 r 同时移动
当 r.next == null 说明 l 位于要被删除节点的前一个节点
删除操作即为 l.next = l.next.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode ans = new ListNode();
        ans.next = head;
        ListNode l = ans, r = ans;
        for (int i = 0; i < n + 1; i ++) r = r.next;
        while (r != null) {
            l = l.next; r = r.next;
        }
        l.next = l.next.next;  // 删除操作
        return ans.next;
    }
}

20. 有效的括号

模拟
用一个栈维护当前存在的左括号
若 s.length() 为奇数则不可能匹配，否则遍历 s
当前字符为左括号：直接进栈
当前字符为右括号：若栈为空或栈顶不匹配直接返回 false，否则弹出栈顶
最后判断栈是否为空，若不为空说明还有剩余的左未匹配，返回 false

class Solution {
    public boolean isValid(String s) {
        if ((s.length() & 1) == 1) return false;
        Stack<Character> st = new Stack<>();
        for (char p : s.toCharArray()) {
            if (p == '(') st.push(')');
            else if (p == '[') st.push(']');
            else if (p == '{') st.push('}');
            else {
                if (st.isEmpty()) return false;
                if (p == ')' || p == ']' || p == '}') {
                    if (st.peek() == p) st.pop();
                    else return false;
                }
            }
        }
        return st.isEmpty();
    }
}

21. 合并两个有序链表

模拟
比较节点的值，较小的尾插
有剩余的全部合并

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode();
        ListNode st = ans;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                st.next = list1;
                list1 = list1.next;
            } else {
                st.next = list2;
                list2 = list2.next;
            }
            st = st.next;
        }
        st.next = list1 != null ? list1 : list2;

        return ans.next;
    }
}

22. 括号生成

DFS
递归的每一层视作添加的括号类型
由于必须保证括号匹配，则必须满足起始括号为 (
添加 ( 的数量 l 必须满足 l < n，添加 ) 的数量 r 必须满足 r < l

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        dfs(ans, "", 0, 0, n);
        return ans;
    }

    private void dfs(List<String> ans, String current, int l, int r, int n) {
        // 满足长度返回
        if (l + r == n * 2) {
            ans.add(current);
            return;
        }
        if (l < n) dfs(ans, current + "(", l + 1, r, n);
        if (r < l) dfs(ans, current + ")", l, r + 1, n);
    }
}

23. 合并 K 个升序链表

模拟
循环枚举链表数组里的链表，一一合并，时间复杂度 $\mathcal{O}(nk^2)$
特判，当 lists.length == 0 时返回 null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        // 全部合并到 lists[0] 上面
        ListNode ans = lists[0];
        for (int i = 1; i < n; i ++) {
            ans = mergeTwoLists(ans, lists[i]);
        }

        return ans;
    }

    // 合并两个链表
    private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode();
        ListNode st = ans;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                st.next = list1;
                list1 = list1.next;
            } else {
                st.next = list2;
                list2 = list2.next;
            }
            st = st.next;
        }
        st.next = list1 != null ? list1 : list2;
        return ans.next;
    }
}

优化：

归并
用两两归并代替循环合并，时间复杂度 $\mathcal{O}(nk \log_2^k)$
每一轮的合并中，从第一个链表开始，将它与它后面的第 cnt 个链表合并，然后将合并结果存储在第一个链表的位置上。
然后继续从第一个链表开始，将它与它后面的第 2 * cnt 个链表合并，再将合并结果存储在第一个链表的位置上。
以此类推，直到所有链表都被合并即 cnt >= n 为止。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        // 合并步长，每一轮合并后 cnt *= 2;
        int cnt = 1;
        while (cnt < n) {
            // 两两合并
            for (int i = 0; i + cnt < n; i += cnt * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + cnt]);
            }
            cnt *= 2;
        }
        // 最终全部合并到 lists[0]
        return lists[0];
    }

    private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode();
        ListNode st = ans;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                st.next = list1;
                list1 = list1.next;
            } else {
                st.next = list2;
                list2 = list2.next;
            }
            st = st.next;
        }
        st.next = list1 != null ? list1 : list2;
        return ans.next;
    }
}

24. 两两交换链表中的节点

模拟
用一个 ListNode t 指向当前要交换的节点对中的左节点（下一次交换的前一个节点）
则每次交换过程中，左右节点分别为 l = t.next, r = t.next.next
先用 t 指向 r，再用 l 指向 r 指向的节点完成 l 替换 r
再让 r 指向 l 完成 r 替换 l
最后 t 指向 l，即下一次交换的前一个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode ans = new ListNode();
        ans.next = head;
        ListNode t = ans;
        while (t.next != null && t.next.next != null) {
            ListNode l = t.next;       // t -> l -> r -> k -> ...
            ListNode r = t.next.next;
            t.next = r;                // t -> r
            l.next = r.next;           // l -> k
            r.next = l;                // r -> l
            t = l;                     // r -> l(t) -> k -> ...
        }
        return ans.next;
    }
}

25. K 个一组翻转链表

模拟
本质上就是修改链表节点指向
即，每组的第一个节点指向本组最后节点指向的节点
然后每组第一个节点后的节点依次指向前节点

如图：

k = 3
node1 -> node2 -> node3 -> node4 -> null
node1 -> node4
node2 -> node1
node3 -> node2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode ans = new ListNode();
        ans.next = head;
        ListNode t = ans;
        ListNode st = findNode(t, k);
        while (t.next != null && st.next != null) {
            ListNode l = t.next;
            ListNode r = st.next;
            // 修改节点指向
            for (int i = 0; i < k; i++) {
                ListNode temp = l.next;
                l.next = r;  // 每组第一个节点指向本组最后的节点指向的节点
                r = l;
                l = temp;
            }
            // 为下一次循环做准备
            ListNode temp = t.next;
            t.next = r;
            temp.next = l;
            t = temp;
            st = findNode(t, k);
        }
        return ans.next;
    }

    // 找到每组最后一个节点
    private ListNode findNode(ListNode t, int k) {
        k --;
        while (k-- > 0) {
            if (t.next != null) t = t.next;
            else break;
        }
        return t;
    }
}

26. 删除有序数组中的重复项

模拟
由于数组单调且元素唯一，显然有 nums[i] < nums[i + 1]
设 idx 为去重后数组的下标，flag 当前维护的值
若 flag < nums[i] 说明元素不重复，则修改 nums[idx ++] = nums[i] 即可

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int idx = 0, flag = Integer.MIN_VALUE;
        for (int i = 0; i < n; i ++) {
            if (flag < nums[i]) {
                flag = nums[i];  // 更新 flag
                nums[idx ++] = nums[i];
            }
        }
        return idx;
    }
}

27. 移除元素

模拟
设 idx 为去重后的数组下标
若 nums[i] == val 直接跳过
否则直接修改 nums[idx ++] = nums[i] 即可

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int idx = 0;
        for (int i = 0; i < n; i ++) {
            if (nums[i] == val) continue;
            nums[idx ++] = nums[i];
        }
        return idx;
    }
}

28. 找出字符串中第一个匹配项的下标

AC自动机
这道题非常的难啊！
既然出题人本意不想让我们循环暴力、直接调库或者KMP这种简单的算法
那我们只好按出题人的意思来了，直接祭大招好了😅😅😅

class Solution {
    class Node {
        Node[] children; // 子节点数组
        Node fail; // 失败指针
        List<Integer> indices; // 匹配成功的模式串在原字符串中的起始位置列表

        public Node() {
            children = new Node[26]; // 26个英文字母
            fail = null;
            indices = new ArrayList<>();
        }
    }

    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }

        Node root = buildTrie(needle); // 构建Trie树
        buildFailure(root); // 构建失败指针

        Node curr = root;
        for (int i = 0; i < haystack.length(); i++) {
            char c = haystack.charAt(i);
            curr = getNextState(curr, c); // 获取下一个状态
            if (curr.indices.size() > 0) { // 匹配成功，返回模式串在原字符串中的起始位置
                return i - needle.length() + 1;
            }
        }

        return -1; // 未找到匹配的模式串
    }

    private Node buildTrie(String needle) {
        Node root = new Node();
        Node curr = root;

        for (int i = 0; i < needle.length(); i++) {
            char c = needle.charAt(i);
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new Node();
            }
            curr = curr.children[c - 'a'];
        }

        curr.indices.add(0); // 将模式串的起始位置添加到当前节点的起始位置列表中

        return root;
    }

    private void buildFailure(Node root) {
        Queue<Node> queue = new LinkedList<>();

        for (int i = 0; i < 26; i++) { // 初始化根节点的子节点的失败指针
            if (root.children[i] != null) {
                root.children[i].fail = root;
                queue.offer(root.children[i]);
            } else {
                root.children[i] = root;
            }
        }

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            for (int i = 0; i < 26; i++) {
                if (curr.children[i] != null) {
                    Node child = curr.children[i];
                    Node fail = curr.fail;
                    while (fail != null && fail.children[i] == null) { // 失败指针回溯
                        fail = fail.fail;
                    }
                    child.fail = fail != null ? fail.children[i] : root; // 更新失败指针
                    child.indices.addAll(child.fail.indices); // 将失败指针节点的起始位置列表合并到当前节点
                    queue.offer(child);
                }
            }
        }
    }

    private Node getNextState(Node curr, char c) {
        while (curr != null && curr.children[c - 'a'] == null) { // 失败指针回溯
            curr = curr.fail;
        }
        if (curr == null) {
            return curr;
        } else {
            return curr.children[c - 'a'];
        }
    }
}

29. 两数相除

位运算
特殊情况：被除数 a 等于Integer.MIN_VALUE 且除数 b 等于 $-1$ 时结果会溢出，直接返回 Integer.MAX_VALUE。
从第 $31$ 位开始逐位检查被除数 a 是否大于等于 b 的左移结果 (b << i)。
如果被除数大于等于 (b << i)，则执行以下操作：
- 将被除数 a 减去 (b << i)，相当于从被除数中减去当前位的除数。
- 检查结果变量 res 是否大于Integer.MAX_VALUE - (1 << i)，如果是，则结果溢出，直接返回 Integer.MIN_VALUE。
- 将结果变量 res 加上 1 << i，相当于将当前位的商加到结果中。
循环结束后，返回结果变量 res。

class Solution {
    public int divide(int a, int b) {
        if (a == 0) return 0;
        if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
        boolean flag = (a > 0) ^ (b > 0);  // 判断符号是否相同，用于确定符号
        a = Math.abs(a); b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            if ((a >>> i) - b >= 0) { // a >= (b << i)
                a -= (b << i);
                if (res > Integer.MAX_VALUE - (1 << i)) {
                    return Integer.MIN_VALUE;
                }
                res += (1 << i);
            }
        }
        return flag ? -res : res;
    }
}

30. 串联所有单词的子串

滑窗
用 StringBuilder 模拟窗口
当窗口长度 sb.length() == words.length * words[0].length() 需要判断是否满足
用 HashMap<String, Integer> 统计 words 里面的单词及其词频
然后依次截取 sb 长度为 words[0].length() 的片段，判断是否存在且频数照应
若满足条件，将下标加入答案中

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int len = words.length * words[0].length();  // 计算目标子串的长度
        int n = s.length();
        StringBuilder sb = new StringBuilder();  // 用于存储当前窗口的子串
        List<Integer> ans = new ArrayList<>();
        HashMap<String, Integer> vis = new HashMap<>();  // 存储目标子串中每个单词的出现次数
        for (int i = 0; i < words.length; i++) {
            vis.put(words[i], vis.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < n; i ++) {
            if (sb.length() == len)  sb.deleteCharAt(0);  // 长度足够，删除最左侧的字符
            sb.append(s.charAt(i));                       // 将当前字符添加到窗口的子串中
            if (sb.length() == len) {
                HashMap<String, Integer> sbwords = new HashMap<>(vis);
                // 检查当前窗口的子串是否符合要求
                if (check(sb.toString(), sbwords, words[0].length())) ans.add(i - len + 1);
            }
        }
        return ans;
    }

    private static boolean check(String sb, HashMap<String, Integer> sbwords, int cnt) {
        // 以单词长度为步长，遍历当前窗口的子串
        for (int i = 0; i < sb.length(); i += cnt) {  
            String res = sb.substring(i, i + cnt);
            // 如果目标子串中包含当前单词
            if (sbwords.containsKey(res)) {
                int t = sbwords.get(res);
                if (t > 0) sbwords.put(res, t - 1);
                else return false;
            } 
            else return false;
        }
        return true;
    }
}

STATISTICS

1. 两数之和

2. 两数相加

3. 无重复字符的最长子串

4. 寻找两个正序数组的中位数

5. 最长回文子串

6. N 字形变换

7. 整数反转

8. 字符串转换整数 (atoi)

9. 回文数

10. 正则表达式匹配

11. 盛最多水的容器

12. 整数转罗马数字

13. 罗马数字转整数

14. 最长公共前缀

15. 三数之和

16. 最接近的三数之和

17. 电话号码的字母组合

18. 四数之和

19. 删除链表的倒数第 N 个结点

20. 有效的括号

21. 合并两个有序链表

22. 括号生成

23. 合并 K 个升序链表

24. 两两交换链表中的节点

25. K 个一组翻转链表

26. 删除有序数组中的重复项

27. 移除元素

28. 找出字符串中第一个匹配项的下标

29. 两数相除

30. 串联所有单词的子串

发送评论编辑评论

发送评论 编辑评论

推荐文章

发送评论编辑评论