LeetCode Hot 100（全）

Leetcode Hot 100

题目

链表

LCR 026. 重排链表

链接：LCR 026. 重排链表 - 力扣（LeetCode）

1->2->3->4变成1->4->2->3

1->2->3->4->5变成1->5->2->4->3

1.队列+栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        Queue<ListNode> queue = new LinkedList<>();//前半部分
        Deque<ListNode> stack = new LinkedList<>();//后半部分

        // 找中点
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode cur = head;
        while(cur != slow.next){
            queue.add(cur);
            cur = cur.next;
        }
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        ListNode dummy = new ListNode(0);
        cur = dummy;
        while(!queue.isEmpty() && !stack.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
            cur.next = stack.pop();
            cur = cur.next;
            System.out.println(cur.val);
        }

        while(!queue.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
        }
        cur.next = null;

        head = dummy.next;
    }
}

2.线性表存顺序

3.寻找链表中点 + 链表逆序 + 合并链表

技巧

只出现一次的数字

136. 只出现一次的数字 - 力扣（LeetCode）

1.异或：a^a=0 a^0=a

多数元素

169. 多数元素 - 力扣（LeetCode）

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素

1
2
3
4
5
输入：nums = [3,2,3]
输出：3

输入：nums = [2,2,1,1,1,2,2]
输出：2

找众数

1.哈希

2.排序（取中间）

3.随机化找众数

4.分治法找众数：一定是左半部分或者右半部分中的众数

5.Boyer-Moore 投票算法

1
2
3
4
nums:      [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] 众数：7
candidate:  7  7  7  7  7  7   5  5   5  5  5  5   7  7  7  7 （候选众数）
count:      1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4 （和候选众数相等+1，否则减1）
value:      1  2  1  2  1  0  -1  0  -1 -2 -1  0   1  2  3  4 （和众数相等+1，否则减1）

寻找重复数

287. 寻找重复数 - 力扣（LeetCode）

题目：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

1
2
3
4
5
6
输入：nums = [1,3,4,2,2]
输出：2
输入：nums = [3,1,3,4,2]
输出：3
输入：nums = [3,3,3,3,3]
输出：3

1.哈希

颜色分类

75. 颜色分类 - 力扣（LeetCode）

1
2
3
4
5
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

输入：nums = [2,0,1]
输出：[0,1,2]

1.单指针：两次for循环，换0，换1

2.双指针：一次for循环（从左到右），首同时换0同时换1

3.双指针：一次for循环（首尾），首换0，尾换2

下一个排列

31. 下一个排列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,2,3]
输出：[1,3,2]

输入：nums = [3,2,1]
输出：[1,2,3]

输入：nums = [1,1,5]
输出：[1,5,1]

1 3 5 2 1            1 2 5 3 1
1 5 1 2 3            1 3 1 2 5

1.从右往左，找到第一个升序的位置，把他和后面开始第一个大于他的交换。然后从这个位置下一位开始翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public void nextPermutation(int[] nums) {
        int left = -1;
        for(int i=nums.length-2; i>=0; i--){
            if(nums[i] < nums[i+1]){
                left = i;
                break;
            }
        }
        for(int i=nums.length-1; i>left && left!= -1; i--){
            if(nums[i] > nums[left]){
                //交换
                int temp = nums[left];
                nums[left] = nums[i];
                nums[i] = temp;
                break;
            }
        }
        //右边一定是降序排序
        for(int i=left+1, j=nums.length-1; i<(left + nums.length + 1)/2; i++, j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

哈希

两数之和

1. 两数之和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

输入：nums = [3,2,4], target = 6
输出：[1,2]

输入：nums = [3,3], target = 6
输出：[0,1]

1.遍历一次，每次找target-num[i]

字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

输入: strs = [""]
输出: [[""]]

输入: strs = ["a"]
输出: [["a"]]

1.遍历一次，每个单词排序后作为key，value是list，key相同的放到同一个list

2.遍历一次，每个单词key为（字母+出现个数），value是list，key相同的放到同一个list

作用：降低排序复杂度，排序klongk，第二种方法k+字符集大小

*最长连续序列

128. 最长连续序列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

输入：nums = [1,0,1,2]
输出：3

1.从x开始找，x+1，x+2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;
        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}

2.连续区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int longestConsecutive(int[] nums) {
        // key表示num，value表示num所在连续区间的长度
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            // 当map中不包含num，也就是num第一次出现
            if (!map.containsKey(num)) {
                // left为num-1所在连续区间的长度，更进一步理解为：左连续区间的长度
                int left = map.getOrDefault(num - 1, 0);
                // right为num+1所在连续区间的长度，更进一步理解为：右连续区间的长度
                int right = map.getOrDefault(num + 1, 0);
                // 当前连续区间的总长度
                int curLen = left + right + 1;
                ans = Math.max(ans, curLen);
                // 将num加入map中，表示已经遍历过该值。其对应的value可以为任意值。
                map.put(num, -1);
                // 更新当前连续区间左边界和右边界对应的区间长度
                map.put(num - left, curLen);
                map.put(num + right, curLen);
            }
        }
        return ans;
    }
}

双指针

移动0

283. 移动零 - 力扣（LeetCode）

1
2
3
4
5
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

输入: nums = [0]
输出: [0]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void moveZeroes(int[] nums) {
        int p0 = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] != 0){
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                p0++;
            }
        }
    }
}

*盛最多水的容器

11. 盛最多水的容器 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {//如果height[l]小，无论height[r]怎么增大，area最大值取决于短板height[l]，area不会增大了，尝试++1，如果height[l]变大则还有机会
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};

*三数之和

15. 三数之和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

1.排序后双指针收缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

*接雨水

42. 接雨水 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);//左边最高的
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);//右边最高的
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

滑动窗口

*无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

*找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

固定窗口大小：p的大小

1.比较字母个数是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

2.比较方法的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];
            
            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

子串

*和为 K 的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

1
2
3
4
5
输入：nums = [1,1,1], k = 2
输出：2

输入：nums = [1,2,3], k = 3
输出：2

1.暴力枚举：两层for循环

2.前缀和+哈希表优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

*滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

输入：nums = [1], k = 1
输出：[1]

1.堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {//大顶堆（<，升序）右边的大
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

2.单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) { //窗口内升序不保留，必须是降序
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

3.分块+预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefixMax(n), suffixMax(n);
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }
            else {
                prefixMax[i] = max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            }
            else {
                suffixMax[i] = max(suffixMax[i + 1], nums[i]);
            }
        }

        vector<int> ans;
        for (int i = 0; i <= n - k; ++i) {
            ans.push_back(max(suffixMax[i], prefixMax[i + k - 1]));
        }
        return ans;
    }
};

*最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

暴力：双重循环

1.滑动窗口：使用count存储不同来优化。和【438. 找到字符串中所有字母异位词】这道题的优化思路一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public String minWindow(String s, String t) {
        //优化：通过count数组存储不同，differ维护不同字符的个数
        if(t.length() > s.length()){
            return "";
        }
        int[] count = new int[128];//存储字符个数
        int differ = 0;//s和t中不同字符的个数
        for(int i=0; i<t.length(); i++){
            char ch = t.charAt(i);
            if(count[ch] == 0){
                differ++;//不同的字符的个数
            }
            count[ch]++;
        }

        int resLeft = -1;
        int resRight = s.length();
        for(int left=0, right = 0; right<s.length(); right++){
            count[s.charAt(right)]--;
            //s中存在该字符，则缺少的个数减一；如果s中存在的字符t中不存在，这里会变成负数，不用考虑
            if(count[s.charAt(right)] == 0){
                differ--;
            }
            while(differ == 0 && left <= right){//符合要求
                if(right - left < resRight - resLeft){
                    //如果当前符合的子串更小，更新为当前子串
                    resRight = right;
                    resLeft = left;
                }
                //收缩窗口
                char ch = s.charAt(left);
                if(count[ch] == 0){
                    differ++;
                }
                count[ch]++;//收缩左端点left，则s中缺少该字符的个数加一
                left++;//收缩左端点
            }
        }

        return resLeft == -1 ? "" : s.substring(resLeft, resRight+1);
    }
}

普通数组

*最大子数组和

1
2
3
4
5
6
7
8
9
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

1.动态规划

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

2.分治：类似线段树求解最长公共上升子序列问题

线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」

*要看分治法（线段树）

合并区间

56. 合并区间 - 力扣（LeetCode）

1
2
3
4
5
6
7
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

1.先排序，看相邻的是否重合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

轮转数组

189. 轮转数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

1.额外数组

2.环状替换，考虑最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {//最大公约数
        return y > 0 ? gcd(y, x % y) : x;
    }
}

3.翻转数组：翻转所有，翻转0到k-1，翻转k到n-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

除自身以外数组的乘积（类似：接雨水）

238. 除自身以外数组的乘积 - 力扣（LeetCode）

1.左侧乘积和右侧乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        left[0] = 1;
        for(int i=1; i<nums.length; i++){//left[i]是i左侧的乘积
            left[i] = left[i-1] * nums[i-1];
        }

        int[] result = new int[nums.length];
        int R = 1;//R是右侧乘积
        for(int i=nums.length-1; i>=0; i--){
            result[i] = left[i] * R;
            R*=nums[i];
        }
        return result;
    }
}

缺失的第一个正数

41. 缺失的第一个正数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

输入：nums = [3,4,-1,1] [3,4,5,1] [-3,4,-5,-1] 返回正数下标+1
输出：2
解释：1 在数组中，但 2 没有。

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

1.tips：长度为 N的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。

方法：把不在 [1,N] 范围内的数修改成任意一个大于N的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

2.置换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);//把num[i]这个位置的数放到他对应的位置
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {//不在对应的位置，则返回
                return i + 1;
            }
        }
        return n + 1;
    }
};

矩阵

矩阵置零

73. 矩阵置零 - 力扣（LeetCode）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

1.标记数组row和col记录

法二法三没必要

螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1
2
3
4
5
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

1.模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];//存储是否访问过
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//右，下，左，上
        int directionIndex = 0;//当前方向
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;//变换方向
            }
            //修改当前位置
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}

2.按层模拟：从里到外

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

旋转图像

48. 旋转图像 - 力扣（LeetCode）

1.辅助数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }
}

2.原地旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}

3.翻转代替旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

搜索二维矩阵（*Z字形查找）

240. 搜索二维矩阵 II - 力扣（LeetCode）

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
1
2
3
4
5
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

1.直接遍历

2.二分查找（对每一行二分查找）

3.Z字形查找（从右上角开始）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            } else {
                ++x;
            }
        }
        return false;
    }
}

链表

相交链表

160. 相交链表 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

1.哈希集合（遍历A链表，哈希表存储每个节点；遍历B链表，匹配）

2.双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

*反转链表

206. 反转链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

回文链表

234. 回文链表 - 力扣（LeetCode）

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

1.将值复制到数组中后用双指针法

2.快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

环形链表（同环形链表 II）

141. 环形链表 - 力扣（LeetCode）

判断链表中是否存在环，如果链表中存在环，则返回 true 。 否则，返回 false 。

1.哈希表

2.快慢指针

*环形链表 II

142. 环形链表 II - 力扣（LeetCode）

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

1.哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

2.快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

*合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

两数相加

2. 两数相加 - 力扣（LeetCode）

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

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

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

1.计算链表长度

2.栈（全部入栈，pop N次）

3.双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

1.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;//僵尸头节点
        while (temp.next != null && temp.next.next != null) {//下两个都不为null
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

2.递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

3.按照【K 个一组翻转链表】解法，K=2。

*K 个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);//僵尸头结点
        ListNode pre = dummy;

        while(head != null){//head是下一段要翻转的链表开头
            ListNode tail = pre;//pre是上一段链表的末尾
            //查看剩余部分长度是否大于等于k
            for(int i=0; i<k; i++){
                tail = tail.next;
                if(tail == null){
                    return dummy.next;//如果剩下长度不足k，直接返回已经翻转好的链表
                }
            }

            ListNode next = tail.next;
            ListNode[] reverse = reverseK(head, tail);
            head = reverse[0];
            tail = reverse[1];
            //把翻转后的子链表重新接回原链表
            pre.next = head;
            tail.next = next;
            pre = tail;//pre是上一段链表的末尾
            head = tail.next;//head是下一段要翻转的链表开头
        }

        return dummy.next;
    }

    public ListNode[] reverseK(ListNode head, ListNode tail){
        //将[head, tail]区间内链表进行翻转

        ListNode prev = tail.next;//指向前一个结点
        ListNode p = head;//指向当前结点
        while(prev != tail){//当前一个结点指向尾结点，说明翻转结束
            ListNode next = p.next;
            p.next = prev;//翻转链表
            prev = p;
            p = next;
        }
        return new ListNode[]{tail, head};//返回翻转后新的头和尾结点
    }
}

*随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

1.回溯+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();//存储已经创建好的节点，key是存在的，value是新建的

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);//key是存在的，value是新建的
            headNew.next = copyRandomList(head.next);//递归得到
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);//返回已经创建好的节点
    }
}

2.迭代+节点拆分：将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，将其拆分为 A→A′→B→B′→C→C′。对于任意一个原节点 S，其拷贝节点 S′即为其后继节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }
}

*排序链表

148. 排序链表 - 力扣（LeetCode）

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

1.自顶向下归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        //自顶向下归并排序
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail){//区间排序（区间是[head,tail)，不包括tail）
        //递归终止条件：链表为空或者链表只包含一个结点，不需要进行拆分和排序
        if(head == null){//链表为空
            return head;
        }
        if(head.next == tail){//只包含一个节点
            head.next = null;//让每个节点断开
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail){//找到中间结点slow，分成两个链表
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode list1 = sortList(head, slow);//对两个链表分别排序
        ListNode list2 = sortList(slow, tail);
        return merge(list1, list2);
    }

    public ListNode merge(ListNode head1, ListNode head2){//合并
        ListNode dummy = new ListNode(0);//僵尸结点
        ListNode temp = dummy;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        while(temp1 != null && temp2 != null){
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        temp.next = temp1 == null ? temp2 : temp1;
        return dummy.next;
    }
}

2.自底向上归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public ListNode sortList(ListNode head) {
        //自底向上归并排序
        if(head == null){
            return head;
        }

        int length = 0;
        ListNode node = head;
        while(node != null){//计算链表长度length
            length ++;
            node = node.next;
        }

        ListNode dummyHead = new ListNode(0, head);
        for(int subLength = 1; subLength < length; subLength <<=1){
            ListNode pre = dummyHead;
            ListNode cur = dummyHead.next;

            while(cur != null){
                ListNode head1 = cur;
                for(int i=1; i<subLength && cur.next != null; i++){
                    cur = cur.next;
                }

                ListNode head2 = cur.next;
                cur.next = null;//断开第一个链表前面sublength个数
                cur = head2;
                for(int i=1; i<subLength && cur != null && cur.next != null; i++){
                    cur = cur.next;
                }

                ListNode next = null;
                if(cur != null){
                    next = cur.next;
                    cur.next = null;//断开第二个链表前面sublength个数
                }

                ListNode mergeHead = merge(head1, head2);//对两个链表进行归并排序
                pre.next = mergeHead;//连接排好序的链表
                while(pre.next != null){
                    pre = pre.next;//pre是当前排好序的链表中最后一个元素
                }
                cur = next;//next是未排序的链表第一个元素
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode head1, ListNode head2){//合并
        ListNode dummy = new ListNode(0);//僵尸结点
        ListNode temp = dummy;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        while(temp1 != null && temp2 != null){
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        temp.next = temp1 == null ? temp2 : temp1;
        return dummy.next;
    }
}

合并 K 个升序链表

23. 合并 K 个升序链表 - 力扣（LeetCode）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

1.顺序合并：遍历链表，每次合并两个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

2.分治合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

3.优先队列合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {//小顶堆，>，降序
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));//把队首放入队列
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}

*LRU 缓存

146. LRU 缓存 - 力扣（LeetCode）

1.哈希表+双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class LRUCache{
    //哈希表+双向链表实现
    class DlinkedNode{
        int key;
        int value;
        DlinkedNode prev;
        DlinkedNode next;

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

    private Map<Integer, DlinkedNode> cache = new HashMap<>();//维护出现在链表的结点
    private int size;//哈希表大小
    private int capacity;//容量
    private DlinkedNode head, tail;//需要头结点和尾结点

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        //使用伪头部结点和伪尾部结点
        head = new DlinkedNode();
        tail = new DlinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DlinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }

        //如果key存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DlinkedNode node = cache.get(key);
        if(node == null){
            //如果key不存在，创建新结点，并插入
            DlinkedNode newNode = new DlinkedNode(key, value);
            //添加进哈希表
            cache.put(key, newNode);
            //添加进双向链表的头部
            addToHead(newNode);
            size++;
            if(size > capacity){
                //如果超出容量，删除双向链表的尾部结点
                DlinkedNode tail = removeTail();
                //删除哈希表中对应的项
                cache.remove(tail.key);
                size--;
            }
        }else{
            //如果key存在，通过哈希表cache定位，修改value，放入头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DlinkedNode node){//将新结点添加到头部
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DlinkedNode node){//删除结点
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DlinkedNode node){//将存在的结点移到头部
        removeNode(node);//删除该结点
        addToHead(node);//再将该节点移到头部
    }

    private DlinkedNode removeTail(){//删除最久未访问的结点
        DlinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

2.继承LinkedHashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {//移除最老的
        return size() > capacity; 
    }
}

二叉树

*二叉树的中序遍历（Morris 中序遍历）

94. 二叉树的中序遍历 - 力扣（LeetCode）

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

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

2.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;//一直找最左边的节点
            }
            root = stk.pop();//最左边的节点（该节点肯定没有左节点）
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

3.Morris 中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode predecessor = null;

        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}

二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

1.深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

2.广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();//当前队列长度就是当前层的节点数
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}

翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

给你一个二叉树的根节点 root ， 检查它是否轴对称。

1.层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        //用层次遍历来判断
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            int sz = deque.size();
            while(sz > 0){
                root = deque.poll();
                if(root != null) deque.offer(root.left);
                if(root != null) deque.offer(root.right);
                if(root != null){
                    list.add(root.val);
                }else {
                    list.add(-101);
                }
                sz--;
            }
            for(int i=0,j=list.size()-1; i<list.size()/2; i++,j--){
                System.out.println(list.get(i)+ " " +list.get(j));
                if(list.get(i) != list.get(j)){
                    return false;
                }
            }
            list.clear();
        }
        return true;
    }
}

2.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }
    
    public boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null){//两边都为null则对称
            return true;
        }
        if(p == null || q == null){//只有一边为null，另一边不为null，一定不对称
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

3.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    
    public boolean check(TreeNode u, TreeNode v){//使用迭代法
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(u);
        q.offer(v);
        while(!q.isEmpty()){
            u = q.poll();
            v = q.poll();
            if(u == null && v == null){//都为null说明到空结点了，是相等的
                continue;
            }
            if((u == null || v == null) || (u.val != v.val)){
                //一个为null，另一个不为null；两个都不为null，但值不一样；这些都是不对称的
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;//如果队列中相邻两个结点都相等，则对称
    }
}

*二叉树的直径

543. 二叉树的直径 - 力扣（LeetCode）

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

1.深度优先搜索：一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。

而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

知道对于该节点的左儿子向下遍历经过最多的节点数 L （即以左儿子为根的子树的深度） 和其右儿子向下遍历经过最多的节点数 R （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1 。

我们记节点 node 为起点的路径经过节点数的最大值为 d_node，那么二叉树的直径就是所有节点d_node的最大值减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);//以该节点为起点的路径经过节点数的最大值为左子树深度+右子树深度+1 
        return ans - 1;
    }
    public int depth(TreeNode node){//求该节点为根的子树的深度
        if(node == null){
            return 0;// 访问到空节点了，返回0
        }
        int L = depth(node.left);// 左儿子为根的子树的深度
        int R = depth(node.right);// 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1);// 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1;// 返回该节点为根的子树的深度
    }
}

二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

1.广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

1.中序遍历，总是选择中间位置左边的数字作为根节点。因为是有序的，直接从中间开始建树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length-1);
    }

    public TreeNode helper(int [] nums, int left, int right){//从上往下建树
        if(left > right){
            return null;
        }
        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid-1);
        root.right = helper(nums, mid+1, right);
        return root;
    }
}

2.平衡二叉树的建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = null;
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            root = insert(root, nums[i]);
            //list.clear();
            //nOrder(root, list);
            //System.out.println(Arrays.toString(list.toArray()));
        }
        return root;
    }

    static public TreeNode insert(TreeNode root, int val){
        if(root == null){
            root = new TreeNode(val, null, null);
        }else if(val < root.val){//左子树
            root.left = insert(root.left, val);
            if(getHeight(root.left) - getHeight(root.right) == 2){
                root = val < root.left.val ? rotateRight(root) : rotateLeftRight(root);
            }
        }else{//右子树
            root.right = insert(root.right, val);
            if(getHeight(root.right) - getHeight(root.left) == 2){
                root = val > root.right.val ? rotateLeft(root) : rotateRightLeft(root);
            }
        }
        return root;
    }

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

    static public TreeNode rotateLeft(TreeNode root){
        TreeNode right = root.right;
        root.right = right.left;
        right.left = root;
        return right;
    }

    static public TreeNode rotateRight(TreeNode root){
        TreeNode left = root.left;
        root.left = left.right;
        left.right = root;
        return left;
    }

    static public TreeNode rotateLeftRight(TreeNode root){
        root = rotateLeft(root.left);
        return rotateRight(root);
    }

    static public TreeNode rotateRightLeft(TreeNode root){
        root = rotateRight(root.right);
        return rotateLeft(root);
    }

}

验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 严格小于 当前节点的数。
  • 节点的右子树只包含 严格大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

2.中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
              // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }
}

二叉搜索树中第 K 小的元素

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

1.中序遍历到第K个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int kv=0;
    int kth;
    int val;

    public int kthSmallest(TreeNode root, int k) {
        kth = k;
        InOrder(root);
        return val;
    }

    public void InOrder(TreeNode node){//中序遍历到第k个
        if(node == null){
            return;
        }
        InOrder(node.left);
        if(++kv == kth){
            val = node.val;
        }
        InOrder(node.right);
    }
}

2.使用栈进行中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        //使用栈进行中序遍历
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){//左结点一定是最先遍历的结点
                stack.push(root);
                root = root.left;
            }
            //此时root为null，说明栈顶结点没有左结点
            root = stack.pop();
            //中序遍历操作；处理当前节点root
            k--;
            if(k==0){
                break;
            }
            //下一次处理右节点
            root = root.right;
        }
        return root.val;
    }
}

3.记录子树的结点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        //记录子树的结点数
        Bst bst = new Bst(root);
        return bst.kthSmallest(k);
    }
}

class Bst{
    TreeNode root;
    Map<TreeNode, Integer> nodeNum;//记录改结点子数数量

    public Bst(TreeNode root){
        this.root = root;
        this.nodeNum = new HashMap<>();
        countNodeNum(root);
    }

    // 统计以node为根结点的子树的结点数
    private int countNodeNum(TreeNode node){
        if(node == null){
            return 0;
        }
        nodeNum.put(node, 1 + countNodeNum(node.left) + countNodeNum(node.right));
        return nodeNum.get(node);
    }

    //返回二叉搜索树中第k小的元素
    public int kthSmallest(int k) {
        TreeNode node = root;
        while(node != null){
            int left = nodeNum.getOrDefault(node.left, 0);
            if(left < k-1){
                node = node.right;//第k小的数在右节点
                k = k-(left+1);
            }else if(left == k-1){
                break;//第k小的数为当前节点
            }else{
                node = node.left;//第k小的数在左节点
            }
        }
        return node.val;
    }
}

4.平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution {
    List<Integer> list = new LinkedList<>();
    public int kthSmallest(TreeNode root, int k) {
        //平衡二叉树
        InOrder(root);
        Object[] num = list.toArray();
        int[] nums = Arrays.stream(num)
                .mapToInt(obj -> Integer.parseInt(obj.toString()))
                .toArray();
        root = sortedArrayToBST(nums);

        //使用栈进行中序遍历
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){//左结点一定是最先遍历的结点
                stack.push(root);
                root = root.left;
            }
            //此时root为null，说明栈顶结点没有左结点
            root = stack.pop();
            //中序遍历操作；处理当前节点root
            k--;
            if(k==0){
                break;
            }
            //下一次处理右节点
            root = root.right;
        }
        return root.val;
    }

    public void InOrder(TreeNode root){
        if(root == null){
            return;
        }
        InOrder(root.left);
        list.add(root.val);
        InOrder(root.right);
    }

    static public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = null;
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            root = insert(root, nums[i]);
        }
        return root;
    }

    static public TreeNode insert(TreeNode root, int val){
        if(root == null){
            root = new TreeNode(val, null, null);
        }else if(val < root.val){//左子树
            root.left = insert(root.left, val);
            if(getHeight(root.left) - getHeight(root.right) == 2){
                root = val < root.left.val ? rotateRight(root) : rotateLeftRight(root);
            }
        }else{//右子树
            root.right = insert(root.right, val);
            if(getHeight(root.right) - getHeight(root.left) == 2){
                root = val > root.right.val ? rotateLeft(root) : rotateRightLeft(root);
            }
        }
        return root;
    }

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

    static public TreeNode rotateLeft(TreeNode root){
        TreeNode right = root.right;
        root.right = right.left;
        right.left = root;
        return right;
    }

    static public TreeNode rotateRight(TreeNode root){
        TreeNode left = root.left;
        root.left = left.right;
        left.right = root;
        return left;
    }

    static public TreeNode rotateLeftRight(TreeNode root){
        root = rotateLeft(root.left);
        return rotateRight(root);
    }

    static public TreeNode rotateRightLeft(TreeNode root){
        root = rotateRight(root.right);
        return rotateLeft(root);
    }
}

二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

image-20250902005340024

1.广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<Integer> res;
    public List<Integer> rightSideView(TreeNode root) {
        //广度优先搜索
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int count = q.size();
            for(int i=0; i<count; i++){//每次遍历一层（层次遍历）
                TreeNode node = q.poll();
                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
                if(i == count - 1){//每层最后一个，就是最右边的结点
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
            int depth = depthQueue.remove();

            if (node != null) {
            	// 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth.put(depth, node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth + 1);
                depthQueue.add(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}

2.深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> res;
    public List<Integer> rightSideView(TreeNode root) {
        //深度优先搜索
        res = new ArrayList<>();
        dfs(root, 0);
        return res;
    }

    public void dfs(TreeNode node, int depth){
        if(node == null) return;
        if(res.size() <= depth){
            res.add(node.val);//每层第一个达到的肯定是最右边的，加入
        }
        dfs(node.right, depth+1);
        dfs(node.left, depth+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Deque<TreeNode> nodeStack = new LinkedList<TreeNode>();
        Deque<Integer> depthStack = new LinkedList<Integer>();
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();

            if (node != null) {
            	// 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 如果不存在对应深度的节点我们才插入
                if (!rightmostValueAtDepth.containsKey(depth)) {
                    rightmostValueAtDepth.put(depth, node.val);
                }

                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}

二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

1.先序遍历（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void flatten(TreeNode root) {
        //前序遍历
        List<TreeNode> list = new ArrayList<>();
        preOrder(root, list);//按照先序遍历顺序存储结点
        for(int i=1; i<list.size(); i++){
            list.get(i-1).left = null;
            list.get(i-1).right = list.get(i);
        }
    }

    public void preOrder(TreeNode root, List<TreeNode> list){
        if(root == null){
            return;
        }
        list.add(root);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
}

2.先序遍历（迭代）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void flatten(TreeNode root) {
        //前序遍历
        List<TreeNode> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        //按照先序遍历顺序存储结点（通过迭代实现先序遍历）
        while(node != null || !stack.isEmpty()){
            while(node != null){//找到没有左孩子的结点
                list.add(node);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();//栈里面都是没有左孩子的结点
            node = node.right;
        }

        for(int i=1; i<list.size(); i++){
            list.get(i-1).left = null;
            list.get(i-1).right = list.get(i);
        }
    }
}

3.前序遍历和展开同步进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public void flatten(TreeNode root) {
        //前序遍历和展开同步进行
        if(root == null){
            return;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null;
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(pre != null){
                pre.left = null;
                pre.right = cur;
            }
            //遍历左子树之前获得左右子节点信息，存入栈内
            if(cur.right != null){//先存右节点，因为栈先访问左节点
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
            pre = cur;//上一个访问的结点
        }
    }
}

4.寻找前驱节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void flatten(TreeNode root) {
        //寻找前驱节点
        TreeNode cur = root;
        while(cur != null){
            if(cur.left != null){//有左子树才需要处理
                TreeNode next = cur.left;
                TreeNode pre = next;
                while(pre.right != null){//寻找前驱节点
                    pre = pre.right;
                }
                pre.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;//没有左子树则直接处理右节点
        }
    }
}

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

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    //递归法
    private Map<Integer, Integer> indexMap;//存储中序遍历根节点对应下标index
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<>();//构造哈希映射，快速定位根节点
        for(int i=0; i<n; i++){
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n-1, 0, n-1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
        if(preorder_left > preorder_right){
            return null;
        }

        //前序遍历中第一个节点是根节点
        int preorder_root = preorder_left;
        //在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        //建立根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //左子树节点数目
        int size_left_subtree = inorder_root - inorder_left;
        //递归构造左子树，连接到根节点
        //先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree, inorder_left, inorder_root - 1);
        //递归构造右子树，并连接到根节点
        //先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right, inorder_root+1, inorder_right);
        return root;
    }
}

2.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //递归法
    private int pre, in; // 先序和中序数组索引

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 3000 + 1);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int limit) {
        if(pre == preorder.length){
            return null;
        }
        if(inorder[in] == limit){//这里是为了控制左子树，in一直加到左子树创建结束；左子树创建结束，则下一步创建右子树
            ++in;
            return null;
        }
        int val = preorder[pre++];
        return new TreeNode(val, buildTree(preorder, inorder, val), buildTree(preorder, inorder, limit));
    }
}

路径总和 III

437. 路径总和 III - 力扣（LeetCode）

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

1.深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        //深度优先搜索
        if(root == null){
            return 0;
        }
        int ret = rootSum(root, targetSum);

        //对二叉树上每个结点求出rootSum
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, long targetSum) {//以节点root为起点向下且满足路径总和为targetSum的路径数目
        int ret = 0;
        if(root == null){
            return 0;
        }
        int val = root.val;
        if(val == targetSum){
            ret++;
        }
        ret += rootSum(root.left, targetSum-val);
        ret += rootSum(root.right, targetSum-val);
        return ret;
    }
}

2.前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        //前缀和
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);//前缀和为0的个数为1个
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long cur, int targetSum) {
        if(root == null){
            return 0;
        }
        int ret = 0;
        cur += root.val;//前缀和

        ret = prefix.getOrDefault(cur-targetSum, 0);
        prefix.put(cur, prefix.getOrDefault(cur, 0)+1);
        ret += dfs(root.left, prefix, cur, targetSum);
        ret += dfs(root.right, prefix, cur, targetSum);
        prefix.put(cur, prefix.getOrDefault(cur, 0)-1);

        return ret;
    }
}

二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1.递归：

（1）左子树和右子树均包含 p 节点或 q 节点，如果左子树包含的是 p 节点，那么右子树只能包含 q 节点，反之亦然，因为 p 节点和 q 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 x 就是我们要找的最近公共祖先。

（2）x 恰好是 p 节点或 q 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 x 就是我们要找的最近公共祖先。

题解：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归
        dfs(root, p, q);
        return res;
    }

    public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return false;
        }
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if((lson && rson) || ((root.val == p.val) || root.val == q.val) && (lson || rson)){
            res = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);//只要当前结点或其子节点存在p或q，标记为true，存在要查找的结点
    }
}

2.存储父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();//存储每个结点的父结点
    Set<Integer> visited = new HashSet<Integer>();//存储访问过的父节点

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //存储父节点
        dfs(root);
        while(p != null){
            visited.add(p.val);//记录从p开始的祖先节点
            p = parent.get(p.val);
        }
        while(q != null){
            if(visited.contains(q.val)){//最近公共祖先节点
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

    public void dfs(TreeNode root) {//存储每个结点的父结点
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
}

3.优秀题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p.val, q.val);
    }

    TreeNode find(TreeNode root, int val1, int val2) {
        if (root == null) {//如果当前节点不是p或q，返回null
            return null;
        }

        if (root.val == val1 || root.val ==val2) {//如果当前节点为p或q，返回该节点（因为先找到的一定是最深的，就是最近公共祖先节点，所以直接返回）
            return root;
        }

        TreeNode left = find(root.left, val1, val2);//从左子树找p或q节点
        TreeNode right = find(root.right, val1, val2);//从右子树找p或q节点

        if (left != null && right != null) {//若从左右子树找到了p或q节点，当前祖先即为最近公共祖先
            return root;
        }

        return left != null ? left : right;
    }
}

二叉树中的最大路径和

124. 二叉树中的最大路径和 - 力扣（LeetCode）

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

image-20250902013020016

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        //递归
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if(node == null){
            return 0;
        }

        //递归计算左右子节点的最大贡献值
        //只有在最大贡献值大于0时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        //节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        //更新最大值
        maxSum = Math.max(maxSum, priceNewpath);//最大子路径和

        //返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

图论

岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

1.深度优先搜索：如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。最终岛屿的数量就是进行深度优先搜索的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';//遍历过修改为0
        dfs(grid, r - 1, c);//上
        dfs(grid, r + 1, c);//下
        dfs(grid, r, c - 1);//左
        dfs(grid, r, c + 1);//右
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

2.广度优先搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {//广度优先搜索
                    ++num_islands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {//上
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {//下
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {//左
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {//右
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
}

3.并查集：扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。

最终岛屿的数量就是并查集中连通分量的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
    class UnionFind{
        int count;
        int[] parent;//并查集
        int[] rank;//rank值高的作为该并查集的根节点

        public UnionFind(char[][] grid){
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m*n];
            rank = new int[m*n];
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(grid[i][j] == '1'){
                        parent[i * n + j] = i * n + j;//注意这里是i*n，不是i*m，因为每行有n个数
                        count++;//count为1的个数，也就是当前连通分量个数，即并查集个数
                    }
                    rank[i*n + j] = 0;//每个位置的rank都是0
                }
            }
        }

        public int find(int i){
            if(parent[i] != i) parent[i] = find(parent[i]);//查找的过程中，将路上的每个结点的父节点都修改为根节点
            return parent[i];
        }

        public void union(int x, int y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx != rooty){//两个结点不在同一个集合，则合并
                if(rank[rootx] > rank[rooty]){//将父节点统一为rank值大的那个
                    parent[rooty] = rootx;
                }else if(rank[rootx] < rank[rooty]){
                    parent[rootx] = rooty;
                }else{//一开始大家rank都一样，这里将左边的rootx作为rank大的那一个
                    parent[rooty] = rootx;
                    rank[rootx] ++;//rootx的rank增大
                }
                count--;//合并之后，联通分量就变少一个，也就是并查集会变少一个
            }
        }
    }

    public int numIslands(char[][] grid) {//二维数组（图）的深度优先搜索
        if(grid == null || grid.length == 0){
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for(int i=0; i<nr; i++){
            for(int j=0; j<nc; j++){
                if(grid[i][j] == '1'){
                    grid[i][j] = '0';

                    //访问上下左右的位置，将同一岛屿的加入并查集
                    if(i - 1 >= 0 && grid[i - 1][j] == '1'){
                        uf.union(i * nc + j, (i - 1) * nc + j);
                    }
                    if(i + 1 < nr && grid[i + 1][j] == '1'){
                        uf.union(i * nc + j, (i + 1) * nc + j);
                    }
                    if(j - 1 >= 0 && grid[i][j - 1] == '1'){
                        uf.union(i * nc + j, i* nc + j - 1);
                    }
                    if(j + 1 < nc && grid[i][j + 1] == '1'){
                        uf.union(i * nc + j, i* nc + j + 1);
                    }
                }
            }
        }
        return uf.count;
    }
}

腐烂的橘子

994. 腐烂的橘子 - 力扣（LeetCode）

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

1
2
3
4
5
6
7
8
9
10
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

1.多源广度优先搜索：从多个源头开始广度优先搜索（一开始队列多个源头节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {//把腐烂的结点都放入队列
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {//腐烂四个方向
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }
        for (int[] row: grid) {
            for (int v: row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}

课程表

207. 课程表 - 力扣（LeetCode）

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

1.深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {//统计后置课程：从 u 出发通过一条有向边可以到达的所有节点（出度）
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int u) {
        visited[u] = 1;//访问中
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {//未访问
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {//访问中
                valid = false;
                return;
            }
        }
        visited[u] = 2;//访问结束
    }
}

2.广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    List<List<Integer>> edges;
    int[] indeg;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];//统计入度
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        int visited = 0;
        while (!queue.isEmpty()) {
            ++visited;
            int u = queue.poll();
            for (int v: edges.get(u)) {
                --indeg[v];
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return visited == numCourses;
    }
}

*实现 Trie (前缀树)

208. 实现 Trie (前缀树) - 力扣（LeetCode）

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Trie {
    private Trie[] children;//存储字母
    private boolean isEnd;//是否是一个单词的末尾
    
    public Trie() {
        children = new Trie[26];//一共有26个字母
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for(int i=0; i<word.length(); i++){
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;//以该字母为结尾
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix){
        Trie node = this;
        for(int i=0; i<prefix.length(); i++){
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null){
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

*除法求值

399. 除法求值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

1.并查集

题解链接：399. 除法求值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class UnionFind{
public:
    vector<int> parent;
    vector<double> weight;//指向父节点的权值（父是分子）

    UnionFind(int n){
        parent.resize(n);
        weight.resize(n);
        for(int i=0; i<n; i++){
            parent[i] = i;
            weight[i] = 1.0;
        }
    }

    void Union(int x, int y, double value){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY){
            return;
        }

        parent[rootX] = rootY;
        weight[rootX] = weight[y]*value/weight[x];
    }

    // 修改为递归实现的路径压缩
    int find(int x) {
        if (parent[x] != x) {
            int origin = parent[x];
            parent[x] = find(parent[x]);
            weight[x] *= weight[origin];
        }
        return parent[x];
    }


    double isConnected(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY){//路径压缩之后，x和y肯定直接连接父亲节点
            return weight[x]/weight[y];
        }else{
            return -1.0;
        }
    }
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int n = equations.size();
        UnionFind* uf = new UnionFind(2*n);

        unordered_map<string, int> map;
        int index = 0;//区分不同字母
        for(int i=0; i<n; i++){
            string s1 = equations[i][0];
            string s2 = equations[i][1];

            if(!map.contains(s1)){
                map[s1] = index;
                index++;
            }

            if(!map.contains(s2)){
                map[s2] = index;
                index++;
            }

            uf->Union(map[s1], map[s2], values[i]);
        }

        vector<double> res(queries.size());
        for(int i=0; i<queries.size(); i++){
            string s1 = queries[i][0];
            string s2 = queries[i][1];

            if(!map.contains(s1) || !map.contains(s2)){
                res[i] = -1.0;
                continue;
            }

            int index1 = map[s1];
            int index2 = map[s2];

            res[i] = uf->isConnected(index1, index2);
        }
        return res;
    }
};

二分查找

*搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

1
2
3
4
5
6
7
8
输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 7
输出: 4

1.目标：在一个有序数组中找第一个大于等于 target 的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = (left+right)>>1;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

*搜索二维矩阵（同上矩阵部分）

74. 搜索二维矩阵 - 力扣（LeetCode）

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

1
2
3
4
5
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

1.两次二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

2.一次二分查找：将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

1
2
3
4
5
6
7
8
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

输入：nums = [], target = 0
输出：[-1,-1]

1.二分查找：数组中「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）。

寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标

寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] searchRange(int[] nums, int target) {
        //「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {//找左边的加上等于号
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

*搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

1
2
3
4
5
6
7
8
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

输入：nums = [1], target = 0
输出：-1

1.二分查找：从中间分开，两边肯定有一边是有序的，根据是否有序判断。

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {//左边有序
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {//右边有序
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

*寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

1.二分查找：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){//当left = right，就是最小值
            int mid = (left + right) / 2;
            if(nums[mid] < nums[right]){//说明mid到right区间递增，最小值在mid左边
                right = mid; //注意，有可能mid就是最小值
            }else {//说明mid到right区间有最小值
                left = mid + 1;//mid大于left，mid肯定不是最小值，所以left=mid+1而不是left=mid
            }
        }
        return nums[left];
    }
}

*寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

1
2
3
4
5
6
7
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

1.二分查找：找第k小的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //二分查找
        int totalLen = nums1.length + nums2.length;//合并后数组的总长度
        if(totalLen % 2 == 1){//奇数
            int midIndex = totalLen / 2;
            return getKthElement(nums1, nums2, midIndex + 1);//第midIndex+1的数是中位数
        }else{//偶数
            int midIndex = totalLen / 2;
            return (getKthElement(nums1, nums2, midIndex) + getKthElement(nums1, nums2, midIndex + 1)) / 2.0;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k){//寻找第k小的数
        int index1 = 0;
        int index2 = 0;
        int kth = 0;
        while(true){
            //边界
            if(index1 == nums1.length){
                return nums2[index2 - 1 + k];//nums1到达边界，从num2中找第k小
            }
            if(index2 == nums2.length){
                return nums1[index1 - 1 + k];//nums2到达边界，从num1中找第k小
            }
            if(k == 1){
                return Math.min(nums1[index1], nums2[index2]);
            }

            //正常
            int half = k/2;
            int newIndex1 = Math.min(index1 + half, nums1.length) - 1;
            int newIndex2 = Math.min(index2 + half, nums2.length) - 1;
            int p1 = nums1[newIndex1];
            int p2 = nums2[newIndex2];
            if(p1 <= p2){
                k = k - (newIndex1 - index1 + 1);//排除从index1到newIndex1之间的数
                index1 = newIndex1 + 1;//只动index1
            }else{
                k = k - (newIndex2 - index2 + 1);//排除从index2到newIndex2之间的数
                index2 = newIndex2 + 1;//只动index2
            }
        }
    }
}

2.划分数组（复杂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);

            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}

回溯

全排列

46. 全排列 - 力扣（LeetCode）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

1
2
3
4
5
6
7
8
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

1.回溯

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

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

2.dfs（回溯）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    int[] vis;//标记该位置访问过的次数
    List<Integer> path = new ArrayList<>();//每次的全排列

    void dfs(List<List<Integer>> res, int[] nums, int x){
        if(x >= nums.length){
            List<Integer> list = new ArrayList<>(path);
            res.add(list);
            return;
        }
        for(int i=0; i<nums.length; i++){//每次dfs都会遍历所有的数，如果没被访问过就加入path
            if(vis[i]>0) continue;//如果已经被访问过，表示之前已经加入path中
            vis[i]++;
            path.add(nums[i]);
            dfs(res, nums, x+1);
            vis[i]--;
            path.remove(path.size()-1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        vis = new int[nums.length];
        dfs(res, nums, 0);
        //System.out.println(res);
        return res;
    }
}

组合

77. 组合 - 力扣（LeetCode）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

输入：n = 1, k = 1
输出：[[1]]

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k)  {
        List<Integer> list1 = new ArrayList<>();
        dfs(list1, 0, 0, k, n);
        return list;
    }

    void dfs(List<Integer> list1, int next, int depth, int k, int n) {
        if(depth == k) {
            List<Integer> list2 = new ArrayList<>(list1);
            list.add(list2);
            return;
        }
        for(int i = next; i < n; i++) {
            list1.add(i+1);
            dfs(list1, i + 1, depth+1, k, n);
            list1.remove(list1.size() - 1);
        }
    }
}

子集

78. 子集 - 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

1
2
3
4
5
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        //只有放入和不放入两种情况
        t.add(nums[cur]);//放入
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);//不放入
        dfs(cur + 1, nums);
    }
}

2.迭代法实现子集枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1
2
3
4
5
6
7
8
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

1.回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

组合总和

39. 组合总和 - 力扣（LeetCode）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

1
2
3
4
5
6
7
8
9
10
11
12
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

输入: candidates = [2], target = 1
输出: []

1.回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();//最终结果
        List<Integer> combine = new ArrayList<Integer>();//候选结果

        dfs(candidates, target, res, combine, 0);
        return res;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> combine, int idx){
        if(idx == candidates.length){//当所有数字遍历完，结束遍历
            return;
        }
        if(target == 0){//target为0说明当前combine候选结果满足条件
            res.add(new ArrayList<Integer>(combine));
            return;
        }
        //不选择索引为idx的值，则直接进入下一个
        dfs(candidates, target, res, combine, idx+1);
        //选择索引为idx的值，则target变为target-candidates[idx]
        if(target - candidates[idx] >= 0){
            combine.add(candidates[idx]);
            dfs(candidates, target-candidates[idx], res, combine, idx);
            combine.remove(combine.size()-1);
        }
    }
}

2.回溯（其他写法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> ans = new ArrayList<>();

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

    void find(List list, int leftValue, int index, int[] candidates) {
        if (leftValue == 0) {//这个是根据剩下的target判断是否进行遍历
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = index; i < candidates.length; i++) {//尝试将每个数字都加进去
            if (leftValue >= candidates[i]) {
                list.add(candidates[i]);
                find(list, leftValue - candidates[i], i, candidates);
                list.remove(list.size() - 1);
            }
        }
    }
}

括号生成

22. 括号生成 - 力扣（LeetCode）

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

1
2
3
4
5
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

1.暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<String> generateParenthesis(int n) {
        //暴力法
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2*n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result){
        if(pos == current.length){//生成括号
            if(valid(current)){
                result.add(new String(current));
            }
        }else{
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }

    public boolean valid(char[] current){//校验括号是否合法
        int balance = 0;
        for(char c: current){
            if(c == '('){
                balance++;
            }else{
                balance--;
            }
            if(balance < 0){
                return false;
            }
        }
        return balance == 0;
    }
}

2.回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<String> generateParenthesis(int n) {
        //回溯法
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    public void backtrack(List<String> res, StringBuilder cur, int open, int close, int max){
        //如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号
        //open是左括号数量，close是右括号数量
        if(cur.length() == max*2){
            res.add(cur.toString());
            return;
        }
        if(open < max){
            cur.append('(');
            backtrack(res, cur, open+1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if(close < open){
            cur.append(')');
            backtrack(res, cur, open, close+1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

3.按括号序列的长度递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    ArrayList[] cache = new ArrayList[100];//存储长度为2*i的有效括号
 
    public List<String> generateParenthesis(int n) {
        //按括号序列的长度递归
        return generate(n);
    }

    public List<String> generate(int n){
        if(cache[n] != null){
            return cache[n];//长度为2*n的有效括号列表
        }
        ArrayList<String> res = new ArrayList<>();
        if(n == 0){
            res.add("");
        }else{
            for(int c=0; c<n; c++){
                for(String left : generate(c)){//0 1 ... n-2 n-1
                    for(String right : generate(n-1-c)){//n-1 n-2 ... 1 0
                        res.add("(" + left + ")" + right);//left和right加起来n-1对个括号，加上这里的一对，共n对括号
                    }
                }
            }
        }
        cache[n] = res;//存储长度为2*n的有效括号
        return res;
    }
}

单词搜索

79. 单词搜索 - 力扣（LeetCode）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public boolean exist(char[][] board, String word) {
        //回溯
        int h = board.length;
        int w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(check(board, visited, i, j, word, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k){
        if(board[i][j] != s.charAt(k)){//不相等则不用判断
            return false;
        }else if(k == s.length() - 1){//相等，且长度满足
            return true;
        }

        visited[i][j] = true;//标记为已访问
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;

        for(int[] dir : directions){
            int newi = i+dir[0];
            int newj = j+dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if(!visited[newi][newj]){
                    if(check(board, visited, newi, newj, s, k+1)){
                        result = true;
                        break;
                    }
                }
            }
        }

        visited[i][j] = false;//标记为未访问
        return result;
    }
}

分割回文串

131. 分割回文串 - 力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

1
2
3
4
5
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

1.回溯 + 动态规划预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    boolean[][] f;
    public List<List<String>> partition(String s) {
        //回溯 + 动态规划预处理
        List<List<String>> res = new ArrayList<>();
        List<String> current = new ArrayList<>();
        f = new boolean[s.length()][s.length()];//f存储以i为开头，以j为结尾的字符串是回文字符串
        for (int i = 0; i < s.length(); ++i) {
            Arrays.fill(f[i], true);
        }

        for(int i=s.length()-1; i>=0; i--){
            for(int j=i+1; j<s.length(); j++){
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i+1][j-1];
            }
        }

        dfs(res, current, s, 0);
        return res;
    }

    public void dfs(List<List<String>> res, List<String> current,String s, int i){
        if(i == s.length()){
            res.add(new ArrayList<>(current));
            return;
        }
        for(int j=i; j<s.length(); j++){
            if(f[i][j]){//以i为开头，以j为结尾的字符串是回文字符串
                current.add(s.substring(i,j+1));//是回文字符串，加入当前答案中
                dfs(res, current, s, j+1);
                current.remove(current.size()-1);//移除，回溯
            }
        }
    }
}

2.回溯 + 记忆化搜索（和题解1思路一样，只是生成f的方式不一样）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    int[][] f;
    public List<List<String>> partition(String s) {
        //回溯 + 记忆化搜索
        List<List<String>> res = new ArrayList<>();
        List<String> current = new ArrayList<>();
        f = new int[s.length()][s.length()];

        dfs(res, current, s, 0);
        return res;
    }

    public void dfs(List<List<String>> res, List<String> current,String s, int i){
        if(i == s.length()){
            res.add(new ArrayList<>(current));
            return;
        }
        for(int j=i; j<s.length(); j++){
            if(isPalindrome(s, i, j) == 1){//以i为开头，以j为结尾的字符串是回文字符串
                current.add(s.substring(i,j+1));//是回文字符串，加入当前答案中
                dfs(res, current, s, j+1);
                current.remove(current.size()-1);//移除，回溯
            }
        }
    }

    // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
    public int isPalindrome(String s, int i, int j) {
        if (f[i][j] != 0) {
            return f[i][j];
        }
        if (i >= j) {
            f[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            f[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
            f[i][j] = -1;
        }
        return f[i][j];
    }
}

N皇后

51. N 皇后 - 力扣（LeetCode）

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

1.基于集合的回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        int [] queens = new int[n];//每一行皇后所在位置
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();
        backtrack(res, queens, n, 0, columns, diagonals1, diagonals2);
        return res;
    }

    public void backtrack(List<List<String>> res, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if(row == n){//row代表当前行，若为n表示遍历完成
            List<String> board = generateBoard(queens, n);
            res.add(board);
            return;
        }

        for(int i=0; i<n; i++){
            if(columns.contains(i)){
                continue;//该列存在皇后，返回
            }
            if(diagonals1.contains(row-i)){//row是当前行，i是当前列
                continue;//左上到右下方向斜线满足行-列之差相等
            }
            if(diagonals2.contains(row+i)){//row是当前行，i是当前列
                continue;//右上到左下方向斜线满足行+列之和相等
            }
            queens[row] = i;//符合条件，放置皇后
            columns.add(i);//所在列
            diagonals1.add(row-i);//左上到右下方向斜线
            diagonals2.add(row+i);//右上到左下方向斜线
            backtrack(res, queens, n, row+1, columns, diagonals1, diagonals2);
            columns.remove(i);
            diagonals1.remove(row-i);
            diagonals2.remove(row+i);
        }
    }

    public List<String> generateBoard(int[] queens, int n) {//生成答案
        List<String> board = new ArrayList<>();
        for(int i=0; i<n; i++){
            char[] row = new char[n];
            Arrays.fill(row, '.');//默认是.
            row[queens[i]] = 'Q';//修改对应位置为皇后
            board.add(new String(row));
        }
        return board;
    }
}

2.基于位运算的回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        int [] queens = new int[n];//每一行皇后所在位置
        Arrays.fill(queens, -1);
        backtrack(res, queens, n, 0, 0, 0, 0);
        return res;
    }

    public void backtrack(List<List<String>> res, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
        if(row == n){//row代表当前行，若为n表示遍历完成
            List<String> board = generateBoard(queens, n);
            res.add(board);
            return;
        }

        int pos = ((1<<n)-1) & (~(columns | diagonals1 | diagonals2));
        while(pos != 0){
            int position = pos & (-pos);//获得pos二进制表示中最低位1的位置
            pos = pos & (pos-1);//将pos二进制中最低位1置为0
            int column = Integer.bitCount(position-1);
            queens[row] = column;
            backtrack(res, queens, n, row+1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);//该位置放置皇后
            queens[row] = -1;
        }

    }

    public List<String> generateBoard(int[] queens, int n) {//生成答案
        List<String> board = new ArrayList<>();
        for(int i=0; i<n; i++){
            char[] row = new char[n];
            Arrays.fill(row, '.');//默认是.
            row[queens[i]] = 'Q';//修改对应位置为皇后
            board.add(new String(row));
        }
        return board;
    }
}

栈

有效的括号

20. 有效的括号 - 力扣（LeetCode）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：s = "()"
输出：true

输入：s = "()[]{}"
输出：true

输入：s = "(]"
输出：false

输入：s = "([])"
输出：true

输入：s = "([)]"
输出：false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

最小栈

155. 最小栈 - 力扣（LeetCode）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

1.辅助栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<>();
        minStack  = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        xStack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

*字符串解码

394. 字符串解码 - 力扣（LeetCode）

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

1
2
3
4
5
6
7
8
9
10
11
输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

1.栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;

        while (ptr < s.length()) {
            char cur = s.charAt(ptr);//当前字符
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }

        return getString(stk);
    }

    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

2.递归（复杂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    String src;
    int ptr;

    public String decodeString(String s) {
        src = s;
        ptr = 0;
        return getString();
    }

    public String getString() {
        if (ptr == src.length() || src.charAt(ptr) == ']') {
            // String -> EPS
            return "";
        }

        char cur = src.charAt(ptr);
        int repTime = 1;
        String ret = "";

        if (Character.isDigit(cur)) {
            // String -> Digits [ String ] String
            // 解析 Digits
            repTime = getDigits(); 
            // 过滤左括号
            ++ptr;
            // 解析 String
            String str = getString(); 
            // 过滤右括号
            ++ptr;
            // 构造字符串
            while (repTime-- > 0) {
                ret += str;
            }
        } else if (Character.isLetter(cur)) {
            // String -> Char String
            // 解析 Char
            ret = String.valueOf(src.charAt(ptr++));
        }
        
        return ret + getString();
    }

    public int getDigits() {
        int ret = 0;
        while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
            ret = ret * 10 + src.charAt(ptr++) - '0';
        }
        return ret;
    }
}

每日温度

739. 每日温度 - 力扣（LeetCode）

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

输入: temperatures = [30,60,90]
输出: [1,1,0]

1.暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        for (int i = length - 1; i >= 0; --i) {
            int warmerIndex = Integer.MAX_VALUE;
            for (int t = temperatures[i] + 1; t <= 100; ++t) {
                //温度的范围是[30,100]，找比temperatures[i]大的数的下标
                if (next[t] < warmerIndex) {//找最近的下标
                    warmerIndex = next[t];
                }
            }
            if (warmerIndex < Integer.MAX_VALUE) {
                ans[i] = warmerIndex - i;
            }
            next[temperatures[i]] = i;//当前温度出现的下标
        }
        return ans;
    }
}

2.单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();//单调栈，栈底到栈顶递减
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                //如果当前temperature大于栈顶，一直弹
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);//每个坐标都会入栈
        }
        return ans;
    }
}

*柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
4
5
6
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

输入： heights = [2,4]
输出： 4

1.暴力法：

（1）枚举宽：使用两重循环枚举矩形的左右边界以固定宽度 w，此时矩形的高度 h，就是所有包含在内的柱子的「最小高度」，对应的面积为 w×h。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int ans = 0;
        // 枚举左边界
        for (int left = 0; left < n; ++left) {
            int minHeight = INT_MAX;
            // 枚举右边界
            for (int right = left; right < n; ++right) {
                // 确定高度
                minHeight = min(minHeight, heights[right]);
                // 计算面积
                ans = max(ans, (right - left + 1) * minHeight);
            }
        }
        return ans;
    }
};

（2）枚举高：使用一重循环枚举某一根柱子，将其固定为矩形的高度 h。随后从这跟柱子开始向两侧延伸，直到遇到高度小于 h 的柱子，就确定了矩形的左右边界。如果左右边界之间的宽度为 w，那么对应的面积为 w×h。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int ans = 0;
        for (int mid = 0; mid < n; ++mid) {//遍历数组，枚举高
            // 枚举高
            int height = heights[mid];
            int left = mid, right = mid;
            // 确定左右边界
            while (left - 1 >= 0 && heights[left - 1] >= height) {
                --left;
            }
            while (right + 1 < n && heights[right + 1] >= height) {
                ++right;
            }
            // 计算面积
            ans = max(ans, (right - left + 1) * height);
        }
        return ans;
    }
};

2.单调栈：枚举高，单调栈找出左边界和右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {//找到高度小于heights[i]的
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {//找到高度小于i的
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {//枚举高
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

3.单调栈+常数优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);

        Deque<Integer> stack = new LinkedList<Integer>();//栈里面单增（包含等于）
        for(int i=0; i<heights.length; i++){
            while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                right[stack.peek()] = i;
                stack.pop();
            }
            //此时栈里面的值一定小于height[i]
            left[i] = stack.isEmpty() ? -1 : stack.peek();//栈顶一定小于height[i]
            stack.push(i);//栈里存下标
        }

        int res = 0;
        for(int i=0; i<heights.length; i++){
            res = Math.max(res, (right[i]-left[i]-1)*heights[i] );
        }
        return res;
    }
}

堆

数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
输入: [3,2,1,5,6,4], k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

1.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int quickselect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }
    public int findKthLargest(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }
}

2.堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

前 K 个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

1
2
3
4
5
6
7
8
9
10
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]


输入：nums = [1], k = 1
输出：[1]


输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]

1.堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num:nums){//统计每个数出现的频率
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] m, int[] n){
                return m[1]-n[1];
            }
        });//使用小顶堆，淘汰出现次数少的，留下出现次数多的

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int num = entry.getKey();
            int count = entry.getValue();
            if(queue.size() == k){
                if(queue.peek()[1] < count){//出现频率小
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            }else{
                queue.offer(new int[]{num, count});
            }
        }

        int res[] = new int[k];
        for(int i=0; i<k; i++){
            res[i] = queue.poll()[0];
        }
        return res;
    }
}

2.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num:nums){//统计每个数出现的频率
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        //获取每个数字出现次数
        List<int[]> values = new ArrayList<int[]>();
        for(Map.Entry<Integer, Integer> entry:map.entrySet()){
            int num = entry.getKey();
            int count = entry.getValue();
            values.add(new int[]{num, count});
        }
        int res[] = new int[k];
        qsort(values, 0, values.size() - 1, res, 0, k);//快排
        return res;//可以按照任意顺序返回topK
    }

    public void qsort(List<int[]> values, int start, int end, int[] res, int resIndex, int k) {
        int pivot = values.get(start)[1];
        int index = start;
        for(int i=start+1; i<=end; i++){
            //双指针：大于等于基准值的放到左边，小于基准值的放到右边
            if(values.get(i)[1] >= pivot){
                Collections.swap(values, index+1, i);
                index++;
            }
        }
        Collections.swap(values, start, index);

        if(k <= index-start){
            //前k大值在左侧子数组
            qsort(values, start, index-1, res, resIndex, k);
        }else{
            //前k大值等于左侧子数组全部元素 + 右侧子数组前k-(index-start+1)大的值
            for (int i = start; i <= index; i++) {
                res[resIndex++] = values.get(i)[0];
            }
            if (k > index - start + 1) {
                qsort(values, index + 1, end, res, resIndex, k - (index - start + 1));
            }
        }
    }
}

数据流的中位数

295. 数据流的中位数 - 力扣（LeetCode）

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

1.优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MedianFinder {
    //优先队列
    PriorityQueue<Integer> queMin;//小于等于中位数（大顶堆）
    PriorityQueue<Integer> queMax;//大于中位数（小顶堆）

    public MedianFinder() {
        queMin = new PriorityQueue<Integer>((a,b) -> (b-a));//大顶堆
        queMax = new PriorityQueue<Integer>((a,b) -> (a-b));//小顶堆
    }
    
    public void addNum(int num) {
        if(queMin.isEmpty() || num <= queMin.peek()){
            queMin.offer(num);
            if(queMin.size() > queMax.size()+1){
                queMax.offer(queMin.poll());
            }
        }else{
            queMax.offer(num);
            if(queMax.size() > queMin.size()){
                queMin.offer(queMax.poll());
            }
        }
    }
    
    public double findMedian() {
        if(queMin.size() > queMax.size()){
            return queMin.peek();
        }
        return (queMax.peek() + queMin.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

2.有序集合+双指针（复杂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class MedianFinder {
    //有序集合
    TreeMap<Integer, Integer> nums;//key为数，value为数出现的次数
    int n;//数组总大小
    int[] left;//左指针
    int[] right;//右指针

    public MedianFinder() {
        nums = new TreeMap<Integer, Integer>();
        n = 0;
        left = new int[2];//下标0表示数，下标1表示重复出现的该数中第几个
        right = new int[2];
    }
    
    public void addNum(int num) {
        nums.put(num, nums.getOrDefault(num, 0) + 1);
        if(n==0){
            left[0] = right[0] = num;
            left[1] = right[1] = 1;
        }else if(n%2 != 0){//奇数，插入后为偶数
            if(num < left[0]){//小于中位数，左指针左移
                decrease(left);
            }else{//大于或等于中位数，右指针右移
                increase(right);
            }
        }else{//偶数，插入后为奇数
            if(num > left[0] && num < right[0]){//插入后成为中位数，左指针右移，右指针左移
                increase(left);
                decrease(right);
            }else if(num >= right[0]){//大于或等于右指针，左指针右移
                increase(left);
            }else{//小于右指针，右指针左移，左指针和右指针指向一致
                decrease(right);
                System.arraycopy(right, 0, left, 0, 2);
            }
        }
        n++;//数组大小增加
    }
    
    public double findMedian() {
        return (left[0] + right[0]) / 2.0;
    }

    public void increase(int[] iterator) {
        iterator[1]++;
        if (iterator[1] > nums.get(iterator[0])) {
            iterator[0] = nums.ceilingKey(iterator[0] + 1);
            iterator[1] = 1;
        }
    }

    public void decrease(int[] iterator) {
        iterator[1]--;
        if (iterator[1] == 0) {
            iterator[0] = nums.floorKey(iterator[0] - 1);
            iterator[1] = nums.get(iterator[0]);
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

贪心

买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int min = prices[0];
        for(int i=1; i<prices.length; i++){
            res = Math.max(res, prices[i]-min);
            min = prices[i] < min ? prices[i] : min;
        }
        return res;
    }
}

跳跃游戏

55. 跳跃游戏 - 力扣（LeetCode）

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canJump(int[] nums) {
        //贪心
        //遍历一次数组，更新每个位置最远可以到达的位置
        int max=0;
        for(int i=0; i<nums.length; i++){
            if(i<=max){//i如果大于max，说明i当前是不可达的
                max = Math.max(i+nums[i], max);//i可达，更新最远可以到达的位置
                if(max >= nums.length - 1){
                    return true;
                }
            }
        }
        return false;
    }
}

跳跃游戏 II

45. 跳跃游戏 II - 力扣（LeetCode）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

1
2
3
4
5
6
7
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

输入: nums = [2,3,0,1,4]
输出: 2

1.正向遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int jump(int[] nums) {
        int step = 0;
        int max = 0;
        int end = 0;
        for(int i=0; i<nums.length-1; i++){
            max = Math.max(max, i+nums[i]);//max是从当前i能跳到的最远的地方
            if(i == end){//到达上一个起跳点能到的最远距离
                end = max;//end更新为：能到的最远距离
                step++;//步数+1
            }
        }
        return step;
    }
}

2.反向遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        //反向查找出发位置（双重循环）
        int position = nums.length - 1;
        int step = 0;
        while(position > 0){
            for(int i=0; i<position; i++){
                if(nums[i] + i >= position){//当前位置能到达position
                    position = i;//找下一个能到达当前位置的
                    step ++ ;
                    break;
                }
            }
        }
        return step;
    }
}

划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

1
2
3
4
5
6
7
8
9
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

输入：s = "eccbbbbdec"
输出：[10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> partitionLabels(String s) {
        //贪心：寻找每个片段可能的最小结束下标
        int[] last = new int[26];
        for(int i=0; i<s.length(); i++){//遍历得到当前字母的最后一次出现的下标
            last[s.charAt(i) - 'a'] = i;
        }
        int start = 0;
        int end = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<s.length(); i++){
            end = Math.max(end, last[s.charAt(i) - 'a']);//当前字母最远达到的地方
            if(i == end){//到达当前片段字母最远的地方
                list.add(end - start + 1);
                start = end + 1;//从当前结束的地方下一个位置开始
            }
        }
        return list;
    }
}

动态规划

爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

动态规划（斐波那契数列）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

1
2
3
4
5
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

输入: numRows = 1
输出: [[1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }
}

打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
5
6
7
8
9
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        //dp[i] 表示前i间房屋能偷窃到的最高总金额
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

*完全平方数

279. 完全平方数 - 力扣（LeetCode）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

1
2
3
4
5
6
7
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

输入：n = 13
输出：2
解释：13 = 4 + 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        //动态规划
        int[] f = new int[n+1];//f[i]表示最少需要多少个数的平方表示i
        for(int i=1; i<=n; i++){
            int minn = Integer.MAX_VALUE;
            for(int j=1; j*j<=i; j++){//这些数肯定落在区间 [1,根号i]
                minn = Math.min(minn, f[i-j*j]);
            }
            f[i] = minn+1;
        }
        return f[n];
    }
}

*零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

1
2
3
4
5
6
7
8
9
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

1.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        //dp[i]为为组成金额 i 所需最少的硬币数量
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//加1表示coins[j]这枚硬币的数量
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

2.记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {//相当于dfs递归（回溯）
        if (rem < 0) {
            return -1;
        }
        if (rem == 0) {
            return 0;
        }
        if (count[rem - 1] != 0) {
            return count[rem - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {//回溯每一个硬币
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}

*单词拆分

139. 单词拆分 - 力扣（LeetCode）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1
2
3
4
5
6
7
8
9
10
11
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        //dp[i]字符串s前i个字符组成的字符串s[0..i−1]是否能被空格拆分成若干个字典中出现的单词
        dp[0] = true;
        for(int i=1; i<=s.length(); i++){
            for(int j=0; j<i; j++){
                if(dp[j] && wordDictSet.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3
4
5
6
7
8
9
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

输入：nums = [0,1,0,3,2,3]
输出：4

输入：nums = [7,7,7,7,7,7,7]
输出：1

1.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

2.贪心 + 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int lengthOfLIS(int[] nums) {
        //贪心+二分查找
        if(nums.length == 0){
            return 0;
        }
        int d[] = new int[nums.length+1];
        //d[i]表示长度为i的最长上升子序列的末尾元素的最小值
        int len = 1;//len表示已求出的最长上升子序列的长度
        d[1] = nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i] > d[len]){
                d[++len] = nums[i];
            }else{
                int left = 1;
                int right = len;
                int pos = 0;
                //如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将pos设为0
                while(left <= right){//二分查找第一个比nums[i]小的数d[k]
                    int mid = (left+right)>>1;
                    if(d[mid] < nums[i]){
                        pos = mid;
                        left = mid+1;
                    }else{
                        right = mid-1;
                    }
                }
                d[pos+1] = nums[i];
            }
        }
        return len;
    }
}

乘积最大子数组

152. 乘积最大子数组 - 力扣（LeetCode）

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

1
2
3
4
5
6
7
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

1.动态规划：考虑正负性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        long maxF = nums[0];//以第 i 个元素结尾的乘积最大子数组的乘积
        long minF = nums[0];//以第 i 个元素结尾的乘积最小子数组的乘积
        for(int i=1; i<nums.length; i++){
            long mx = maxF;
            long mn = minF;
            maxF = Math.max(mx*nums[i], Math.max(mn*nums[i], nums[i]));
            minF = Math.min(mx*nums[i], Math.min(mn*nums[i], nums[i]));
            max = Math.max(max, (int)maxF);
        }
        return max;
    }
}

分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

1
2
3
4
5
6
7
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

本质：转化为01背包：从nums中找出和为数组和一半的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return false;
        }
        boolean dp[] = new boolean[sum/2+1];//01背包
        dp[0] = true;//背包为0：不放东西
        for(int i=0; i<nums.length; i++){//遍历物品
            for(int j=sum/2; j>=nums[i]; j--){//遍历背包
                dp[j] = dp[j] | dp[j-nums[i]];//是否放入该物品
            }
        }
        return dp[sum/2];
    }
}

最长有效括号

32. 最长有效括号 - 力扣（LeetCode）

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

1
2
3
4
5
6
7
8
9
10
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

输入：s = ""
输出：0

1.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        int dp[] = new int[s.length()];
        //dp[i]是以下标i字符结尾的最长有效括号的长度
        for(int i=1; i<s.length(); i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    dp[i] = (i-2>=0 ? dp[i-2] : 0) + 2;
                }else if(i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1) == '('){
                    dp[i] = dp[i-1] + ((i-dp[i-1]-2) >= 0 ? dp[i-dp[i-1]-2] : 0) + 2;
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}

2.栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        //栈底为已经遍历过的元素中最后一个没有被匹配的右括号下标，其他的均为未匹配的左括号的下标
        stack.push(-1);
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){//左括号
                stack.push(i);
            }else{//右括号
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);//当前右括号没有匹配，压入栈底
                }else{//当前括号可弹出栈的左括号匹配
                    max = Math.max(max, i-stack.peek());
                }
            }
        }
        return max;
    }
}

3.不需要额外的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}

多维动态规划

不同路径

62. 不同路径 - 力扣（LeetCode）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

1.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

2.组合数学

1
2
3
4
5
6
7
8
9
class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

最小路径和

64. 最小路径和 - 力扣（LeetCode）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];//从左边或者上边来的最小值
            }
        }
        return dp[rows - 1][columns - 1];
    }
}

*最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

给你一个字符串 s，找到 s 中最长的 回文 子串。

1
2
3
4
5
6
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"

1.动态规划：dp[i][j]表示s[i..j]是否是回文串

在状态转移方程中，从长度较短的字符串向长度较长的字符串进行转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2){
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        // dp[i][j] 表示 s[i..j]是否是回文串
        
        //初始化：所有长度为1的子串都是回文串
        for(int i=0; i<s.length(); i++){
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        //状态转移方程中，从长度较短的字符串向长度较长的字符串转移
        for(int L=2; L<=s.length(); L++){//枚举子串长度
            for(int i=0; i<s.length(); i++){//枚举左边界
                int j=L+i-1;
                if(j>=s.length()){//右边界越界，退出当前循环
                    break;
                }

                if(charArray[i] != charArray[j]){
                    dp[i][j] = false;//不相等，则不是回文串
                }else{//相等
                    if(j-i<2){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                //dp[i][L] == true成立，表示子串s[i..L]是回文，记录回文长度和起始位置
                if(dp[i][j] && j-i+1 > maxLen){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + maxLen);
    }
}

2.中心转移算法：枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。对所有的长度求出最大值，即可得到最终的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public String longestPalindrome(String s) {
        //中心扩展算法
        if(s==null || s.length()<1){
            return "";
        }
        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            int len1 = expandAroundCenter(s, i, i);//以i为回文中心
            int len2 = expandAroundCenter(s, i, i+1);//以[i,i+1]为回文中心
            int len = Math.max(len1, len2);
            if(len > end-start){
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        return s.substring(start, end+1);
    }

    public int expandAroundCenter(String s,int left,int right) {
        //以[left, right]为回文中心的最长回文串
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;//回文串长度
    }
}

*最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

1
2
3
4
5
6
7
8
9
10
11
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestCommonSubsequence(String text1, String text2){
        int dp[][] = new int[text1.length()+1][text2.length()+1];
        //初始化：最长公共子序列为0
        //dp[i][j]表示以i-1为结尾的字符串和以j-1为结尾的字符串的最长公共子序列
        for(int i=0; i<text1.length(); i++){
            for(int j=0; j<text2.length(); j++){
                if(text1.charAt(i) == text2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

*编辑距离

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int minDistance(String word1, String word2) {
        //有一个字符串为空串
        if(word1.length() == 0 || word2.length() == 0){
            return word1.length() + word2.length();
        }

        int dp[][] = new int[word1.length()+1][word2.length()+1];
        //dp[i][j]表示A的前i个字母和B的前j个字母之间的编辑距离

        //边界状态初始化
        for(int i=0; i<=word1.length(); i++){
            dp[i][0] = i;
        }
        for(int j=0; j<=word2.length(); j++){
            dp[0][j] = j;
        }

        for(int i=1; i<=word1.length(); i++){
            for(int j=1; j<=word2.length(); j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                } else{
                    int left = dp[i-1][j] + 1;
                    int upper = dp[i][j-1] + 1;
                    int left_upper = dp[i-1][j-1] + 1;
                    dp[i][j] = Math.min(left, Math.min(upper, left_upper));
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}

模板

快慢指针

1.快慢指针找中间结点（按照/2找）

1
2
3
4
5
6
7
8
9
private ListNode endOfFirstHalf(ListNode head){//找到中间结点
    ListNode fast = head;
    ListNode slow = head;
    while(fast.next != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

2.找[head, tail)之间的指针

1
2
3
4
5
6
7
8
9
ListNode slow = head;
ListNode fast = head;
while(fast != tail){//找到中间结点slow，分成两个链表
    slow = slow.next;
    fast = fast.next;
    if(fast != tail){
        fast = fast.next;
    }
}

翻转链表

1.翻转一整个链表

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while(cur != null){
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre; //返回翻转后的头结点
}

2.翻转在【head, tail】区间的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode[] reverseK(ListNode head, ListNode tail){
    //将[head, tail]区间内链表进行翻转

    ListNode prev = tail.next;//指向前一个结点
    ListNode p = head;//指向当前结点
    while(prev != tail){//当前一个结点指向尾结点，说明翻转结束
        ListNode next = p.next;
        p.next = prev;//翻转链表
        prev = p;
        p = next;
    }
    return new ListNode[]{tail, head};//返回翻转后新的头和尾结点
}

倒数第N个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;//从僵尸节点开始
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;//second->next是倒数第n个节点
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

并查集

1.路径有权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class UnionFind{
public:
    vector<int> parent;
    vector<double> weight;//指向父节点的权值（父是分子）

    UnionFind(int n){
        parent.resize(n);
        weight.resize(n);
        for(int i=0; i<n; i++){
            parent[i] = i;
            weight[i] = 1.0;
        }
    }

    void Union(int x, int y, double value){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY){
            return;
        }

        parent[rootX] = rootY;
        weight[rootX] = weight[y]*value/weight[x];
    }

    // 修改为递归实现的路径压缩
    int find(int x) {
        if (parent[x] != x) {
            int origin = parent[x];
            parent[x] = find(parent[x]);
            weight[x] *= weight[origin];
        }
        return parent[x];
    }


    double isConnected(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY){//路径压缩之后，x和y肯定直接连接父亲节点
            return weight[x]/weight[y];
        }else{
            return -1.0;
        }
    }
};

2.路径没权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class UnionFind{
    int count;
    int[] parent;//并查集
    int[] rank;//rank值高的作为该并查集的根节点

    public UnionFind(char[][] grid){
        count = 0;
        int m = grid.length;
        int n = grid[0].length;
        parent = new int[m*n];
        rank = new int[m*n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == '1'){
                    parent[i * n + j] = i * n + j;//注意这里是i*n，不是i*m，因为每行有n个数
                    count++;//count为1的个数，也就是当前连通分量个数，即并查集个数
                }
                rank[i*n + j] = 0;//每个位置的rank都是0
            }
        }
    }

    public int find(int i){
        if(parent[i] != i) parent[i] = find(parent[i]);//查找的过程中，将路上的每个结点的父节点都修改为根节点
        return parent[i];
    }

    public void union(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){//两个结点不在同一个集合，则合并
            if(rank[rootx] > rank[rooty]){//将父节点统一为rank值大的那个
                parent[rooty] = rootx;
            }else if(rank[rootx] < rank[rooty]){
                parent[rootx] = rooty;
            }else{//一开始大家rank都一样，这里将左边的rootx作为rank大的那一个
                parent[rooty] = rootx;
                rank[rootx] ++;//rootx的rank增大
            }
            count--;//合并之后，联通分量就变少一个，也就是并查集会变少一个
        }
    }
}

二分查找（左边和右边区间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] searchRange(int[] nums, int target) {
        //「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {//找左边的加上等于号
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

*排序

*KMP

参考链接：KMP算法——通俗易懂讲好KMP算法：实例图解分析+详细代码注解 –》你的所有疑惑在本文都能得到解答-CSDN博客

LeetCode链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

实现：

1.实现1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;


public class Main {
    public static void main(String[] args) {
        //KMP算法
        //next[i]前缀函数：s[0,i]中最长的相等的真前缀和真后缀的长度
        // "acacebacacc";
        //  00120012340
        String haystack = "sadbutsad";
        String needle = "sad";

        int []next = new int[needle.length()];
        int j=0;
        for(int i=1; i<needle.length(); i++){
            while(j>0 && needle.charAt(i) != needle.charAt(j)){//不相等
                j = next[j-1];//当前匹配到j这个位置，前一个就是j-1
            }
            if(needle.charAt(i) == needle.charAt(j)){//如果相等，j+1
                j++;
            }
            //此时j为0或者needle[i]==needle[j]
            next[i] = j;
        }

        // KMP匹配过程
        j=0; //needle的当前匹配位置
        for (int i = 0; i < haystack.length(); i++) {
            // 不匹配时回退
            while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j-1];//当前匹配到j这个位置，前一个就是j-1
            }
            // 匹配时前进
            if(haystack.charAt(i) == needle.charAt(j)){//如果相等，j+1
                j++;
            }
            // 完全匹配成功
            if(j == needle.length()) {
                System.out.println(i - j + 1);
                j = 0; // 匹配成功后，从0开始匹配
            }
        }

        System.out.println(-1);
    }
}

2.实现2：子串匹配也复用了求next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package other;

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

/**
 * @author srr
 * @createDate 2025/5/20
 * @description
 */
public class KMP {
    public static void main(String[] args) {
        String s  = "acacebacacc";
        int[] next = new int[s.length()];
        for(int i=1; i<s.length(); i++){
            int j = next[i-1];//前一个（这里是i-1，因为字符串匹配到i这个位置）
            while(j > 0 && s.charAt(i) != s.charAt(j)){//不相等
                j = next[j-1];//前一个位置（这里是j-1，因为字符串匹配到j这个位置
            }
            if(s.charAt(j) == s.charAt(i)){//相等
                j++;
            }
            next[i] = j;
        }
        System.out.println(Arrays.toString(next));


        String text  = "acacebacaacacebacaccccacacebacacc";//主串
        String pattern = "acacebacacc";//子串
        String cur = pattern + '#' + text;//子串在前，主串在后
        int sz1 = text.length(), sz2 = pattern.length();
        List<Integer> v = new ArrayList<>();
        int[] lps = prefix_function(cur);
        System.out.println(Arrays.toString(lps));
        for (int i = sz2 + 1; i <= sz1 + sz2; i++) {//从主串的位置开始
            if (lps[i] == sz2) {
                v.add(i - 2 * sz2);
            }
        }
        System.out.println(v);
    }

    static int[] prefix_function(String s) {
        int n = s.length();
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = pi[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        return pi;
    }
}

*背包问题

参考链接：

完全背包问题 - 讨论 - 力扣（LeetCode）

01背包问题详解（浅显易懂）-CSDN博客

背包问题详解（01背包，完全背包，多重背包，分组背包）-CSDN博客

【算法】一文带你搞懂完全背包！（附背包问题总结）-CSDN博客

完全背包问题相对于0-1背包，主要区别点在于物品可以使用无限次

1.0-1背包的dp状态转移方程

1
2
3
4
5
6
7
// 01背包
for (int i = 0; i < weight.length; i++) {
    // 从后往前遍历背包容量
    for (int j = cap; j >= weight[i]; j--) {
        dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
    }
}

2.完全背包的dp状态转移方程

1
2
3
4
5
6
7
// 完全背包
for (int i = 0; i < weight.length;; i++) {
    // 从前往后遍历背包容量
    for (int j = weight[i]; j <= cap; j++) {
        dp[j] = max(dp[j], dp[j-weight[i]] + valeu[i]);
    }
}

上面那个是先遍历物品在遍历背包容量

我们还可以从另外一个角度理解完全背包：

因为所有物品可以无限次拿，定义dp数组表示 容量为n时，所装物品的最大价值

则有 f(n) = max( f(n-i) ) 0<i<=n且需要存在物品重量等于i

则可以循环物品，针对每一个小于等于n的物品，计算f(n-i)值取最大值

1
2
3
4
5
6
7
8
// 先循环容量、在循环物品
for (int i = 1; i <= cap; i++) {
    for (int j = 0; j < weight.length; j++) {
        if (weight[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - weight[j]] + values[j]);
        }
    }
}
LeetCode Hot 100
#LeetCode Hot 100
LeetCode Hot 100（全）
http://surourou8.github.io/2025/10/08/LeetCode-Hot-100（全）/
作者
Su Rourou
发布于
2025年10月8日
许可协议