经典算法题目记录

力扣100

1. 两数之和（复习）

  • 题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if (map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}
  • 分析

略

参考：
两数之和

49. 字母异位词分组

  • 题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

  • 题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> map = new HashMap<>();
            for (String str : strs){
                char[] chars = str.toCharArray();
                Arrays.sort(chars);
                String key = new String(chars);
                List<String> list = map.getOrDefault(key, new ArrayList<>());
                list.add(str);
                map.put(key, list);
            }
            List<List<String>> list = new ArrayList<>();
            for (Map.Entry<String, List<String>> entry : map.entrySet()){
                list.add(entry.getValue());
            }
            return list;
        }
    }

  • 分析

略

参考：
字母异位词分组

128. 最长连续序列

  • 题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(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 longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums){
            set.add(num);
        }
        int res = 0;
        for (int num : nums){
            if (set.contains(num - 1)){
                continue;
            }
            int tl = 1;
            int t = num;
            while (set.contains(t + 1)){
                t++;
                tl++;
            }
            res = Math.max(tl, res);
        }
        return res;
    }
}
  • 分析

当Set中有数字小于当前数字时需要剪枝。

参考：
最长连续序列

283. 移动零

  • 题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void moveZeroes(int[] nums) {
        int zs = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == 0){
                zs = i;
                break;
            }
        }
        if (zs == -1){
            return;
        }
        for (int e = zs + 1; e < nums.length; e++){
            if (nums[e] == 0){
                continue;
            }
            nums[zs] = nums[e];
            zs++;
            nums[e] = 0;
        }
    }
}
  • 分析

如果找不到第一个0，直接退出

时间复杂度：O(n)
空间复杂度：O(1)

参考：
最长连续序列

11. 盛最多水的容器

  • 题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int res = 0;
        while (i < j){
            res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]){
                i++;
            } else {
                j--;
            }
        }
        return res;
    }
}
  • 分析

移动小的那边

参考：
盛最多水的容器

15. 三数之和（复习）

  • 题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 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
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++){
            if (nums[i] > 0){
                return res;
            }
            if (i != 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                if (j != i + 1 && nums[j] == nums[j - 1]){
                    j++;
                    continue;
                }
                if (k != nums.length - 1 && nums[k] == nums[k + 1]){
                    k--;
                    continue;
                }
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0){
                    Integer[] arr = new Integer[]{nums[i], nums[j], nums[k]};
                    res.add(Arrays.asList(arr));
                    j++;
                    k--;
                } else if (sum > 0){
                    k--;
                } else{
                    j++;
                }
            }
        }
        return res;
    }
}
  • 分析

基本的思路是排序，然后双指针夹逼，需要注意的点是结果不能重复，所以我直接采用了暴力的HashSet进行去重。但是整体流程不是那么的优雅，更加优雅的方案是前面几个值固定时，当前值去重，一但当前值有重复的，很可能导致出现重复结果，所以需要跳过。

参考：
三数之和
力扣题解

42. 接雨水

  • 题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++){
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--){
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }
        int res = 0;
        for (int i = 0; i < height.length; i++){
            res += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        return res;
    }
}
  • 分析

每个位置所能接的雨水是Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i])

参考：
接雨水

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

  • 题目

给定一个字符串 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 int lengthOfLongestSubstring(String s) {
        if (s.length() == 0){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(0), 0);
        int[] dp = new int[s.length()];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < s.length(); i++){
            char c = s.charAt(i);
            if (map.containsKey(c)){
                dp[i] = Math.min(dp[i - 1] + 1, i - map.get(c));
            } else {
                dp[i] = dp[i - 1] + 1;
            }
            res = Math.max(res, dp[i]);
            map.put(c, i);
        }
        return res;
    }
}
  • 分析

动态规划

参考：
无重复字符的最长子串

560. 和为 K 的子数组

  • 题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

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

前缀和

参考：
和为 K 的子数组

53. 最大子数组和

  • 题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int res = dp[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++){
            dp[i] = nums[i] + Math.max(0, dp[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
  • 分析

动态规划

参考：
最大子数组和

56. 合并区间

  • 题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

  • 题解
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[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++){
            int[] p = intervals[i];
            if (p[0] <= end){
                if (p[1] <= end){
                    continue;
                } else {
                    end = p[1];
                }
            } else {
                list.add(new int[]{start, end});
                start = p[0];
                end = p[1];
            }
        }
        list.add(new int[]{start, end});
        return list.toArray(new int[0][0]);
    }
}
  • 分析

动态规划

参考：
合并区间

41. 缺失的第一个正数

  • 题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++){
            while(nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]){
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
        }
        for (int i = 0; i < nums.length; i++){
            if (nums[i] != i + 1){
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}
  • 分析

通过置换，将数字放到正确的位置，置换并不会改变数字，但是可以确定数字该有的位置，如果一个nums[i] = x,则将这个数字和num[x - 1]的位置，循环这样放置后，数组就会呈现1、2、3之类的顺序，第一个错误的位置就是最小的正数。如果每个位置都有正确的数字，说明1~n的数字都是全的，那么结果就是n+1了。
每个位置循环置换，如果nums[i] = x 大于N或者小于1，说明超出范围，跳到下一位置继续置换，如果出现num[i] == num[num[i] - 1],说明num[i] 上的数字已经是正确的数字了，这样也需要跳到下一个位置继续置换。

这个思路真是想不出来，好好把这个题目给记住吧。注意，本题的数字可能重复，所以这里nums[i] != nums[nums[i] - 1] 而不是 nums[i] != i + 1；

时间复杂度：O(n)，至多置换n次，每次置换都会把一个数字放到正确的位置或者排除掉一个超限的数字。
空间复杂度：O(1)。

参考：
缺失的第一个正数

73. 矩阵置零

  • 题目

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> cs = new HashSet<>();
        Set<Integer> rs = new HashSet<>();
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length; j++){
                if (matrix[i][j] == 0){
                    rs.add(i);
                    cs.add(j);
                }
            }
        }
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length; j++){
                if (rs.contains(i) || cs.contains(j)){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
  • 分析

记录置零的行列，最后遍历

参考：
矩阵置零

54. 螺旋矩阵

  • 题目

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

  • 题解
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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int t = 0;
        int d = matrix.length - 1;
        int l = 0;
        int r = matrix[0].length - 1;
        List<Integer> res = new ArrayList<>();
        while(true){
            for (int j = l; j <= r; j++){
                res.add(matrix[t][j]);
            }
            t++;
            if (t > d){
                break;
            }
            for (int i = t; i <= d; i++){
                res.add(matrix[i][r]);
            }
            r--;
            if (r < l){
                break;
            }
            for (int j = r; j >= l; j--){
                res.add(matrix[d][j]);
            }
            d--;
            if (d < t){
                break;
            }
            for (int i = d; i >= t; i--){
                res.add(matrix[i][l]);
            }
            l++;
            if (l > r){
                break;
            }
        }
        return res;
    }
}
  • 分析

收缩边界，本体直接用边界的坐标进行遍历即可。

时间复杂度：O(n*m)。
空间复杂度：O(1)。

参考：
螺旋矩阵

160. 相交链表

  • 题目

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        ListNode pb = headB;
        while (pa != pb){
            if (pa == null){
                pa = headB;
            }
            if (pb == null){
                pb = headA;
            }
            if (pa == pb){
                return pa;
            }
            pa = pa.next;
            pb = pb.next;
        }
        return pa;
    }
}
  • 分析

注意在点切换的时候，还需要判断一次相等，否则可能漏掉相交点。

时间复杂度：O(n+m)。
空间复杂度：O(1)。

参考：
相交链表

206. 反转链表

  • 题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur.next != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        cur.next = pre;
        return cur;
    }
}
  • 分析

经典题目，原来做过，曾经某电商面试原题，没做出来的我尴尬得不行，这次倒是可以很快写出来，记录下用于巩固。

时间复杂度：O(n)。
空间复杂度：O(1)。

参考：
反转链表

141. 环形链表

  • 题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while(slow != fast){
            if (slow == null){
                return false;
            } else {
                slow = slow.next;
            }
            if (fast == null || fast.next == null){
                return false;
            } else {
                fast = fast.next.next;
            }
        }
        return true;
    }
}
  • 分析

快慢指针

参考：
环形链表

142. 环形链表 II

  • 题目

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

  • 题解
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
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while(slow != fast){
            if (slow == null){
                return null;
            } else {
                slow = slow.next;
            }
            if (fast == null || fast.next == null){
                return null;
            } else {
                fast = fast.next.next;
            }
        }
        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
  • 分析

快慢指针

参考：
环形链表2

24. 两两交换链表中的节点（复习）

  • 题目

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode vh = new ListNode();
        ListNode p = vh;
        while (head != null){
            if (head.next == null){
                p.next = head;
                return vh.next;
            }
            ListNode next = head.next;
            head.next = next.next;
            next.next = head;
            p.next = next;
            p = head;
            head = head.next;
        }
        return vh.next;
    }
}
  • 分析

node1和node2的顺序会改变，直接用这两个指针会有点麻烦，所以直接又创建了指针p，为了方便又创建一个虚拟头节点。

时间复杂度：O(n)。
空间复杂度：O(1)。

参考：
两两交换链表中的节点

138. 随机链表的复制

  • 题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node p = head;
        while (p != null){
            map.put(p, new Node(p.val));
            p = p.next;
        }
        p = head;
        while (p != null){
            Node node = map.get(p);
            node.next = map.get(p.next);
            node.random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}
  • 分析

先建立副本，然后根据原链表关系建立连结。

参考：
随机链表的复制

138. 随机链表的复制

  • 题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node p = head;
        while (p != null){
            map.put(p, new Node(p.val));
            p = p.next;
        }
        p = head;
        while (p != null){
            Node node = map.get(p);
            node.next = map.get(p.next);
            node.random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}
  • 分析

先建立副本，然后根据原链表关系建立连结。

参考：
随机链表的复制

543. 二叉树的直径

  • 题目

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

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDep(root);
        return res;
    }
    public int maxDep(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = maxDep(root.left);
        int right = maxDep(root.right);
        res = Math.max(res, left + right );
        return Math.max(left, right) + 1;
    }
}
  • 分析

在求最大深度的过程中进行计算，顺带计算的中间变量。

时间复杂度：O(n)。
空间复杂度：O(1)。

参考：
二叉树的直径

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

  • 题目

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int[] nums;
    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return dfs(0, nums.length - 1);
    }
    public TreeNode dfs(int start, int end){
        if (start == end){
            return new TreeNode(nums[start]);
        }
        if (start > end){
            return null;
        }
        TreeNode root = new TreeNode(nums[(start + end)/2]);
        TreeNode right = dfs((start + end)/2 + 1, end);
        TreeNode left = dfs(start, (start + end)/2 - 1);
        root.right = right;
        root.left = left;
        return root;
    }
}
  • 分析

分治

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

98. 验证二叉搜索树

  • 题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

  • 题解
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 {
    boolean res = true;
    Integer pre = null;
    boolean stop = false;
    public boolean isValidBST(TreeNode root) {
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if (root == null || stop){
            return;
        }
        dfs(root.left);
        if (stop){
            return;
        }
        if (pre == null || pre < root.val){
            pre = root.val;
        } else {
            res = false;
            stop = true;
            return;
        }
        dfs(root.right);
    }
}
  • 分析

中根遍历，用包装类解决初始化的问题，增加停止标识进行剪枝。注意每段开始都要做一下剪枝检查。

时间复杂度：O(n)。
空间复杂度：方法1:栈深度O(n)

参考：
验证二叉搜索树

114. 二叉树展开为链表

  • 题目

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

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

  • 题解
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) {
        dfs(root);
    }
    public TreeNode dfs(TreeNode root){
        if (root == null){
            return null;
        }
        TreeNode left = dfs(root.left);
        TreeNode right = dfs(root.right);
        TreeNode p = root;
        p.right = left;
        while (p.right != null){
            p = p.right;
        }
        p.right = right;
        root.left = null;
        return root;
    }
}
  • 分析

技巧题

参考：
二叉树展开为链表

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

  • 题目

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

  • 题解
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 {
    int[] preorder;
    int[] inorder;
    Map<Integer, Integer> iMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        iMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++){
            iMap.put(inorder[i], i);
        }
        return dfs(0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode dfs(int pl, int pr, int il, int ir){
        if (pl > pr || il > ir){
            return null;
        }
        TreeNode root = new TreeNode(preorder[pl]);
        int iri = iMap.get(preorder[pl]);
        root.left = dfs(pl + 1, pl + iri - il, il, iri - 1);
        root.right = dfs(pl + iri - il + 1, pr, iri + 1, ir);
        return root;
    }
}
  • 分析

一个map加速定位根坐标，四个坐标确定边界，通过子树长度辅助确定边界。

时间复杂度：O(n)
空间复杂度：O(n)

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

437. 路径总和 III

  • 题目

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

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

  • 题解

前缀和

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 res = 0;
    int targetSum = 0;
    Map<Long, Integer> preMap = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        preMap.put(0L, 1);
        dfs(root, 0L);
        return res;
    }
    public void dfs(TreeNode root, long pre){
        if (root == null){
            return;
        }
        pre += root.val;
        res += preMap.getOrDefault(pre - targetSum, 0);
        preMap.put(pre, preMap.getOrDefault(pre, 0) + 1);
        dfs(root.left, pre);
        dfs(root.right, pre);
        preMap.put(pre, preMap.getOrDefault(pre, 0) - 1);
    }
}
  • 分析

枚举法：
时间复杂度：O(n^2)
空间复杂度：O(n)，二叉树最坏的情况，树深度等于n

前缀和：
时间复杂度：O(n)
空间复杂度：O(n)

枚举法是以某个节点出发，分别有多少个目标路径，然后求和，这样对每个节点均需要再便利一次，时间复杂度较高
前缀和是计算以某个节点为结尾，分别有多少个目标路径，因为用了前缀和，对于每个点可以以O(1)的复杂度获取路径数，整体时间复杂度较低。前缀和加回溯掉的一批。大数的那个用例略撒比。

参考：
路径总和 III

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

  • 题目

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

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

  • 题解

前缀和

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

    public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q){
        if (root == null){
            return null;
        }
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        if (left != null && right != null || root.val == p.val || root.val == q.val){
            return root;
        } else if(left == null){
            return right;
        } else {
            return left;
        }
    }
}
  • 分析

技巧题

参考：
二叉树的最近公共祖先

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

  • 题目

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

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if (root == null){
            return 0;
        }
        int left =  Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        res = Math.max(res, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}
  • 分析

时间复杂度：O(n)
空间复杂度：O(n)

路径为节点值加左边加右边，贡献值G是节点值加左边或右边的贡献值，贡献值最低为0

参考：
二叉树中的最大路径和

46. 全排列

  • 题目

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

  • 题解
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 {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;
    boolean[] flags;
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        this.flags = new boolean[nums.length];
        dfs(new ArrayList<>());
        return res;
    }
    public void dfs(List<Integer> list){
        if (list.size() == nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (flags[i]){
                continue;
            }
            list.add(nums[i]);
            flags[i] = true;
            dfs(list);
            flags[i] = false;
            list.remove(list.size() - 1);
        }
    }
}
  • 分析

做到最后都靠直觉了。。。

参考：
全排列

78. 子集

  • 题目

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(new ArrayList<>(), 0);
        return res;
    }
    public void dfs(List<Integer> list, int ix){
        if (ix == nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        list.add(nums[ix]);
        dfs(list, ix + 1);
        list.remove(list.size() - 1);
        dfs(list, ix + 1);
    }
}
  • 分析

按照顺序，加入或者不加入dfs，可以得到所有的子集，回溯

时间复杂度：O(n·2^n)。共有2^n个状态，每个状态构造过程为O(n)
空间复杂度：O(n)，栈深度和临时数组的长度。

参考：
子集

39. 组合总和

  • 题目

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

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

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

  • 题解
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 {
    List<List<Integer>> res = new ArrayList<>();
    int[] candidates;
    int target;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        dfs(new ArrayList<>(), 0, 0);
        return res;
    }
    public void dfs(List<Integer> list, int ix, int sum){
        if (sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        if (ix == candidates.length || sum > target){
            return;
        }
        list.add(candidates[ix]);
        dfs(list, ix, sum + candidates[ix]);
        list.remove(list.size() - 1);
        dfs(list, ix + 1, sum);
    }
}
  • 分析

一个分支一只加当前元素，一个分支跳过当前元素

复杂度不太好算，懒了，不算了

参考：
组合总和

22. 括号生成

  • 题目

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<String> res = new ArrayList<>();
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(new StringBuilder(), 0, 0);
        return res;
    }
    public void dfs(StringBuilder sb, int left, int right){
        if (right > left || right + left > 2 * n){
            return;
        }
        if (right == left && left + right == 2 * n){
            res.add(sb.toString());
            return;
        }
        sb.append('(');
        dfs(sb, left + 1, right);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(')');
        dfs(sb, left, right + 1);
        sb.deleteCharAt(sb.length() - 1);
    }
}
  • 分析

就回溯的方法而言，这个题目不算难，这个题目难在对于括号终止条件的判断，有三个情况会终止，right > left 、 (right + left) > 2 * n 、 (left + right) == 2 * n && left == right。
这个终止条件的总结类似于业务知识，如果没有独到的分析能力，业务知识还是好好背背吧。

回溯问题的复杂度太难想了，放弃思考了。

参考：
括号生成

131. 分割回文串

  • 题目

给你一个字符串 s，请你将 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
24
25
26
27
28
29
30
31
class Solution {
    List<List<String>> res = new ArrayList<>();
    String s;
    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0, new ArrayList<>());
        return res;
    }
    public void dfs(int start, List<String> list){
        if (start == s.length()){
            res.add(new ArrayList<String>(list));
        }
        for (int end = start; end < s.length(); end++){
            if (check(start, end)){
                list.add(s.substring(start, end + 1));
                dfs(end + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }
    public boolean check(int start, int end){
        while (start < end){
            if (s.charAt(start) != s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}
  • 分析

从头开始，找到每个回文字符串加入列表中迭代寻找，另外需要回溯

参考：
分割回文串

35. 搜索插入位置

  • 题目

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

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

  • 题解
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 searchInsert(int[] nums, int target) {
        if (target > nums[nums.length - 1]){
            return nums.length;
        }
        int i = 0;
        int j = nums.length - 1;
        while (i < j){
            int mid = (i + j) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] < target){
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        return i;
    }
}
  • 分析

取大于等于target的第一个数，如果nums[mid] < target，则mid绝不可能成为解，所以left=mid+1，如果nums[mid] >= target，mid可能成为解，所以right=mid，因为推出条件为right == left，所以返回任意一个都可以。注意超界的特例判断。

参考：
搜索插入位置

74. 搜索二维矩阵

  • 题目

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

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = matrix.length - 1;
        while (i < j){
            int mid = (i + j + 1) / 2;
            if (matrix[mid][0] > target){
                j = mid - 1;
            } else {
                i = mid;
            }
        }
        int row = i;
        i = 0;
        j = matrix[0].length - 1;
        while (i < j){
            int mid = (i + j) / 2;
            if (matrix[row][mid] == target){
                return true;
            } else if (matrix[row][mid] < target){
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        if (matrix[row][i] == target){
            return true;
        } else{
            return false;
        }
    }
}
  • 分析

有点长了，感觉不会考的题目，思路其实挺简单，注意点是因为要从前向后逼近，所以前面int mid = (i + j + 1) / 2;

参考：
搜索二维矩阵

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

  • 题目

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

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target){
            return new int[]{-1, -1};
        }
        int i = 0;
        int j = nums.length - 1;
        while (i < j){
            int mid = (i + j) / 2;
            if (nums[mid] < target){
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        if (nums[i] != target){
            return new int[]{-1, -1};
        }
        int start = i;
        i = 0; 
        j = nums.length - 1;
        while (i < j){
            int mid = (i + j + 1) / 2;
            if (nums[mid] > target){
                j = mid - 1;
            } else {
                i = mid;
            }
        }
        return new int[]{start, i};
    }
}
  • 分析

找大于等于某数的第一个数字索引，用int mid = (i + j) / 2，找小于等于某数的第一个数字索引，用int mid = (i + j + 1) / 2，否则会死循环，另外找到后判断下是否是等于目标值，如果不等说明找不到。要形成一个夹逼的趋势。

时间复杂度：O(log n)
空间复杂度：O(1)

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

33. 搜索旋转排序数组

  • 题目

整数数组 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
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 search(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i < j){
            int mid = (i + j) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] > nums[j]){
                if (target > nums[j]){
                    if (nums[mid] > target){
                        j = mid - 1;
                    } else {
                        i = mid + 1;
                    }
                } else {
                    i = mid + 1;
                }
            } else {
                if (target > nums[j]){
                    j = mid - 1;
                } else {
                    if (nums[mid] > target){
                        j = mid - 1;
                    } else {
                        i = mid + 1;
                    }
                }
            }
        }
        if (nums[i] == target){
            return i;
        } else {
            return -1;
        }
    }
}
  • 分析

首先观察数组，最小的数字始终在右半边，所以可以认定右半边一直存在，所以每次mid都和nums[j]比较，确定mid在左半边还是右半边，同理target也是和nums[j]比较，如果mid和target在异侧，直接确定i或者j即可，如果在同侧，继续比较nums[mid]和target，然后再确定i或者j。最后需要看nums[i]是否和target相等，如不等说明没找到。

参考：
搜索旋转排序数组

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

  • 题目

已知一个长度为 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
12
13
14
15
class Solution {
    public int findMin(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        while (i < j){
            int mid = (i + j) / 2;
            if (nums[mid] > nums[j]){
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        return nums[i];
    }
}
  • 分析

因为找最小的数字，可以认为右边的数组是一直存在的

参考：
寻找旋转排序数组中的最小值

20. 有效的括号

  • 题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

  • 题解
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 isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()){
            if (!map.containsKey(c)){
                stack.addLast(c);
            } else {
                if (stack.size() == 0 || map.get(c) != stack.peekLast()){
                    return false;
                } else {
                    stack.removeLast();
                }
            }
        }
        return stack.size() == 0;
    }
}
  • 分析

map需要将后半括号作为key.

参考：
有效的括号

155. 最小栈

  • 题目

设计一个支持 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
17
18
19
20
21
22
23
24
25
26
27
28
29
class MinStack {
    Deque<Integer> stack = new LinkedList<>();
    Deque<Integer> minStack = new LinkedList<>();

    public MinStack() {

    }
    
    public void push(int val) {
        stack.addLast(val);
        if (minStack.isEmpty() || minStack.peekLast() >= val){
            minStack.addLast(val);
        }
    }
    
    public void pop() {
        if (minStack.peekLast().equals(stack.removeLast())){
            minStack.removeLast();
        }
    }
    
    public int top() {
        return stack.peekLast();
    }
    
    public int getMin() {
        return minStack.peekLast();
    }
}
  • 分析

有两个需要注意的点，一个是最小栈的放入逻辑，一个是包装类的比较。

参考：
最小栈

739. 每日温度

  • 题目

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<int[]> stack = new LinkedList<>();
        for (int i = 0; i < temperatures.length; i++){
          
            while(stack.size() != 0 && stack.peekLast()[0] < temperatures[i]){
                int[] e = stack.removeLast();
                res[e[1]] = i - e[1];
            }
            stack.addLast(new int[]{temperatures[i], i});
        }
        return res;
    }
}
  • 分析

单调栈法，栈元素为索引和值的数组，如果栈顶元素的值小于当前元素，说明温度第一次上升了，通过索引差值可以得到结果，然后栈顶出栈，直到栈顶元素大于当前元素或者栈为空时再将当前元素入栈。

参考：
每日温度

84. 柱状图中最大的矩形

  • 题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 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 largestRectangleArea(int[] heights) {
        int res = 0;
        int[] nh = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++){
            nh[i + 1] = heights[i];
        }
        Deque<int[]> stack = new LinkedList<>();
        stack.addLast(new int[]{0, 0});
        for (int i = 1; i < nh.length; i++){
            while(stack.peekLast()[1] > nh[i]){
                int[] e = stack.removeLast();
                int w = i - stack.peekLast()[0] - 1;
                int h = e[1];
                res = Math.max(res, w * h);
                
            }
            stack.addLast(new int[]{i, nh[i]});
        }
        return res;
    }
}
  • 分析

哨兵加单调栈，这个题解的第一个精髓是哨兵，可以免去边界值的考虑，极大降低解题的复杂程度，第二重点是矩形的宽度考虑，为什么是i - stack.peekLast()[0] - 1而不是i-出栈的索引，因为在出栈的索引前可能还有几个早就出栈的竖条，这些竖条的高度肯定不比当前出栈的高度低，所以当前出栈的高度对应的左边界应该在栈顶，所以为i - stack.peekLast()[0] - 1。

参考：
柱状图中最大的矩形

215. 数组中的第K个最大元素

  • 题目

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

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums){
            queue.add(num);
            if (queue.size() > k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}
  • 分析

优先队列

参考：
数组中的第K个最大元素

121. 买卖股票的最佳时机

  • 题目

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

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int res = 0;
        for (int i = 1; i < prices.length; i++){
            min = Math.min(min, prices[i]);
            res = Math.max(res, prices[i] - min);
        }
        return res;
    }
}
  • 分析

贪心

参考：
买卖股票的最佳时机

55. 跳跃游戏

  • 题目

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int maxid = 0;
        for (int i = 0; i < nums.length; i++){
            if (i > maxid){
                return false;
            }
            maxid = Math.max(maxid, i + nums[i]);
        }
        return true;
    }
}
  • 分析

贪心

参考：
跳跃游戏

45. 跳跃游戏 II

  • 题目

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

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

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

  • 题解
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 start = 0;
        int end = 0;
        int last = 0;
        int res = 0;
        while(last < nums.length - 1){
            res++;
            for (int i = start; i <= end; i++){
                last = Math.max(last, i + nums[i]);
            }
            start = end + 1;
            end = last;
        }
        return res;
    }
}
  • 分析

贪心

参考：
跳跃游戏 II

763. 划分字母区间

  • 题目

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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> res = new ArrayList<>();
        for (int i = 0; i < s.length(); i++){
            end = Math.max(last[s.charAt(i) - 'a'], end);
            if (i == end){
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}
  • 分析

也是类似一层一层的找，思路类似上题

参考：
划分字母区间

198. 打家劫舍

  • 题目

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

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

  • 题解
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 rob(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if (nums.length == 1){
            return dp[0];
        }
        dp[1] =  Math.max(dp[0], nums[1]);
        if (nums.length == 2){
            return dp[1];
        }
        dp[2] = Math.max(dp[0] + nums[2], dp[1]);
        if (nums.length == 3){
            return dp[2];
        }
        int res = dp[2];
        for (int i = 3; i < nums.length; i++){
            dp[i] = Math.max(Math.max(dp[i - 1], dp[i - 2] + nums[i]), dp[i - 3] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}
  • 分析

转移方程中极易漏掉的一点，dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + nums[i],dp[i - 3] + nums[i]))，有可能隔两个再加。

参考：
打家劫舍

279. 完全平方数

  • 题目

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++){
            int t = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++){
                t = Math.min(dp[i - j * j] + 1, t);
            }
            dp[i] = t;
        }
        return dp[n];
    }
}
  • 分析

在内层遍历的时候直接从完全平方数数着手，效率高很多

参考：
完全平方数

322. 零钱兑换

  • 题目

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

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

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

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++){
            int t = Integer.MAX_VALUE;
            for (int coin : coins){
                if (i - coin < 0 || dp[i - coin] == -1){
                    continue;
                }
                t = Math.min(t, dp[i - coin] + 1);
            }
            dp[i] = t == Integer.MAX_VALUE ? -1 : t;
        }
        return dp[amount];
    }
}
  • 分析

和上一题差不多了，麻了。

参考：
零钱兑换

139. 单词拆分

  • 题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

  • 题解
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) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i < dp.length; i++){
            boolean f = false;
            for (String word : wordDict){
                if (i - word.length() >= 0 && dp[i - word.length()] == true && word.equals(s.substring(i - word.length(),i))){
                    f = true;
                    break;
                }
            }
            dp[i] = f;
        }
        return dp[dp.length - 1];
    }
}
  • 分析

好像和上题还是差不多

参考：
单词拆分

300. 最长递增子序列

  • 题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 1;
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++){
            int t = 1;
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    t = Math.max(t, dp[j] + 1);
                }
            }
            dp[i] = t;
            res = Math.max(res, dp[i]);
        }
        return res;

    }
}
  • 分析

动态规划，有的状态基于前面一两个就行，还有的是要遍历前面所有状态的，背包问题就是这样的，这个题目也是这样的。

参考：
最长递增子序列

62. 不同路径

  • 题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

  • 题解
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[][] dp = new int[m][n];
        for (int i = 0; i < m; i++){
            dp[i][0]  = 1;
        }
        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
  • 分析

动态规划.

参考：
不同路径

64. 最小路径和

  • 题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; i++){
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < grid[0].length; i++){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < grid.length; i++){
            for (int j = 1; j < grid[0].length; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];

    }
}
  • 分析

动态规划.

参考：
最小路径和

136. 只出现一次的数字

  • 题目

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

  • 题解
1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums){
            res ^= num;
        }
        return res;
    }
}
  • 分析

异或

参考：
只出现一次的数字

136. 只出现一次的数字

  • 题目

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

  • 题解
1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums){
            res ^= num;
        }
        return res;
    }
}
  • 分析

异或

参考：
只出现一次的数字

169. 多数元素

  • 题目

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

  • 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++){
            int num = nums[i];
            if (count == 0){
                res = nums[i];
                count++;
            } else {
                if (res == nums[i]){
                    count++;
                } else {
                    count--;
                }
            }
        }
        return res;
    }
}
  • 分析

数字相消

参考：
多数元素

5. 最长回文子串

  • 题目

给你一个字符串 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
24
class Solution {
    public String longestPalindrome(String s) {
        String res = s.substring(0, 1);
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++){
            dp[i][i] = true;
        }
        for (int j = 1; j < s.length(); j++){
            for (int i = 0; i < j; i++){
                if (s.charAt(i) == s.charAt(j)){
                    if (j - i <= 2){
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > res.length()){
                    res = s.substring(i ,j + 1);
                }
            }
        }
        return res;
    }
}
  • 分析

多维dp

参考：
最长回文子串

数据结构与算法
#刷题
经典算法题目记录
https://fattree.cn/2024/04/26/经典算法题目记录/
作者
fattree
发布于
2024年4月26日
许可协议