力扣记录：Hot100（7）——207-240

207 课程表

• 图论问题，判断有向图中是否存在环，拓扑排序。递归：定义二维数组，保存节点间的依赖关系（指向关系），从每个节点出发进行深度遍历，定义节点的三种状态（未遍历、已被其他节点遍历、已被当前节点遍历）。
  • 时间复杂度O(m+n)，空间复杂度O(m+n)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //图论问题，判断有向图中是否存在环，拓扑排序
        //递归：定义二维数组，保存节点间的依赖关系（指向关系）
        List<List<Integer>> coursesList = new ArrayList<>();
        //初始化
        for(int i = 0; i < numCourses; i++){
            coursesList.add(new ArrayList<>());
        }
        for(int[] p : prerequisites){
            coursesList.get(p[1]).add(p[0]);    //[0,1]，1依赖于0
        }
        //定义节点的三种状态（未遍历0、已被其他节点遍历1、已被当前节点遍历-1）
        int[] flag = new int[numCourses];
        //从每个节点出发进行深度遍历
        for(int i = 0; i < numCourses; i++){
            if(!dfs(coursesList, flag, i)) return false;
        }
        return true;
    }
    //深度遍历，输入课程依赖二维数组，节点状态数组，出发节点
    private boolean dfs(List<List<Integer>> coursesList, int[] flag, int i){
        //终止条件
        if(flag[i] == 1) return true;
        if(flag[i] == -1) return false;
        flag[i] = -1;    //修改当前状态
        //递归
        for(int j : coursesList.get(i)){
            if(!dfs(coursesList, flag, j)) return false;
        }
        flag[i] = 1;   //递归结束发现没有环，修改后准备下一出发节点
        return 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

208 实现 Trie (前缀树)

• 使用多叉树（节点），每个节点有一个长度为26（分别表示'a'-'z'）的节点数组，初始化为全null，还有一个判断当前节点是否字符串最后的布尔值，初始化为false。插入字符串，遍历字符串，如果节点已存在，直接向下遍历，否则在节点数组对应位置插入新节点（新节点同样包括一个数组和布尔值），直到最后一个字符，将布尔值赋值为true。查找字符串，遍历字符串，从多叉树中查找，若对应节点为null，则返回false，直到最后一个字符，布尔值需要为true。查找前缀，同查找字符串，但是最后一个字符不要求布尔值为true。
  • 优化：可以将查找字符串和查找前缀的冗余代码写成新函数
  • 时间复杂度O(|字符串长度|)，空间复杂度O(|所有插入字符串之和|*字符集大小)，字符集大小为26

class Trie {
    //使用多叉树（节点），每个节点有一个长度为26（分别表示'a'-'z'）的节点数组，初始化为全null
    //还有一个判断当前节点是否字符串最后的布尔值，初始化为false
    private Trie[] children;
    private boolean end;
    public Trie() {
        children = new Trie[26];
        end = false;
    }
    //插入字符串，遍历字符串，在节点数组对应位置插入新节点（新节点同样包括一个数组和布尔值）
    //如果节点已存在，直接向下遍历
    //直到最后一个字符，将布尔值赋值为true
    public void insert(String word) {
        Trie node = this;
        for(int i = 0; i < word.length(); i++){
            int pos = word.charAt(i) - 'a';
            if(node.children[pos] == null){
                node.children[pos] = new Trie();
            }
            node = node.children[pos];
        }
        node.end = true;
    }
    //查找字符串，遍历字符串，从多叉树中查找，若对应节点为null，则返回false
    //直到最后一个字符，布尔值需要为true
    public boolean search(String word) {
        Trie node = this;
        for(int i = 0; i < word.length(); i++){
            int pos = word.charAt(i) - 'a';
            if(node.children[pos] == null){
                return false;
            }
            node = node.children[pos];
        }
        if(node.end == true) return true;
        return false;
    }
    //查找前缀，同查找字符串，但是最后一个字符不要求布尔值为true
    public boolean startsWith(String prefix) {
        Trie node = this;
        for(int i = 0; i < prefix.length(); i++){
            int pos = prefix.charAt(i) - 'a';
            if(node.children[pos] == null){
                return false;
            }
            node = node.children[pos];
        }
        return 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

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

• 前k大->小根堆（o1-o2），前k小->大根堆（o2-o1）。参考JZ40 最小的k个数。建议手动写根堆。
  • 时间复杂度O(nlogk)，空间复杂度O(k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //前k大->小根堆，前k小->大根堆
        Queue<Integer> priQueue = new PriorityQueue<>((o1, o2) -> o1 - o2);
        for(int n : nums){
            if(priQueue.size() < k){
                priQueue.offer(n);
            }else{
                if(priQueue.peek() < n){
                    priQueue.poll();
                    priQueue.offer(n);
                }
            }
        }
        return priQueue.poll();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

221 最大正方形

• 动态规划，定义dp数组dp[i][j]表示以下标i、j为右下角的最大正方形边长。初始化第一行、第一列为二维数组值，当前位置的最大正方形边长等于min(上方、左方和左上方最大正方形边长) + 1
  • 时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
    public int maximalSquare(char[][] matrix) {
        //动态规划，注意输入为char[][]
        int m = matrix.length;
        int n = matrix[0].length;
        //定义dp数组dp[i][j]表示以下标i、j为右下角的最大正方形边长
        int[][] dp = new int[m][n];
        int max = 0;
        //初始化第一行、第一列为二维数组值
        for(int i = 0; i < m; i++){
            dp[i][0] = matrix[i][0] - '0';
            max = Math.max(max, dp[i][0]);
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = matrix[0][j] - '0';
            max = Math.max(max, dp[0][j]);
        }
        //当前位置的最大正方形边长等于min(上方、左方和左上方最大正方形边长) + 1
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }else{
                    dp[i][j] = 0;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}
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

226 翻转二叉树

• 递归，之前做过，交换左右子树
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //递归
        if(root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        //交换左右子树
        root.left = right;
        root.right = left;
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

234 回文链表

• 快慢指针，但是需要修改链表（不适合并发环境），将链表分为前半和后半，将后半部分翻转（参考206 反转链表），逐个对比后再恢复链表
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        //快慢指针
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = null;    //方便链表恢复
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        //若节点数为奇数，则此时slow指向中间节点，next才是后半部分起点
        if(fast != null){
            pre = slow;
            slow = slow.next;
        }
        //翻转后半部分链表，切断
        ListNode reRight = reverseList(slow);
        ListNode right = reRight;
        ListNode left = head;
        //逐个对比
        boolean result = true;
        while(right != null){
            if(right.val != left.val){
                result = false;
                break;
            }
            right = right.next;
            left = left.next;
        }
        //恢复链表
        pre.next = reverseList(reRight);
        return result;
    }
    //翻转链表
    private ListNode reverseList(ListNode node){
        if(node == null) return null;
        ListNode pre = null;
        ListNode cur = node;
        ListNode temp = null;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
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

236 二叉树的最近公共祖先

• 递归，之前做过，后序遍历，相当于将子节点的状态向父节点传递，若找到目标节点则将目标节点向上传递，否则直到叶子节点下面（null），当某个节点左右子树返回值都为目标节点（不为null）时即为最近公共祖先，返回该节点，否则返回不为空的子树（继续向上传递，直到找到最近公共祖先，若目标节点互为父子，同样传递到root返回）。
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归
        //相当于将子节点的状态向父节点传递，若找到目标节点则将目标节点向上传递
        //否则直到叶子节点下面（null）
        if(root == p || root == q || root == null) return root;
        //后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //当某个节点左右子树返回值都为目标节点（不为null）时即为最近公共祖先，返回该节点
        //否则返回不为空的子树
        //继续向上传递，直到找到最近公共祖先，若目标节点互为父子，同样传递到root返回
        if(left != null && right != null){
            return root;
        }else if(left != null){
            return left;
        }else{
            return right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

238 除自身以外数组的乘积

• 构建两个数组，分别存储自身左边和右边的乘积，参考JZ66 构建乘积数组，可以用一个数组存左边，一个数存右边累积到左边，最后左边即结果
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        //先计算i左边再计算i右边
        int[] result = new int[nums.length];
        result[0] = 1;
        for(int i = 1; i < nums.length; i++){
            result[i] = result[i - 1] * nums[i - 1];
        }
        int rightSum = 1;   //用一个数存即可
        for(int j = nums.length - 2; j >= 0; j--){
            rightSum *= nums[j + 1];
            result[j] *= rightSum;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

239 滑动窗口最大值

• 单调队列（尾进头出，保持队列头部为最大，即出队位置为最大），之前做过，入队时若当前元素大于队列尾部元素，则弹出尾部元素直到保持单调或队列为空后再入队，否则直接入队；出队时如果队列头部元素（最大）等于要出队的元素，则出队，否则不处理。
  • 时间复杂度O(n)，空间复杂度O(k)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //单调队列（尾进头出，保持队列头部为最大，即出队位置为最大）
        myDeque mydeque = new myDeque();
        int[] result = new int[nums.length - k + 1];
        int count = 0;
        //初始化
        for(int i = 0; i < k; i++){
            mydeque.offer(nums[i]);
        }
        result[count++] = mydeque.peek();
        //滑动窗口
        for(int i = k; i < nums.length; i++){
            mydeque.poll(nums[i - k]);
            mydeque.offer(nums[i]);
            result[count++] = mydeque.peek();
        }
        return result;
    }
    //自定义单调队列
    class myDeque {
        Deque<Integer> deque = new LinkedList<>();
        //入队时若当前元素大于队列尾部元素，则弹出尾部元素直到保持单调或队列为空后再入队
        //否则直接入队
        void offer(int n){
            while(!deque.isEmpty() && n > deque.peekLast()){
                deque.pollLast();
            }
            deque.offer(n);
        }
        //出队时如果队列头部元素（最大）等于要出队的元素，则出队，否则不处理
        void poll(int n){
            if(!deque.isEmpty() && deque.peek() == n){
                deque.poll();
            }
        }
        //队列头部即为最大
        int peek(){
            return deque.peek();
        }
    }
}
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

240 搜索二维矩阵 II

• 同JZ4 二维数组中的查找，从右上角开始搜索，相当于二叉搜索树，左小下大。
  • 时间复杂度O(m+n)，空间复杂度O(1)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //从右上角开始搜索，相当于二叉搜索树，左小下大
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while(i >= 0 && i < m && j >= 0 && j < n){
            if(matrix[i][j] > target){
                j -= 1;
            }else if(matrix[i][j] < target){
                i += 1;
            }else{
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19