Hot100-Java

数组

T14. 除自身以外数组的乘积

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

如果是遍历每个数，令每个数在每个位置上相乘，则时间复杂度为 $O(n^2)$，不满足题意

使用 lmul 和 rmul 记录：当前这个数左侧所有数的乘积与当前这个数右侧所有数的乘积，就能使用 lmul[i]*rmul[i] 得到对应位置的乘积

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] lmul = new int[n], rmul = new int[n];
        lmul[0] = 1;
        rmul[n - 1] = 1;
        for (int i = 1; i < n; i++) {
            lmul[i] = lmul[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            rmul[i] = rmul[i + 1] * nums[i + 1];
        }

        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = lmul[i] * rmul[i];
        }
        return ret;
    }
}

T16. 乘积最大子数组

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

• f[i]
  • 表示以第 $i$ 个元素为结尾，得到的子数组的所有组合
  • 乘积 max
• 计算：选取前一段加上自己，或者以自己为新的子数组
  • 如果当前位置是负数，希望以它前一个位置为结尾的某段子数组的积，也能为负数，且绝对值尽可能得大（即数值尽可能小）
  • 如果当前位置为正数，则希望以它前一个位置为结尾的某段子数组的积，也能为正数，且尽可能得大
  • 所以维护两个数组 fmax 和 fmin（但是只需要上一个位置的数据，可以优化为各自使用一个变量记录，再使用 ret 记录全局最大值）

public class Solution {
    public int maxProduct(int[] nums) {
        int positive = Math.max(nums[0], 0);
        int negative = Math.min(nums[0], 0);
        int ret = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num > 0) {
                positive = Math.max(positive * num, num);   // 主要考虑positive原先可能是0
                negative = Math.min(negative * num, 0);
            } else {
                // 交换正负
                int tmp = positive;
                positive = Math.max(negative * num, 0);
                negative = Math.min(tmp * num, num);
            }
            ret = Math.max(positive, ret);
        }

        return ret;
    }
}

T23. 回文子串

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

中心扩展：选取中心点，使用两个指针向两侧扩展，判断是否仍然为回文串

需要考虑中心长度为 1 或长度为 2，对应奇数长度的回文串和偶数长度的回文串

public class Solution {
    public int countSubstrings(String s) {
        int ret = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int len = 0; i + len < n && i - len >= 0; len++) {
                if (s.charAt(i + len) == s.charAt(i - len)) {
                    ret++;
                } else {
                    break;
                }
            }
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                continue;
            }
            for (int len = 0; i - len >= 0 && i + len + 1 < n; len++) {
                if (s.charAt(i - len) == s.charAt(i + len + 1)) {
                    ret++;
                } else {
                    break;
                }
            }
        }

        return ret;
    }
}

T29. 找到所有数组中消失的数字

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

do it without extra space and in O(n) runtime

1. 哈希表映射，但是需要 $O(n)$ 的空间复杂度
2. 鸽笼原理：当数 $x$ 出现时，对 nums[x-1] 进行标记

标记方式有 2 种：

1. +n，这样子可以通过取模 %n 来恢复数字，但是要注意溢出问题
2. 转为负数，可以不改变数组信息，通过正负号来判断元素是否出现过，要注意出现大于 2 次的情况，应该是要取绝对值的负数：nums[x-1] = -abs(nums[abs(x)-1])

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> ret = new ArrayList<>();
        if (n == 1) {
            return ret;
        }

        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            nums[num - 1] = -Math.abs(nums[num - 1]);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                ret.add(i + 1);
            }
        }
        return ret;
    }
}

T30. 找到字符串中所有字符的异位词

Given two strings s and p, return an array of all the start indices of p ‘s anagrams in s. You may return the answer in any order.

滑动窗口。比较统计数组是否一致即可

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length(), m = p.length();
        List<Integer> ret = new ArrayList<>();
        if (n < m) {
            return ret;
        }
        int[] sMap = new int[26], pMap = new int[26];
        for (int i = 0; i < m; i++) {
            sMap[s.charAt(i) - 'a']++;
            pMap[p.charAt(i) - 'a']++;
        }
        if (equalsCharMap(sMap, pMap)) {
            ret.add(0);
        }

        for (int i = m; i < n; i++) {
            sMap[s.charAt(i - m) - 'a']--;
            sMap[s.charAt(i) - 'a']++;
            if (equalsCharMap(sMap, pMap)) {
                ret.add(i - m + 1);
            }
        }
        return ret;
    }

    private boolean equalsCharMap(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }
}

T39. 买卖股票的最佳时机

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

维护一个最小值，一直更新最大获利

public class Solution {
    public int maxProfit(int[] prices) {
        int min = 0x3f3f3f3f, res = 0;
        for (Integer i : prices) {
            res = Math.max(res, i - min);
            min = Math.min(min, i);
        }
        return res;
    }
}

T53. 旋转图像

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

![[images/Pasted image 20251209142702.png]]

• 使用一个一维临时数组存储一组，一行元素转一圈
• 或者是只用一个临时变量存储一个元素，一个元素转一圈

原理相同

旋转元素时，需要考虑坐标如何变化：

• Top to Right: $(x,y)\rightarrow(y,n-1-x)$
• Right to Bottom: $(x,y)\rightarrow(y,n-1-x)$

发现无论元素位置如何，坐标变化规律均为：

$$
(x,y)\rightarrow(y,n-1-x)
$$

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 对于单个元素旋转，每次都能使4个元素归位
        // 以反对角线为界，只需要遍历每一层的顶部，直到反对角线即可
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                rotateOne(matrix, i, j);
            }
        }
    }

    private void rotateOne(int[][] matrix, int x, int y) {
        // 考虑顺时针旋转时，4个元素的坐标变化
        int n = matrix.length;
        int update = matrix[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = y, ny = n - 1 - x;
            int tmp = matrix[nx][ny];
            matrix[nx][ny] = update;
            update = tmp;
            x = nx;
            y = ny;
        }
    }
}

T60. 下一个排列

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

The replacement must be in place and use only constant extra memory.

两遍扫描：

核心需求：下一个序列总是比当前的序列大（除非已经是最大排列）；希望能找到一种方法：使能找到一个大于当前序列的新序列，且变大的幅度尽可能小

思路：

• 找到更大序列：将左边的一个较小数与右边的一个较大数交换
• 变大的幅度尽可能小：较小数尽可能靠右，较大数尽可能小；交换完成后，较大数右侧数需要按升序重新排序

具体实现：

1. 从后向前查找第一个顺序对 $(s,s+1)$，使得有 $nums[s]<nums[s+1]$，此时区间 $[s+1,n)$ 为降序。$nums[s]$ 即为较小数
2. 如果找到了上述顺序对，则在区间 $[s+1,n)$ 中从后向前，查找到第一个元素 $g$ 使得 $nums[s]<nums[g]$。$nums[g]$ 即为较大数
3. 交换 $nums[s]$ 和 $nums[g]$，可以证明区间 $[s+1,n)$ 必为降序；将该区间反转变为升序

如果在步骤 1 找不到顺序对，说明当前序列已经是一个降序序列，即最大的序列，直接跳过步骤 2 执行步骤 3，即可得到最小的升序序列。

public class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return;
        }
        // 找到较小数
        int s = n;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                s = i;
                break;
            }
        }
        // 已经是最大序列
        if (s == n) {
            sortDesc(nums, 0, n - 1);
            return;
        }

        // 找到较大数
        int g = n - 1;
        for (int i = n - 1; i > s; i--) {
            if (nums[s] < nums[i]) {
                g = i;
                break;
            }
        }
        swap(nums, s, g);
        sortDesc(nums, s + 1, n - 1);
    }

    // 对降序序列进行排序
    private void sortDesc(int[] nums, int l, int r) {
        while (l < r) {
            swap(nums, l, r);
            l++;
            r--;
        }
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}

T71. 最长回文子串

Given a string s, return the longest palindromic substring in s.

方法同 T23. 回文子串，在其基础上记录最长子串即可

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int maxL = 1;
        int st = 0, ed = 0;
        for (int i = 0; i < n; i++) {
            int curL = 1;
            for (int j = 0; i - j >= 0 && i + j < n; j++) {
                if (s.charAt(i - j) != s.charAt(i + j)) {
                    break;
                }
                curL += 2;
                if (curL > maxL) {
                    maxL = curL;
                    st = i - j;
                    ed = i + j;
                }

            }
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                continue;
            }
            int curL = 2;
            for (int j = 0; i - j >= 0 && i + 1 + j < n; j++) {
                if (s.charAt(i - j) != s.charAt(i + 1 + j)) {
                    break;
                }
                curL += 2;
                if (curL > maxL) {
                    maxL = curL;
                    st = i - j;
                    ed = i + 1 + j;
                }
            }
        }
        return s.substring(st, ed + 1);
    }
}

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

Given a string s, find the length of the longest substring without duplicate characters.

滑动窗口思想

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        Set<Character> exist = new HashSet<>();
        int ret = 0;
        int st = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            while (exist.contains(c)) {
                exist.remove(s.charAt(st));
                st++;
            }
            exist.add(c);
            ret = Math.max(ret, i - st + 1);
        }
        return ret;
    }
}

T91. 最小覆盖子串

Given two strings s and t of lengths m and n respectively, return *the minimum window* substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

滑动窗口思想

• words 记录出现的字符次数
• cnt 记录出现的字符种数

当出现字符种数一致时，再判断 words 中字符的出现次数是否对应

public class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        if (n < m) {
            return "";
        }
        int[] words = new int[52];
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            int idx = mapping(t.charAt(i));
            if (words[idx] == 0) {
                cnt++;
            }
            words[idx]++;
        }

        int ncnt = 0;
        int st = 0, ed = n;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            int idx = mapping(s.charAt(i));
            words[idx]--;
            if (words[idx] == 0) {
                ncnt++;
            }

            while (cnt == ncnt) {
                if (i - cur < ed - st) {
                    st = cur;
                    ed = i;
                }
                int rmv = mapping(s.charAt(cur));
                words[rmv]++;
                if (words[rmv] > 0) {
                    ncnt--;
                }
                cur++;
            }
        }
        return ed == n ? "" : s.substring(st, ed + 1);
    }

    private int mapping(char c) {
        if ('a' <= c && c <= 'z') {
            return c - 'a' + 26;
        }
        return c - 'A';
    }
}

T99. 跳跃游戏

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

维护一个最远能到达的位置，判断能否再向前即可。

public class Solution {
    public boolean canJump(int[] nums) {
        int longest = 0, n = nums.length;
        for (int i = 0; i <= longest && i < n; i++) {
            longest = Math.max(longest, i + nums[i]);
        }
        return longest >= n - 1;
    }
}

双指针

T46. 移动零

Given an integer array nums, move all 0 ‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

双指针，先将非零元素移动到数组开头，然后将后面的多余位置置零。

public class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0, n = nums.length;
        for (int fast = 0; fast < n; fast++) {
            if (nums[fast] == 0) {
                continue;
            }
            nums[slow] = nums[fast];
            slow++;
        }
        for (int i = slow; i < n; i++) {
            nums[i] = 0;
        }
    }
}

T68. 三数之和

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

由于结果是 (nums[i], nums[j], nums[k]) 的形式，与实际的 $i,j,k$ 无关，所以可以直接先进行排序，$i$ 跳过重复的值，从而实现去重

• 暴力实现：三重循环：$O(n^3)$
• 两数之和优化：遍历 $i$，对于 $j$ 和 $k$ 做两数之和解：$O(n^3)$

但是由于排序了，必然有 $nums[i]\leq nums[j] \leq nums[k]$，当固定了 $i$ 时，只需要让 $nums[j] + nums[k] = -nums[i]$。可以使用双指针：

• 当小于 $-nums[i]$ 时，左指针右移
• 当大于 $-nums[i]$ 时，右指针左移

而且当 $nums[i] > 0$ 时，一定不存在解，所以可以直接舍去；还需要注意不仅要对 $i$ 去重，对于 $j,k$ 也要去重

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            } else if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int j = i + 1, k = n - 1;
            int target = -nums[i];
            while (j < k) {
                int sum = nums[j] + nums[k];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    // skip duplicate items
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return res;
    }
}

T69. 盛最多水的容器

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

![[images/Pasted image 20260301103947.png]]

解法一：遍历每根柱子，对于每根柱子，以该柱子为容器的一边，则：

• 向右遍历其他柱子，则可以确定由当前两根柱子所构成的容器容量
• 时间复杂度为：$O(N^2)$

解法二：双指针，每次移动高度更小的一侧指针

• 记两侧指针分别为 l 和 r，此时所能容纳的水量为：$\min(height[l],height[r])\times(r-l)$
• 不失一般性，假设 height[l] < height[r]，此时所能容纳的水量为：$height[l]\times(r-l)$
• 如果移动 r，height[r-1] 对于 height[r] 的大小存在两种关系：
  • height[r-1] > height[r]：容量仍受到 height[l] 的限制，此时所能容纳的水量为：$height[l]\times(r-l)$
  • height[r-1] <= height[r]，则有 $\min(height[l],height[r-1])\leq\min(height[l],height[r])$ 和 $(r-1-l)<(r-l)$，所以容量 $\min(height[l],height[r-1])\times(r-1-l)\leq\min(height[l],height[r])\times(r-l)$ 必然成立
• 因此如果移动高度更大一侧的指针，必定无法获得更优解
• 所以需要移动高度更小的一侧指针

public class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ret = 0;
        while (l < r) {
            ret = Math.max(ret, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ret;
    }
}

T92. 颜色分类

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

• 可以直接统计每个数字出现几次，直接覆盖
• 或者：由于只有 3 种数字，所以可以把 0 全部移到开头，把 2 全部移到末尾，这样剩下来的 1 就会恰好填满中间。可以使用双指针实现（实际上是三指针，不过底层还是两个双指针）

public class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int start = 0, end = n - 1;
        for (int i = start; i <= end; i++) {
            if (nums[i] == 0) {
                swap(nums, start, i);
                // 因为是从左往右遍历，所以出现2时一定会移到末尾，因此移动后i不用停留
                start++;
            } else if (nums[i] == 2) {
                swap(nums, end, i);
                end--;
                // 因为末尾元素不确定，所以还需要再判断当前位置
                i--;
            }
        }
    }

    private void swap(int[] nums, int x, int y) {
        if (x == y) {
            return;
        }
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}

二分

T45. 寻找重复数

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

不满足条件，但可以实现的方法：

• 如果使用 $O(n)$ 空间复杂度，使用哈希表可以轻松完成
• 使用 $O(1)$ 空间复杂度，可以考虑在对应 index 的数据改为负数，但是要求不修改原数组

满足条件的方法：

• 二分：
  • 定义 cnt[i] 表示数组中小于等于 $i$ 的数的数量
  • 假设重复的数为 target，则 $[1,target-1]$ 里所有的数满足 $cnt[i]\leq i$；在 $[target,n]$ 范围内所有数满足 $cnt[i]>i$，具有二分性
• 在统计 cnt 时，可以使用前缀和优化
• 也可以直接遍历，找到发生属性变化的位置即可

public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length - 1;
        int[] cnt = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            cnt[nums[i]]++;
        }
        for (int i = 1; i <= n; i++) {
            cnt[i] += cnt[i - 1];
        }

        int left = 1, right = n;
        while (left < right) {
            int mid = left + right >> 1;
            if (cnt[mid] > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

T49. 搜索二维矩阵 II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

• 对每一列进行二分

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        for (int[] mtx : matrix) {
            int left = 0, right = m - 1;
            while (left <= right) {
                int mid = left + right >> 1;
                int num = mtx[mid];
                if (target == num) {
                    return true;
                } else if (target < num) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}

T57. 在排序数组中查找元素的第一个和最后一个位置

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

两次二分，找最左和最右即可，注意处理没有找到的情况

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        // find left
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        int first = left;

        // find right
        left = 0;
        right = nums.length - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        int last = left;

        if (nums[first] != target) {
            return new int[]{-1, -1};
        }
        return new int[]{first, last};
    }
}

T58. 搜索旋转排序数组

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums , or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

难点在于不确定的 $k$ 旋转，如果使用 $O(n)$ 解法，可以直接复原数组。但是要求使用 $O(\log n)$，需要从二分来考虑

• 只有在顺序区间内才可以通过区间两端的数值判断 target 是否在其中
• 判断顺序区间还是乱序区间，只需要对比 left 和 right 是否是顺序对即可，left <= right，顺序区间，否则乱序区间
• 每次二分都会至少存在一个顺序区间

每次都会是两种情况其一

![[images/Pasted image 20251213145944.png]]

public class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            int x = nums[mid];
            if (x == target) {
                return mid;
            }
            // 判断左右哪边有序
            if (x < nums[l]) {
                // 右半边有序
                if (target < x) {
                    r = mid - 1;
                } else if (target <= nums[r]) {
                    l = mid + 1;
                } else {
                    // target > nums[r]
                    r = mid - 1;
                }
            } else {
                // 左半边有序
                if (target > x) {
                    l = mid + 1;
                } else if (target >= nums[l]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }

        return -1;
    }
}

前缀和

T31. 路径总和 III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

回溯

根据当前节点选择开闭，进行回溯。需要注意，节点必须连续选取，所以使用一个 flag 标记上一个节点是否有被选择

public class Solution {
    private int ret;

    public int pathSum(TreeNode root, int targetSum) {
        ret = 0;
        dfs(root, targetSum, false);
        return ret;
    }

    private void dfs(TreeNode root, long target, boolean flag) {
        if (root == null) {
            return;
        }
        if (root.val == target) {
            ret++;
        }

        if (!flag) {
            // 上一个结点没有被选取，所以可以重从子结点新开始选
            dfs(root.left, target, false);
            dfs(root.right, target, false);
        }
        // 选取当前结点
        dfs(root.left, target - root.val, true);
        dfs(root.right, target - root.val, true);
    }
}

前缀和

上面的方式中，会有很多重复计算。

定义前缀和为：从根节点出发，到当前节点的路径上所有节点的和

• 前序遍历二叉树，记录根节点 root 到当前节点 p 的路径上，除当前节点以外所有节点的前缀和
• 在已保存的路径前缀和中查找：是否存在前缀和，刚好等于当前节点到根节点的前缀和 curr 减去 targetSum

T63. 和为 K 的子数组

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

子数组为连续的部分原数组，因此计算子数组的总和时，可以使用前缀和

• 使用 p[i] 表示 nums[0]+nums[1]+...+nums[i]
• 则 p[i+1]=p[i]+nums[i+1]
• 对于从 [i,j] 的子数组，p[j]-p[i-1] 即为子数组元素总和，判断 p[j]-p[i-1] == k 是否成立即可

在遍历时需要确保 i<j 的成立，可以通过从左到右遍历元素来实现；通过哈希表快速定位，同时因为有哈希表进行记录，也不需要额外空间存储前缀和，直接使用变量 preSum 来进行记录

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            preSum += nums[i];
            if (map.containsKey(preSum - k)) {
                ret += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return ret;
    }
}

链表

T1. 相交链表

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

• 每步操作需要同时更新指针 pA 和 pB。
• 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
• 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
• 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        while (pa != pb) {
            if (pa == null) {
                pa = headB;
            } else {
                pa = pa.next;
            }
            if (pb == null) {
                pb = headA;
            } else {
                pb = pb.next;
            }
        }
        return pa;
    }
}

T3. 回文链表

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

1. 直接遍历链表，将元素提取到数组中再判断回文
2. 快慢指针，慢指针遍历到中间结点，快指针遍历到末尾结点，反转一半链表，然后遍历两条链表判断是否相同 3. 从工程角度来说要恢复这个链表，但从做题角度直接返回结果就好

func isPalindrome(head *ListNode) bool {
    slow, fast := head, head.Next
    // 快指针走到 nil 时停止: 奇数个节点
    // 快指针走到最后一个节点停止: 偶数个节点
    for fast != nil && fast.Next != nil {
        // 慢指针一次走一步
        slow = slow.Next
        // 快指针一次走两步
        fast = fast.Next.Next
    }
    // 将链表以 slow 为分界线，将 slow 之后的进行反转
    l1 := head
    l2 := reverseList(slow.Next)
    // l2 长度小于等于 l1，但是最多只会少 1 个中间字符，不影响结果
    for l2 != nil {
        if l1.Val != l2.Val {
            return false
        }
        l1 = l1.Next
        l2 = l2.Next
    }
    return true
}

// 反转链表
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    // 如果 head == nil，返回的也是 nil
    return prev
}

T10. 反转链表

Given the head of a singly linked list, reverse the list, and return the reversed list.

顺序反转

1. 设 3 个结点：prev / cur / next，整体向后移动
2. next = cur.Next
3. cur.Next = prev
4. prev = cur
5. cur = next

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

递归反转

假设链表为：

$$
n_{1} \rightarrow \dots \rightarrow n_{k} \rightarrow n_{k+1} \rightarrow \dots \rightarrow n_{m}
$$

若从结点 $n_{k+1}$ 到 $n_{m}$ 已经被反转，当前处于 $n_{k}$

$$
n_{1} \rightarrow \dots \rightarrow n_{k} \rightarrow n_{k+1} \leftarrow \dots \leftarrow n_{m}
$$

希望 $n_{k+1}$ 的下一个节点指向 $n_{k}$

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 递归，一直先遍历到链表尾部，返回的是反转后的新头结点
        ListNode newHead = reverseList(head.next);
        // 将当前节点接入到链尾之后
        head.next.next = head;
        // 同时删去当前节点的指针，避免形成环
        head.next = null;
        // 返回新头结点(最开始的尾结点)
        return newHead;
    }
}

T18. LRU 缓存

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

哈希表+双向链表

• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的
  • 用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限
• 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置

对于 get 操作，首先判断 key 是否存在：

• 如果 key 不存在，则返回 −1；
• 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
  对于 put 操作，首先判断 key 是否存在：
• 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
• 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

public class LRUCache {
    private static class Node {
        public int key, val;
        public Node prev, next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private final Map<Integer, Node> map;
    private final Node head, tail;
    private final int capacity;


    public LRUCache(int capacity) {
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeFromList(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeFromTail() {
        removeFromList(tail.prev);
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 获取
        Node node = map.get(key);
        // 移动到队列头部
        removeFromList(node);
        addToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            removeFromList(node);
            addToHead(node);
            return;
        }

        Node node = new Node(key, value);
        map.put(key, node);
        addToHead(node);
        if (map.size() > capacity) {
            Node removeNode = tail.prev;
            removeFromTail();
            map.remove(removeNode.key);
        }
    }
}

T19. 环形链表 II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle.

Note that pos is not passed as a parameter.

Do not modify the linked list.

1. 哈希表，存储遍历过的指针即可
2. 快慢指针

判断是否有环

1. 使用双指针，快指针以快的速度移动（两个结点），慢指针以慢的速度移动（一个结点），如果快慢指针相遇，则存在环（因为快指针陷入环里了）
2. 有环则一定相遇证明：两个指针都进入环中时，相当于快指针以一个结点每步的速度追逐慢指针，两者距离是逐个结点递减的，所以必定会相遇

寻找入口

1. 假设在环中两个指针相遇了，设头结点到入口结点距离为 x ​，入口结点到相遇结点距离为 y ​，相遇结点沿着环再回到入口结点距离为 z ​
2. 根据快指针每次走 2 步，慢指针每次走 1 步，可以得到：
   • ​ slow = x + y ​ 慢指针一定在第一圈就会被快指针追上
   • fast = x + y + n * (y + z) ​ n 为快指针转的圈数
   • 2 * slow = fast ​

=> x = n * (y + z) - y ​ (n >= 1) 因为是快指针追逐慢指针的过程，所以快指针一定在环中转至少一圈

=> x = (n - 1) * (y + z) + z ​

即头结点到入口的距离，就是 (n - 1) 个环的长度 + 相遇结点回到入口结点的距离：从相遇点出发，沿环走 z 步，再绕 n-1 圈，能到达环入口；同时取一个新节点从 head 出发，也走同样的步数，也恰好能到达环入口（和另一节点重合）

所以两个节点同时减去绕环走的部分，即只需要第一次相遇，就是环的入口！

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode ret = head;
                while (ret != slow) {
                    ret = ret.next;
                    slow = slow.next;
                }
                return ret;
            }
        }
        return null;
    }
}

T20. 环形链表

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

上一题的子问题，双指针判断即可

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

T64. 合并两个有序链表

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

双指针合并

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead, tmp;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tmp = list1;
                list1 = list1.next;
            } else {
                tmp = list2;
                list2 = list2.next;
            }
            cur.next = tmp;
            cur = cur.next;
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return dummyHead.next;
    }
}

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

Given the head of a linked list, remove the nth node from the end of the list and return its head.

双指针，让快指针提前 n 个结点到达结尾，就能获取到倒数第 N 个结点

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode slow = dummyHead, fast = dummyHead;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;
        return dummyHead.next;
    }
}

T75. 两数相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

即大整数相加的链表形式

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode();
        ListNode prev = dummyHead;
        int t = 0;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            prev.next = new ListNode(t % 10, null);
            prev = prev.next;
            t /= 10;
        }
        if (t > 0) {
            prev.next = new ListNode(1, null);
        }
        return dummyHead.next;
    }
}

哈希表

T24. 最长连续序列

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

1. 排序
2. 哈希表：想办法不重复遍历：遍历元素时，判断 num-1 是否存在，如果存在，则说明当前元素为“中间元素”，需要遍历的只有“开始元素”，即每一段连续序列的最小值。

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }

        int ret = 0;
        for (Integer each : set) {
            if (set.contains(each - 1)) {
                continue;
            }
            int curLength = 1;
            int curNumber = each + 1;
            while (set.contains(curNumber)) {
                curLength++;
                curNumber++;
            }
            ret = Math.max(ret, curLength);
        }

        return ret;
    }
}

T52. 字母异位词分组

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

其实就是将每个单词映射到同一组，可以统计出现字符次数，构造新的字符串；也可以直接排序，只要保证同一组的字符串在经过操作之后能得到相同结果即可

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String pattern = hash(str);
            if (!map.containsKey(pattern)) {
                map.put(pattern, new ArrayList<>());
            }
            map.get(pattern).add(str);
        }
        map.forEach((key, value) -> ret.add(value));
        return ret;
    }

    private String hash(String str) {
        char[] ch = str.toCharArray();
        Arrays.sort(ch);
        return new String(ch);
    }
}

T89. 两数之和

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

使用一个哈希表，记录出现过的值，每次查询是否出现过 target - nums[i] 即可（相当于将 $O(n^2)$ 的查找优化为 $O(n\log n)$）

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

栈

T4. 每日温度

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

1. 维护一个单调递减栈，从后往前遍历 temperatures，对比 top 和 temperatures[i]

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ret = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            int num = temperatures[i];
            while (!stack.isEmpty() && num >= temperatures[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                ret[i] = stack.peek() - i;
            }
            stack.push(i);
        }
        return ret;
    }
}

2. 上一种方法是从后往前遍历，将确定的元素放入栈。此方法是从前往后遍历，将未确定的元素（索引）放入单调栈，当遍历数组到比栈顶元素大（通过索引查询）的元素时，取出栈顶元素，直到栈空或栈顶元素大于等于当前元素。同时将栈压缩为数组实现

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ret = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            if (stack.isEmpty()) {
                stack.add(i);
                continue;
            }
            int num = temperatures[i];
            while (!stack.isEmpty() && num > temperatures[stack.peek()]) {
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
        }
        return ret;
    }
}

T15. 最小栈

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

某一时刻的栈的最小值，一定与最近入栈的元素有关，即元素入栈时，最小值要么不变，要么变为入栈元素的值，那只需要记录每次入栈的 pair 就好了

public class MinStack {
    private static class Node {
        int val;
        int minVal;

        public Node(int val, int minVal) {
            this.val = val;
            this.minVal = minVal;
        }
    }

    private Stack<Node> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new Node(val, val));
        } else {
            int lastMinVal = stack.peek().minVal;
            stack.push(new Node(val, Math.min(val, lastMinVal)));
        }
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek().val;
    }

    public int getMin() {
        return stack.peek().minVal;
    }
}

也可以用维护一个单调链表，入栈和出栈时进行修改

T35. 字符串解码

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

public class Solution {
    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        int num = 0;
        boolean flag = false;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                num = num * 10 + c - '0';
                flag = true;
            } else if (c == ']') {
                StringBuilder sb = new StringBuilder();
                String out;
                // 读字符
                while (!(out = stack.pop()).equals("[")) {
                    sb.append(out);
                }

                // "[" 之后的一定是数字
                out = stack.pop();
                int times = Integer.parseInt(out);
                for (int t = 0, len = sb.length(); t < times - 1; t++) {
                    sb.append(sb, 0, len);
                }
                stack.push(sb.toString());
            } else {
                if (flag) {
                    stack.push(String.valueOf(num));
                    num = 0;
                    flag = false;
                }
                stack.push(String.valueOf(c));
            }
        }

        StringBuilder ret = new StringBuilder();
        while (!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }
}

T65. 有效的括号

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

使用栈维护括号的出现，为了方便比较，可以直接将左括号处理为右括号，这样当遍历到右括号时，就能直接比较而不用另外的分支了

注意要考虑奇数个括号的情况，会存在一对括号无法匹配，但是不会走遍历，所以最后还要判断栈是否为空

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.add(')');
            } else if (c == '[') {
                stack.add(']');
            } else if (c == '{') {
                stack.add('}');
            } else {
                if (stack.isEmpty() || c != stack.pop()) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

T87. 最大矩形

Given a rows x cols binary matrix filled with 0 ‘s and 1 ‘s, find the largest rectangle containing only 1 ‘s and return its area.

![[images/f4274937-61f3-4af8-8c9a-1243bf76ecb6.png]]

实际上是 T88. 柱状图中最大矩形的进阶形式，多使用一个变量用于控制行，将二维矩阵转换为一维进行求解

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int ret = 0, m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            ret = Math.max(ret, find(i, heights));
        }
        return ret;
    }

    private int find(int row, int[] heights) {
        int ret = 0;
        int n = heights.length;
        int[] lm = new int[n], rm = new int[n];
        int[] stack = new int[n];
        int top = -1;
        for (int i = 0; i < n; i++) {
            while (top != -1 && heights[stack[top]] >= heights[i]) {
                top--;
            }
            lm[i] = top == -1 ? i : i - stack[top] - 1;
            stack[++top] = i;
        }
        top = -1;
        for (int i = n - 1; i >= 0; i--) {
            while (top != -1 && heights[stack[top]] >= heights[i]) {
                top--;
            }
            rm[i] = top == -1 ? n - 1 - i : stack[top] - i - 1;
            stack[++top] = i;
        }
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, heights[i] * (lm[i] + rm[i] + 1));
        }
        return ret;
    }
}

T88. 柱状图中最大的矩形

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

![[images/38a9e2d4-2d9c-4c6e-be8f-47345f40365f.png]]

单调队列

• 对于当前矩形高度 height[i]，尽可能的向两侧进行延伸
• 即寻找左右侧第一个小于 height[i] 的高度
• 使用单调递增队列

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] lm = new int[n], rm = new int[n];
        List<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.get(stack.size() - 1)] >= heights[i]) {
                stack.remove(stack.size() - 1);
            }
            lm[i] = stack.isEmpty() ? i : i - stack.get(stack.size() - 1) - 1;
            stack.add(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.get(stack.size() - 1)] >= heights[i]) {
                stack.remove(stack.size() - 1);
            }
            rm[i] = stack.isEmpty() ? n - 1 - i : stack.get(stack.size() - 1) - i - 1;
            stack.add(i);
        }

        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, heights[i] * (lm[i] + rm[i] + 1));
        }
        return ret;
    }
}

队列

T50. 滑动窗口最大值

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

维护一个单调递减队列（存储索引可以方便控制活动窗口大小）

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ret = new int[n - k + 1];
        // 存放index而不是数据
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 去除超出窗口的数据
            while (!q.isEmpty() && q.getFirst() < i - k + 1) {
                q.removeFirst();
            }

            // 维护单调队列
            while (!q.isEmpty() && nums[q.getLast()] < nums[i]) {
                q.removeLast();
            }
            q.addLast(i);

            // 未形成窗口
            if (i < k - 1) {
                continue;
            }
            ret[i - k + 1] = nums[q.getFirst()];
        }
        return ret;
    }
}

树

T2. 二叉树的最近公共祖先

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

1. p & q 位于同一侧，则返回最上的
2. p & q 位于两侧，返回公共父节点

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right == null) {
            return left;
        } else if (left == null && right != null) {
            return right;
        } else if (left != null && right != null) {
            return root;
        }
        return null;
    }
}

T5. 翻转二叉树

Given the root of a binary tree, invert the tree, and return its root.

对于每个结点，翻转它的左右结点，每个翻转操作都是独立的，前中后序遍历都可以，更改一下操作结点即可

后序遍历：

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

T8. 实现 Trie 前缀树

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:

• Trie () Initializes the trie object.
• void insert (String word) Inserts the string word into the trie.
• boolean search (String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith (String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

1. 将每一个字符构建成一个结点，每个结点有指向下一个结点的指针数组，并使用 cnt 标记是否为结尾结点（int 或 bool 都可，只是用于标记）
2. 若可以通过这个数组到达某一结点，则为前缀，若同时 cnt==1，则为一个完整单词

public class Trie {

    private static class Node {
        Node[] next;
        boolean isWord;

        public Node() {
            next = new Node[26];
            isWord = false;
        }
    }

    private Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                cur.next[idx] = new Node();
            }
            cur = cur.next[idx];
        }
        cur.isWord = true;
    }

    public boolean search(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                return false;
            }
            cur = cur.next[idx];
        }
        return cur.isWord;
    }

    public boolean startsWith(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i) - 'a';
            if (cur.next[idx] == null) {
                return false;
            }
            cur = cur.next[idx];
        }
        return cur != null;
    }
}

T25. 二叉树中的最大路径和

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

递归 + 后序遍历：

1. 使用全局变量检测最大值变化
2. 先遍历两个子树，计算各自经过左、右节点所能得到的最大路径和。（注意返回值并不是求得的最大路径和）
3. 然后计算经过当前节点，加上左右节点，得到当前最大路径和，更新最大值
4. 返回值应当是当前节点、当前节点加上左子树和当前节点加上右子树中的最大者，注意只能有一颗子树被加上

public class Solution {
    private int ret;

    public int maxPathSum(TreeNode root) {
        ret = Integer.MIN_VALUE;
        postorder(root);
        return ret;
    }

    private int postorder(TreeNode cur) {
        if (cur == null) {
            return 0;
        }
        int left = postorder(cur.left);
        int right = postorder(cur.right);

        int res = cur.val;
        if (left > 0) {
            res += left;
        }
        if (right > 0) {
            res += right;
        }

        ret = Math.max(ret, res);
        return Math.max(Math.max(cur.val, 0), Math.max(cur.val + left, cur.val + right));
    }
}

值得注意的是，在 Leetcode 测试时，ret 被初始化过了，必须在函数内部再赋值一次

T44. 二叉树的序列化与反序列化

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

难点在于处理 null，如何判断终止？

• 如果使用层次遍历，则每一层的 null 都必须显式存入，而这时如果传入链表形式的二叉树，就会导致存储空间膨胀
• 这里使用了前序遍历的方式，将 null 视为了终点，一但出现 null 则停止向下搜索

import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringJoiner;
import java.util.stream.Collectors;

public class Codec {

    // Encodes a tree to a single string.
	public String serialize(TreeNode root) {
        StringJoiner sj = new StringJoiner(",");
        preorder(root, sj);
        return sj.toString();
    }

    private void preorder(TreeNode cur, StringJoiner sj) {
        if (cur == null) {
            sj.add("#");
            return;
        }
        sj.add(String.valueOf(cur.val));
        preorder(cur.left, sj);
        preorder(cur.right, sj);
    }

    // Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
        LinkedList<String> trees = Arrays.stream(data.split(",")).collect(Collectors.toCollection(LinkedList::new));
        return deHelper(trees);
    }

    private TreeNode deHelper(LinkedList<String> trees) {
        if (trees.isEmpty()) {
            return null;
        } else if ("#".equals(trees.get(0))) {
            trees.remove(0);
            return null;
        }
        TreeNode cur = new TreeNode(Integer.parseInt(trees.remove(0)));
        cur.left = deHelper(trees);
        cur.right = deHelper(trees);
        return cur;
    }
}

T56. 二叉树的直径

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root

The length of a path between two nodes is represented by the number of edges between them.

根据左右子树深度即可计算：经过 root 时，所能得到的最大直径。随后遍历整棵树，维护最大直径即可

public class Solution {

    private int ret;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ret = 0;
        preorder(root);
        return ret;
    }


    private int preorder(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = preorder(root.left);
        int right = preorder(root.right);
        ret = Math.max(ret, left + right);
        return Math.max(left, right) + 1;
    }
}

T61. 把二叉搜索树转换为累加树

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

根据二叉搜索树的性质：对于结点 cur

• 其左子树中的所有结点值都小于自身
• 其右子树中的所有结点值都大于自身

根据这个性质，如果使用中序遍历，则可以以从小到大的顺序遍历二叉搜索树；那么使用逆中序遍历，即可从大到小顺序遍历该二叉搜索树，再使用一个全局变量 sum 进行累加即可

![[images/Pasted image 20260224110447.png]]

public class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}

T77. 二叉树展开为链表

Given the root of a binary tree, flatten the tree into a “linked list”:

• The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The “linked list” should be in the same order as a pre-order traversal of the binary tree.

![[images/Pasted image 20260224142018.png]]

1. 如果没有空间复杂度要求，则直接根据前序遍历创建新的结点即可
2. 如果要求空间复杂度为 $O(1)$，则需要在原有二叉树的基础上移动结点来实现

由前序遍历的顺序（根左右）可以得出：对于结点 root，它的右子树一定会被拼接到左子树中的最右结点（如图则为将 5 拼接到 4 的右结点）

按照如下操作即可：

• 左子树移动到右子树
• 原右子树拼接到左子树的最右侧
• 按上述规律进行递归

注：题目虽然要求以前序遍历的顺序转换，但代码中实际上并不需要前序遍历

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode t = root;
        while (t.right != null) {
            t = t.right;
        }
        t.right = tmp;
        flatten(root.right);
    }
}

T79. 合并二叉树

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

双指针，以相同方式遍历树即可。可以构造新结点返回，也可以直接服用链路（因为当一个结点为空，另一结点非空时，非空结点之下可以还有很多子结点，但是它们必然不会被合并了，所以可以直接复用来提升效率）

public class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        } else if (root1 == null && root2 != null) {
            return root2;
        } else if (root1 != null && root2 == null) {
            return root1;
        }

        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

T80. 从前序与中序遍历序列构造二叉树

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

根据前序（根左右）和中序（左根右）的顺序，递归构造。

• 每次前序序列的第一个元素必为根节点
• 根据在前序序列中找到的根节点，在中序序列中找到根节点，在该节点左右的即为左子树和右子树

可以优化的点：将 inorder 用哈希表建立值和索引的关系（因为没有重复值），可以优化查询 root 的时间

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildHelper(int[] preorder, int pl, int pr, int[] inorder, int il, int ir) {
        if (pl > pr) {
            return null;
        }
        int rootVal = preorder[pl];
        TreeNode root = new TreeNode(rootVal);

        int i = 0;
        while (inorder[il + i] != rootVal) {
            i++;
        }

        root.left = buildHelper(preorder, pl + 1, pl + i, inorder, il, il + i - 1);
        root.right = buildHelper(preorder, pl + i + 1, pr, inorder, il + i + 1, ir);
        return root;
    }
}

T81. 二叉树的最大深度

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

遍历一下树即可

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

T82. 二叉树的层序遍历

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

广搜即可，注意要使用每层遍历的版本

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> row = new ArrayList<>();
            while (size-- > 0) {
                TreeNode cur = q.remove();
                row.add(cur.val);
                if (cur.left != null) {
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    q.add(cur.right);
                }
            }
            ret.add(row);
        }

        return ret;
    }
}

T83. 对称二叉树

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

双指针遍历，左树左节点对应右树右节点，左树右节点对应右树左节点

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null || right == null) {
            return left == null && right == null;
        }
        if (left.val != right.val) {
            return false;
        }
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

T84. 验证二叉搜索树

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys strictly less than the node’s key.
• The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

• 直接将二叉树转换为中序遍历序列，如果是合法的二叉搜索树，则为有序序列

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        List<Integer> arr = new ArrayList<>();
        inorder(root, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) <= arr.get(i - 1)) {
                return false;
            }
        }
        return true;
    }

    private void inorder(TreeNode root, List<Integer> arr) {
        if (root == null) {
            return;
        }
        inorder(root.left, arr);
        arr.add(root.val);
        inorder(root.right, arr);
    }
}

• 或者是传递上界和下界，确保在区域内

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean check(TreeNode root, long low, long high) {
        if (root == null) {
            return true;
        }
        if (root.val <= low || root.val >= high) {
            return false;
        }
        return check(root.left, low, root.val) && check(root.right, root.val, high);
    }
}

T86. 二叉树的中序遍历

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

有递归和非递归两种写法

递归

public class Solution {
    private List<Integer> ret;

    public List<Integer> inorderTraversal(TreeNode root) {
        ret = new ArrayList<>();
        inorder(root);
        return ret;
    }

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        ret.add(root.val);
        inorder(root.right);
    }
}

回溯

T51. 括号生成

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

回溯算法，使用 left 和 right 标记还剩下左、右括号的个数，需要注意的是每个右括号必须在一个左括号之后，所以要控制 right >= left

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<String>();
        backtrack(ret, new StringBuilder(), n, n);
        return ret;
    }

    // left表示还剩余的左括号; right表示剩余的右括号
    private void backtrack(List<String> list, StringBuilder path, int left, int right) {
        if (left == 0 && right == 0) {
            list.add(path.toString());
            return;
        }
        // 加(
        if (left > 0) {
            backtrack(list, path.append("("), left - 1, right);
            path.deleteCharAt(path.length() - 1);
        }
        // 加), 但是要确保left <= right
        if (right > left) {
            backtrack(list, path.append(")"), left, right - 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

T54. 全排列

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        backtrack(nums, new boolean[n], new ArrayList<>(), ret);
        return ret;
    }

    private void backtrack(int[] nums, boolean[] visited, List<Integer> path, List<List<Integer>> ret) {
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                path.add(nums[i]);
                visited[i] = true;
                backtrack(nums, visited, path, ret);
                visited[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

T55. 组合总和

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target . You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

回溯。注意需要使用 start 来控制起点，实现去重

public class Solution {

    private List<List<Integer>> ret;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new ArrayList<>();
        backtrack(candidates, target, 0, 0, new ArrayList<>());
        return ret;
    }

    private void backtrack(int[] nums, int target, int start, int sum, List<Integer> path) {
        if (sum > target) {
            return;
        } else if (sum == target) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, target, i, sum + nums[i], path);
            path.remove(path.size() - 1);
        }
    }
}

T67. 电话号码的字母组合

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
![[images/Pasted image 20251208191010.png]]

根据数字映射字母回溯即可

package t061_070.t067;

import java.util.ArrayList;
import java.util.List;


public class Solution {
    private final static char[][] phone = {{}, {}, {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
            {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}
    };

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        backtracking(digits, 0, new StringBuilder(), res);
        return res;
    }

    private void backtracking(String digits, int startIndex, StringBuilder path, List<String> res) {
        if (path.length() == digits.length()) {
            res.add(path.toString());
            return;
        }
        for (int i = startIndex; i < digits.length(); i++) {
            for (char c : phone[digits.charAt(i) - '0']) {
                path.append(c);
                backtracking(digits, i + 1, path, res);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}

T76. 单词搜索

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

深搜

public class Solution {
    private static int[] fx = {1, -1, 0, 0}, fy = {0, 0, 1, -1};

    private char[][] board;
    private String word;
    private int n, m;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.m = board.length;
        this.n = board[0].length;

        char start = word.charAt(0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == start) {
                    boolean search = dfs(i, j, new boolean[m][n], 1);
                    if (search) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, boolean[][] visited, int idx) {
        if (idx == word.length()) {
            return true;
        }
        visited[x][y] = true;
        char cur = word.charAt(idx);
        boolean ret = false;
        for (int i = 0; i < 4; i++) {
            int dx = x + fx[i], dy = y + fy[i];
            if (0 <= dx && dx < m && 0 <= dy && dy < n && !visited[dx][dy]) {
                if (board[dx][dy] == cur) {
                    ret = ret || dfs(dx, dy, visited, idx + 1);
                }
            }
        }
        visited[x][y] = false;
        return ret;
    }
}

T90. 子集

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

基本回溯，注意结果的存储时机

public class Solution {

    private List<List<Integer>> ret;

    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>());
        return ret;
    }

    private void dfs(int[] nums, int startIndex, List<Integer> subset) {
        ret.add(new ArrayList<>(subset));
        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            dfs(nums, i + 1, subset);
            subset.remove(subset.size() - 1);
        }
    }
}

图

T9. 课程表

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.

You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

检测是否有换，求拓扑排序：

1. 先构造图（邻接表、邻接矩阵）
2. 接着找到入口（入度为 0 的节点），放入队列
3. 遍历队列，删去队首元素和其他节点的边，并修改它们的边数，将入边减为 0 的节点入队
4. 如果存在节点没有入队，则说明不能完成（可以判断遍历过的节点个数和总节点数）

邻接表

本题为稀疏图，用邻接表效率更好：

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 邻接表
        int[] in = new int[numCourses];
        LinkedList<Integer>[] out = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            out[i] = new LinkedList<>();
        }

        // 初始化边
        for (int[] edge : prerequisites) {
            int from = edge[0], to = edge[1];
            in[to]++;
            out[from].add(to);
        }

        // 求拓扑排序
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                queue.add(i);
                cnt++;
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.remove();

            // 删除cur出边对应的入边
            for (int to : out[cur]) {
                in[to]--;
                if (in[to] == 0) {
                    cnt++;
                    queue.add(to);
                }
            }
        }

        return cnt == numCourses;
    }
}

T11. 岛屿数量

Given an m x n 2D binary grid grid which represents a map of '1' s (land) and '0' s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Flood Fill，使用 BFS 和 DFS 都可以

public class Solution {
    private static final int[] fx = {1, -1, 0, 0};
    private static final int[] fy = {0, 0, 1, -1};
    private int n, m;

    public int numIslands(char[][] grid) {
        n = grid.length;
        m = grid[0].length;

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private void dfs(char[][] grid, int x, int y) {
        grid[x][y] = '2';
        for (int i = 0; i < 4; i++) {
            int dx = x + fx[i], dy = y + fy[i];
            if (0 <= dx && dx < n && 0 <= dy && dy < m && grid[dx][dy] == '1') {
                dfs(grid, dx, dy);
            }
        }
    }
}

T34. 除法求值

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

建立一张有向图，路径权重即为 a / b，只需要使用 Floyd 算法计算出各个点的距离即可，相互不可达的点结果就是 -1.0

需要注意测试用例中存在一个长路径例子，存在精度问题，使用：

if (graph[i][k] > 0 && graph[k][j] > 0 && graph[i][j] < 0) {
    graph[i][j] = graph[i][k] * graph[k][j];
    graph[j][i] = 1 / graph[i][j];
}

来提高精度

public class Solution {
    // equations最大20，每个2个元素；同时queries中也可能出现新元素，最多80个元素
    private static final int N = 80;
    private static final double INF = -1.0;
    private Map<String, Integer> map = new HashMap<>();
    private double[][] graph = new double[N][N];
    private int n = 0;

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // equations 为边数，明显为稀疏图，使用邻接矩阵，同时节点数还未知，使用一个map进行映射
        for (int i = 0; i < N; i++) {
            Arrays.fill(graph[i], INF);
        }

        for (int i = 0; i < equations.size(); i++) {
            List<String> edge  = equations.get(i);
            int from = getNode(edge.get(0));
            int to = getNode(edge.get(1));
            graph[from][to] = values[i];
            graph[to][from] = 1.0 / values[i];
        }

        // floyd
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][k] > 0 && graph[k][j] > 0 && graph[i][j] < 0) {
                        graph[i][j] = graph[i][k] * graph[k][j];
                        graph[j][i] = 1 / graph[i][j];
                    }
                }
            }
        }

        int q = queries.size();
        double[] ret = new double[q];
        for (int i = 0; i < q; i++) {
            List<String> query  = queries.get(i);
            double t = -1.0;
            int ia = getNode(query.get(0)), ib = getNode(query.get(1));
            if (graph[ia][ib] > 0) {
                t = graph[ia][ib];
            }
            ret[i] = t;
        }
        return ret;
    }

    private int getNode(String node) {
        if (!map.containsKey(node)) {
            map.put(node, n++);
        }
        return map.get(node);
    }
}

排序

T7. 数组中第 k 个最大元素

^5900fe

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

堆排序（手动实现）

• 创建堆：从最后一个非叶子节点开始进行下沉
• 下沉：比较根左右大小，进行交换

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        buildHeap(nums);
        int ret = 0;
        for (int i = 0; i < k; i++) {
            ret = pop(nums, nums.length - i);
        }
        return ret;
    }

    private void buildHeap(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            sink(nums, i, nums.length);
        }
    }

    private void sink(int[] nums, int x, int n) {
        if (x >= n) {
            return;
        }

        int idx = x, maxi = nums[x];
        int l = x * 2 + 1;
        if (l < n && maxi < nums[l]) {
            idx = l;
            maxi = nums[l];
        }
        if (l + 1 < n && maxi < nums[l + 1]) {
            idx = l + 1;
            maxi = nums[l + 1];
        }

        if (idx == x) {
            return;
        }
        int tmp = nums[x];
        nums[x] = nums[idx];
        nums[idx] = tmp;
        sink(nums, idx, n);
    }

    private int pop(int[] nums, int n) {
        int ret = nums[0];
        nums[0] = nums[n - 1];
        sink(nums, 0, n);
        return ret;
    }
}

使用 PriorityQueue

需要掌握如何设定排序规则

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int num : nums) {
            pq.add(num);
        }

        int ret = 0;
        for (int i = 0; i < k; i++) {
            ret = pq.poll();
        }
        return ret;
    }
}

快速排序

进行第一次排序后，可以通过判断 k 与左右部分的长度来判断第 k 大的数在左部分还是在右部分

1. k <= SL 递归 Left
2. k > SL 递归 Right，且 k = k - SL

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickK(nums, k, 0, nums.length - 1);
    }

    private int quickK(int[] nums, int k, int l, int r) {
        if (l >= r) {
            return nums[l];
        }
        int x = nums[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do {
                i++;
            } while (nums[i] > x);
            do {
                j--;
            } while (nums[j] < x);
            if (i < j) {
                swap(nums, i, j);
            }
        }

        // 计算k在左半部分还是右半部分
        int sl = j - l + 1;
        if (k <= sl) {
            return quickK(nums, k, l, j);
        } else {
            return quickK(nums, k - sl, j + 1, r);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

T17. 排序链表

Given the head of a linked list, return *the list after sorting it in ascending order*.

• 插入排序
• 归并排序
  • 使用快慢指针分割链表，不断分割至最小
  • 然后二路归并，合并两个链表

实际上和数组没什么区别，关键在于将链表分成两半

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // split to two part
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(tmp);

        // merge two sorted lists
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                cur.next = left;
                cur = cur.next;
                left = left.next;
            } else {
                cur.next = right;
                cur = cur.next;
                right = right.next;
            }
        }

        while (left != null) {
            cur.next = left;
            cur = cur.next;
            left = left.next;
        }
        while (right != null) {
            cur.next = right;
            cur = cur.next;
            right = right.next;
        }

        return dummyHead.next;
    }
}

但实际上直接转换为数组，然后排序反而更快

T36. 前 K 个高频元素

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

先统计，使用哈希表，遍历数组进行记录每个元素出现的个数。然后有以下方法可以求前 k 个出现次数最多的元素：

• 直接构造大根堆，选取前 $k$ 个元素。时间复杂度为 $O(n\log n)$ ，不满足要求
• 构造小根堆，但是限制堆的大小不超过 $k$，这样每次新加入元素只需要和堆顶元素比较即可。时间复杂度为 $O(n\log k)$
• 快速排序：类似于数组中第 k 个最大元素，找到第 k 个最大元素，这样在它其中一侧的元素就都是所求结果

小根堆

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计数量 pair<num, count>
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 计算前k pair<count, num>
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[0] - b[0];
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.add(new int[] {entry.getValue(), entry.getKey()});
            if (pq.size() > k) {
                pq.remove();
            }
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = pq.remove()[1];
        }
        return ret;
    }
}

T62. 合并 K 个升序链表

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

多路归并，记平均结点数为 $N$

• 可以每次都遍历 $K$ 个链表的头结点，找出最小值，时间复杂度为 $O(K^2N)$
• 也可以维护一个优先队列，K-V 为 (head.val, head.index)，可以快速定位下一个链表，时间复杂度为 $O(k\log k N)$
• 或者分治思想，每次两两合并

public class Solution {
    private static class Node implements Comparable<Node> {
        private int val, idx;
        public Node(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }

        @Override
        public int compareTo(Node o) {
            if (this.val == o.val) {
                return this.idx - o.idx;
            }
            return this.val - o.val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int n = lists.length;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (lists[i] == null) {
                continue;
            }
            pq.add(new Node(lists[i].val, i));
        }

        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while (!pq.isEmpty()) {
            Node top = pq.remove();
            int idx = top.idx;
            cur.next = lists[idx];
            cur = cur.next;
            lists[idx] = lists[idx].next;
            if (lists[idx] != null) {
                pq.add(new Node(lists[idx].val, idx));
            }
        }
        return dummyHead.next;
    }
}

T95. 最短无序连续子数组

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

可以将整个数组分为 3 段：

• 递增段 A
• 无序段 B
• 递增段 C

题目是需要找到其中的无序段 B。对于递增段 A 和 C，由于已经是有序的，所以如果对数组进行排序，则 A 和 C 不会受到影响。那么只需要找到排序数组和原数组不同两个边界，就能确定这个无序段 B

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] sorted = new int[n];
        System.arraycopy(nums, 0, sorted, 0, n);
        Arrays.sort(sorted, 0, n);
        int left = 0, right = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] != sorted[i]) {
                left = i;
                break;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] != sorted[i]) {
                right = i;
                break;
            }
        }
        return right - left + 1;
    }
}

动态规划

T6. 最大正方形

Given an m x n binary matrix filled with 0 ‘s and 1 ‘s, find the largest square containing only 1 ‘s and return its area.

1. 前缀和，判断正方形区块内和是否为平方数
2. 动态规划

• f[i][j]
  • 表示矩阵中第 $i$ 行第 $j$ 列的位置，能够形成的最大正方形
  • 大小
• 计算
  • $f[i][j]=1$ if $matrix[i][j]==1$
  • $f[i][j]=2$ if $matrix[i][j]==1: & : f[i-1][j]==1: & : f[i][j-1]==1: & : f[i-1][j-1]==1$ *
  • $f[i][j]=n$ if $matrix[i][j]==1:&: f[i-1][j]==n-1:&: f[i][j-1]==n-1:&: f[i-1][j-1]==n-1$

即：

$$
f[i][j]=\min{f[i-1][j],f[i][j-1],f[i-1][j-1]}+1,if: matrix[i][j]==1
$$

public class Solution {
    public int maximalSquare(char[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[][] f = new int[n + 1][m + 1];
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
                    ret = Math.max(ret, f[i][j] * f[i][j]);
                }
            }
        }
        return ret;
    }

    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

T12. 打家劫舍

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police*.

动态规划

• $f[i]$
  • 表示只考虑前 $i$ 个房子，抢劫的所有方案
  • max value
• 计算
  • 第 $i$ 个抢，那么第 $i-1$ 不能抢：$f[i]=f[i-2]+nums[i]$
  • 第 $i$ 个不抢，继承第 $i-1$ 个：$f[i]=f[i-1]$
  • 取最大值：$f[i]=max{f[i-1], f[i-2]+nums[i]}$
• 初始化：$f[0]$ 和 $f[1]$

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        int[] f = new int[n];
        f[0] = nums[0];
        f[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);
        }
        return f[n - 1];
    }
}

T21. 单词拆分

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

• f[i]
  • 表示前 $i$ 个字符，能被 wordDict 组合的所有组合（注意 $i$ 从 0 开始还是 1 开始，这里选用 1-index）
  • bool
• 遍历 wordDict，记每个元素为 word，则 f[i] = f[i - len(word)] && s[i - len(word): i] == word
  • 判断当前位置能否由前一组组合，和某一单词组成

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] f = new boolean[n + 1];

        f[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int m = word.length();
                if (i - m >= 0 && f[i - m]) {
                    f[i] = f[i] || s.substring(i - m, i).equals(word);
                }
            }
        }
        return f[n];
    }
}

T26. 零钱兑换

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

完全背包问题

• f[i][j]
  • 只使用了前 $i$ 种硬币，凑出金额为 $j$ 的所有组合方案
  • min count
• 计算
  • 不使用第 $i$ 种硬币
  • 使用 1 个第 $i$ 种硬币
  • 使用 2 个第 $i$ 种硬币
  • …

得到：

$$
f[i][j]=min(f[i-1][j],:f[i-1][j-coins[i]]+1,f[i-1][j-2*coins[i]]+2,…)
$$

此时由于要遍历硬币种类、金额、硬币数量，需要 $O(n^3)$ 时间

取 $f[i][j-coins[i]]$：

$$
f[i][j-coins[i]]=min(f[i-1][j-coins[i]],f[i-1][j-2*coins[i]]+1,…)
$$

将下面的式子代入上面，可得：

$$
f[i][j]=min(f[i-1][j], f[i][j-coins[i]]+1)
$$

消去了数量，只需要控制遍历顺序，就可以将 $O(n^3)$ 简化为 $O(n^2)$

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] f = new int[amount + 1];

        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                f[j] = Math.min(f[j], f[j - coin] + 1);
            }
        }
        return f[amount] == 0x3f3f3f3f ? -1 : f[amount];
    }
}

T27. 目标和

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

1. 回溯
2. 动态规划

两个背包，一个背包 package_a 存放标记为正的元素，另一个背包 package_b 存放标记为负的元素。package_a - package_b = target。

设 nums 的元素和为sum, 可以列出方程：

$$
\begin{align}\left{\begin{aligned}
package_a - package_b = target; \
package_a + package_b = sum;
\end{aligned}\right.\end{align}
$$

则  package_a = (sum + target) / 2。
所以根据题意给的target和sum，可以求出package_a的值。

那这道题就可以转化为：给定一个大小为 package_a 的背包，有多少种组合方式能把背包装满？ 即 0-1 背包。

需要注意的是：sum + target 需要为非负偶数

• 非负：确保能凑出
• 偶数：确保划分时不会导致小数缺失

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        // p_a - p_b = target
        // p_a + p_b = sum
        // p_a = (target + sum) / 2
        int pa = target + sum;
        if (pa < 0 || pa % 2 == 1) {
            return 0;
        }
        pa /= 2;

        int[] f = new int[pa + 1];
        f[0] = 1;
        for (int num : nums) {
            for (int j = pa; j >= num; j--) {
                f[j] += f[j - num];
            }
        }

        return f[pa];
    }
}

T32. 分割等和子集

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

先求和 sum，然后判断能否组成 sum/2 就好（0-1 背包），需要注意 sum 必须为偶数

public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if ((sum & 1) == 1) {
            return false;
        }

        int n = sum / 2;
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for (int num : nums) {
            for (int j = n; j >= num; j--) {
                f[j] = f[j] || f[j - num];
            }
        }
        return f[n];
    }
}

T38. 打家劫舍 III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return *the maximum amount of money the thief can rob without alerting the police*.

不同于数组的动态规划，直接用下标来对应元素，结点可以使用哈希表来对应。

需要考虑当前结点是否选择，使用两个哈希表 f，g

• f：选取了当前结点，所能得到的最大值
• g：不选取当前结点，所能得到的最大值

记当前结点为 root，则有：

$$
f[root]=g[root.left]+g[root.right])+root.val
$$

和

$$
g[root]=max(f[root.left],g[root.left])+max(f[root.right],g[root.right])
$$

public class Solution {
    private final Map<TreeNode, Integer> f = new HashMap<>();
    private final Map<TreeNode, Integer> g = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        rob(root.left);
        rob(root.right);
        f.put(root, root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));
        g.put(root,
                Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) +
                        Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0))
        );

        return Math.max(f.get(root), g.get(root));
    }
}

T40. 戳气球

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

添加 nums[-1] 和 nums[n]，构成新数组 vals 这样子处理可以避免越界（将数组整体移动，index0-n+1，vals.length == n + 2）

将戳改为放，从而转换为区间动态规划问题，但是需要注意最左和最右不能放置

• f[i][j]
  • 填满 (i,j) 的所有方案（注意是开区间）
  • max coins
• 使用 $k$ 遍历分割点

得到函数：

$$
f[i][j]=\left{
\begin{aligned}
\max(vals[i]*vals[k]*vals[j]+f[i][k]+f[k][j]),\ \ \text{i<j} \
0,\ \ i\geq j
\end{aligned}
\right}
$$

最后答案即为 $f[0][n + 1]$

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] vals = new int[n + 2];
        vals[0] = vals[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            vals[i + 1] = nums[i];
        }

        int[][] f = new int[n + 2][n + 2];
        // 长度至少为3，确保i和j之间至少有一个元素
        for (int len = 3; len <= n + 2; len++) {
            for (int i = 0; i <= n; i++) {
                int j = i + len - 1;
                if (j >= n + 2) {
                    break;
                }
                // 选定(i,j)
                for (int k = i + 1; k < j; k++) {
                    f[i][j] = Math.max(f[i][j], vals[i] * vals[k] * vals[j] + f[i][k] + f[k][j]);
                }
            }
        }
        return f[0][n + 1];
    }
}

T43. 最长递增子序列

Given an integer array nums, return *the length of the longest strictly increasing subsequence.

动态规划- $O(n^2)$

• f[i] 表示以第 $i$ 个元素为结尾，所能构造的所有递增子序列
  • max length
• $f[i]=max(f[i-k])+1::if:nums[i]>nums[i-k](0\leq k\leq i)$

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int ret = 1;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}

贪心+二分- $O(n\log n)$

• f[i] 表示长度为 $i$ 的最长递增子序列的末尾元素
• 希望对于每一个长度的递增子序列，末尾元素都尽可能的小（贪心），这样才可能更长
• 而 f 是单调递增的
  • 因为长度更长的子序列肯定包含了长度短的子序列
  • 如果 $f[j]≥f[i],j<i$，从长度为 $i$ 的最长上升子序列的末尾删除 $i−j$ 个元素，那么这个序列长度变为 $j$ ，且第 $j$ 个元素 $x$（末尾元素）必然小于 $f[i]$，也就小于 $f[j]$。那么就找到了一个长度为 $j$ 的最长上升子序列，并且末尾元素比 $f[j]$ 小，从而产生了矛盾。因此数组 f 的单调性得证。
• 对于 nums[i]，如果
  • nums[i] > f[len]，则 len++，意味着最长递增子序列可以再延长
  • nums[i] <= f[len]，则二分查找 $x$ 使得 $f[x-1]\leq f[x]$

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int len = 1;
        f[1] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > f[len]) {
                len++;
                f[len] = nums[i];
            } else {
                int l = find(f, len, nums[i]);
                f[l] = nums[i];
            }
        }
        return len;
    }

    private int find(int[] f, int len, int x) {
        int l = 1, r = len;
        while (l < r) {
            int mid = l + r >> 1;
            if (f[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

T47. 完全平方数

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

转换为完全背包问题即可

public class Solution {
    public int numSquares(int n) {
        int[] nums = new int[101];
        for (int i = 1; i <= 100; i++) {
            nums[i] = i * i;
        }
        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 1; i <= 100; i++) {
            for (int j = nums[i]; j <= n; j++) {
                f[j] = Math.min(f[j], f[j - nums[i]] + 1);
            }
        }
        return f[n];
    }
}

T54. 接雨水

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

![[images/Pasted image 20260302082632.png]]

对于第 $i$ 个位置，它所能接的水的高度，取决于其两边的最大高度的最小值（不一定是紧邻）

• 朴素算法：对于每一个位置都向两侧查找最大值（$O(N^2)$）
• 动态规划：预处理左右两侧的最大高度：lh[]、rh[]
  • lh[0] = h[0]
  • rh[n-1] = h[n-1]
  • lh[i] = max(h[i-1], lh[i-1])
  • rh[i] = max(h[i+1], rh[i+1])

public class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] lh = new int[n], rh = new int[n];
        lh[0] = height[0];
        rh[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            lh[i] = Math.max(height[i - 1], lh[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rh[i] = Math.max(height[i + 1], rh[i + 1]);
        }

        int ret = 0;
        for (int i = 1; i < n - 1; i++) {
            int diff = Math.min(lh[i], rh[i]) - height[i];
            ret += diff > 0 ? diff : 0;
        }
        return ret;
    }
}

T59. 最长有小括号

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

方法一：可以使用栈对 s 进行预处理，将可以匹配的置为 0，不能匹配的置为 1，这样就转换为了最长序列问题

public class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] arr = new int[n];
        // 预处理。栈存储左括号索引
        List<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                // 当前为左括号
                stack.add(i);
            } else {
                // 为右括号
                if (stack.isEmpty()) {
                    // 如果栈空，则无对应左括号，置1
                    arr[i] = 1;
                    continue;
                }
                // 栈非空，则有对应左括号，左括号出栈
                // 左右括号对应索引置0（不操作）
                stack.remove(stack.size() - 1);
            }
        }
        // 合法的括号都已经匹配，栈内剩余括号为未匹配的括号
        stack.forEach(i -> arr[i] = 1);

        // 寻找最长0子串
        int ret = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                cur = 0;
            } else {
                cur++;
            }
            ret = Math.max(ret, cur);
        }
        return ret;
    }
}

方法二：动态规划

T85. 不同的二叉搜索树

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

![[images/Pasted image 20260306115058.png]]

寻找规律：

• 1 个结点构成：1 棵树
• 2 个结点构成：2 棵树
  • 以 1 为根：剩余 2 构成 1 棵树
  • 以 2 为根：剩余 3 构成 1 棵树
• 3 个结点构成：5 棵树
  • 以 1 为根：剩余 2 / 3 构成 2 棵树
  • 以 2 为根：剩余 1 / 3 构成 1 棵树
  • 以 3 为根：剩余 1 / 2 构成 2 棵树

可以将结点之间的大小转换为左子树和右子树的结点数量：根结点轮换，实际上就是控制左右树的结点数量

左子树可能类型 x 右子树可能类型 = 当前根结点所能构成的所有类型

public class Solution {
    public int numTrees(int n) {
        int[] f = new int[n + 1];
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                f[i] += f[j] * f[i - 1 - j];
            }
        }
        return f[n];
    }
}

T93. 编辑距离

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

假设有单词 A 和 B，那么上面 3 种操作一共有 6 种方法（分别对 A 和 B）

• 对于 A 删除一个字符，和对于 B 插入一个字符等价
• 对于 B 删除一个字符，和对于 A 插入一个字符等价
• 对于 A 替换一个字符，和对于 B 替换一个字符等价

所以本质上只有 3 种操作：

• 在 A 插入一个字符
• 在 B 插入一个字符（在 A 删除一个字符）
• 修改 A 的一个字符

那么讨论每一种操作（以 A=horse 和 B=ros 为例）：

• 在 A 插入一个字符：假设 horse 到 ro 的距离为 $a$，那么从 horse 到 ros 的距离不会超过 $a+1$（使用 $a$ 次操作将 horse 变为 ro，并使用额外的 $1$ 次操作添加一个 s，就能使用 $a+1$ 次操作将 horse 变为 ros）
• 在 B 插入一个字符：假设从 hors 到 ros 的距离为 $b$，同理那么从 horse 到 ros 的距离不会超过 $b+1$
• 修改 A 的一个字符：同理得不超过 c+1

即从 horse 到 ros 的编辑距离为：

$$
min(a+1,b+1,c+1)
$$

注：操作的顺序不影响结果，所以可以只在单词末尾插入或者修改字符

将给定的单词继续拆分，直到

• A 从空字符串 转换为 ros
• A 从非空字符串转换为空

使用 f[i][j] 表示用 A 的前 $i$ 个字母和 B 的前 $j$ 个字母之间的编辑距离

• f[i][j-1]：f[i][j] = f[i][j - 1] + 1，在 A 末尾插入字符
• f[i-1][j]：f[i][j] = f[i - 1][j] + 1，在 B 末尾插入字符
• f[i-1][j-1]：修改 A[i] 和 B[j] 使其保持一致，如果本身就相等，就不用额外操作，否则 f[i][j] = f[i - 1][j - 1] + 1

最后得到：

• A 和 B 最后一个字母相同

  $$
  f[i][j]=\min(f[i][j-1]+1,f[i-1][j]+1,f[i-1][j-1])=1+min(f[i][j-1],f[i-1][j],f[i-1][j-1]-1)
  $$

• A 和 B 最后一个字母不同

$$
f[i][j] = 1+\min(f[i][j-1],f[i-1][j].f[i-1][j-1])
$$

每一步结果都基于上一步的计算结果

public class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] f = new int[n + 1][m + 1];

        // 边界初始化
        // word1执行 i 次删除得到 word2
        for (int i = 0; i <= n; i++) {
            f[i][0] = i;
        }
        // word1 执行 j 次插入得到 word2
        for (int j = 0; j <= m; j++) {
            f[0][j] = j;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // word1插入
                int insert = f[i - 1][j] + 1;
                // word1删除
                int delete = f[i][j - 1] + 1;
                // word1修改
                int update = f[i - 1][j - 1];
                // 判断word1[i-1]和word2[j-1]是否相同，如果相同则无需额外操作，否则需要进行修改
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    update++;
                }
                // 取3种操作中的最小值
                f[i][j] = Math.min(update, Math.min(insert, delete));
            }
        }
        return f[n][m];
    }
}

T94. 爬楼梯

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

递归，或者动态规划

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

T96. 最小路径和

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

本质杨辉三角，每个格子只受左边和上边影响

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] f = new int[n];

        f[0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            f[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                f[j] = Math.min(f[j - 1], f[j]) + grid[i][j];
            }
        }

        return f[n - 1];
    }
}

T97. 不同路径

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

动态规划

本质上是一个杨辉三角，每个格子（除最左边和最顶边外）中的值都来源于左边的格子和上面的格子

• f[i][j]
  • 走到第 $i$ 行第 $j$ 列的所有方案
  • count

$$
f[i][j]=\left
{
\begin{aligned}
f[i-1][j]+f[i][j-1],\ \ i \neq 0 & j \neq 0 \
1,\ \ \text{else}
\end{aligned}
\right
}
$$

而由于每个格子都只受左侧格子和上侧格子影响，所以可以将二维数组优化为一维数组

public class Solution {
    public int uniquePaths(int m, int n) {
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 0; i < m - 1; i++) {
            // 跳过f[0]，相当于f[0] = 1
            for (int j = 1; j < n; j++) {
                // f[i][j] = f[i - 1][j] + f[i][j - 1]
                f[j] += f[j - 1];
            }
        }

        return f[n - 1];
    }
}

数学方法

一共需要走 $m+n-2$ 步，向下 $m-1$ 步，向右 $n-1$ 步，那么就是走步的排列组合，答案为 $C^{n-1}_{m+n-2}$

需要注意的是计算中可能会发生越界

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m > n) {
            int temp = m;
            m = n;
            n = temp;
        }
        int x = m + n - 2;
        // C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)
        // m+n-2-m+1 = n-1        long ret = 1;
        for (int i = 1, j = m; i <= n - 1; i++, j++) {
            ret *= j;
            ret /= i;
        }
        return (int) ret;
    }
}

贪心

T33. 根据身高重建队列

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

因为身高低的人无论怎么移动，都不会影响高的人的 k，所以先按照身高从大到小排序，再从身高高的开始调整，每次就只会影响一个变量，相当于降维处理

• 将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照 $h_{i}$ 为第一关键字降序，$k_{i}$ 为第二关键字升序进行排序。
• 如果按照排完序后的顺序，依次将每个人放入队列中，那么当放入第 $i$ 个人时：
  • 第 0,⋯,i−1 个人已经在队列中被安排了位置，他们只要站在第 $i$ 个人的前面，就会对第 $i$ 个人产生影响，因为他们都比第 $i$ 个人高；
  • 而第 i+1,⋯,n−1 个人还没有被放入队列中，并且他们无论站在哪里，对第 $i$ 个人都没有任何影响，因为他们都比第 $i$ 个人矮。
• 在这种情况下，无从得知应该给后面的人安排多少个空位置，因此就不能沿用方法一。
  • 但可以发现，后面的人既然不会对第 $i$ 个人造成影响，就可以采用插空的方法，依次给每一个人在当前的队列中选择一个插入的位置。
  • 也就是说，当放入第 $i$ 个人时，只需要将其插入队列中，使得他的前面恰好有 $k_{i}$个人即可。

1. 身高降序、k 升序排序
2. 按照 k 直接插入

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return b[0] - a[0];
        });

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] p : people) {
            list.add(p[1], p);
        }
        return list.toArray(new int[list.size()][]);
    }
}

T98. 合并区间

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

按照 interval[0] 升序排序，贪心合并

public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        List<int[]> ret = new ArrayList<>();
        int left = intervals[0][0], right = intervals[0][1];
        for (int[] interval : intervals) {
            if (right < interval[0]) {
                ret.add(new int[]{left, right});
                left = interval[0];
                right = interval[1];
            } else {
                right = Math.max(right, interval[1]);
            }
        }
        ret.add(new int[]{left, right});
        return ret.toArray(new int[ret.size()][2]);
    }
}

T100. 最大子数组和

Given an integer array nums, find the subarray with the largest sum, and return its sum.

贪心：统计 sum，当 sum < 0 时，直接抛弃前面的，因为它们对于结果的贡献为负，只需要找贡献为正的子数组

public class Solution {
    public int maxSubArray(int[] nums) {
        int ret = nums[0];
        int sum = 0;
        for (int num : nums) {
            sum += num;
            ret = Math.max(ret, sum);
            sum = Math.max(sum, 0);
        }
        return ret;
    }
}

数学

T13. 多数元素

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore 投票算法：一命抵一命，最后留下来的肯定是多数元素

public class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        int num = nums[0];
        for (int i : nums) {
            if (cnt == 0) {
                num = i;
            }

            if (i == num) {
                cnt++;
            } else {
                cnt--;
            }
        }
        return num;
    }
}

也可以用：

1. 哈希表 ：时间复杂度$O (n)$；空间复杂度$O (n)$
2. 排序后取中间位置：复杂度视选用的排序方式
3. 分治

位运算

T22. 只出现一次的数据

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

位运算，两个相同的数进行异或得到 0，一个数和 0 异或得到本身

public class Solution {
    public int singleNumber(int[] nums) {
        int ret = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }
}

T28. 汉明距离

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

public class Solution {
    public int hammingDistance(int x, int y) {
        int ret = 0;
        while (x != 0 || y != 0) {
            if ((x & 1) != (y & 1)) {
                ret++;
            }
            x >>= 1;
            y >>= 1;
        }
        return ret;
    }
}

T37. 比特位计数

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] *is the number of* 1 *‘s in the binary representation of* i.

如果直接遍历，使用 $O(n\log n)$ 很简单，需要考虑能否优化为 $O(n)$ 的时间复杂度

寻找规律：

• 一个奇数 $x$ 一定比 $x-1$ 多 1
• 一个偶数 $y$ 一定和 $y/2$ 相同（右移，去掉了末尾 0，1 的个数不变）

public class Solution {
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        ret[0] = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & 1) == 1) {
                // 奇数一定比前一个数多一个
                ret[i] = ret[i - 1] + 1;
            } else {
                // 偶数一定等于它的一半的结果
                ret[i] = ret[i / 2];
            }
        }
        return ret;
    }
}