力扣记录：剑指offer（4）——JZ33-42

JZ33 二叉搜索树的后序遍历序列

• 递归，判断当前节点左子树所有节点是否小于该节点，右子树所有节点是否大于该节点
  • 时间复杂度O(n^2)，空间复杂度O(n)

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //递归，左闭右闭
        return recursive(postorder, 0, postorder.length - 1);
    }
    //递归判断当前节点左子树所有节点是否小于该节点，右子树所有节点是否大于该节点
    private boolean recursive(int[] postorder, int left, int right){
        //左边界大于右边界遍历结束返回true
        if(left >= right) return true;
        //求取左子树右边界（开区间），即右子树左边界（闭区间）
        int leftTreeR = left;
        while(postorder[leftTreeR] < postorder[right]) leftTreeR++;
        //求取右子树右边界（开区间）
        int rightTreeR = leftTreeR;
        while(postorder[rightTreeR] > postorder[right]) rightTreeR++;
        //未到达根节点时说明非法
        if(rightTreeR != right) return false;
        //开始下一轮判断，分别判断左子树和右子树
        return recursive(postorder, left, leftTreeR - 1) && recursive(postorder, leftTreeR, right - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 辅助栈，根据后序遍历的反向序列进行判断：当前元素大于栈顶元素，该元素为栈顶元素的右孩子，否则查找栈中大于且最接近该元素的父节点，剩下的元素都应该小于该父节点，
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //辅助栈
        Deque<Integer> stack = new LinkedList<>();
        int root = Integer.MAX_VALUE;   //当前父节点
        for(int i = postorder.length - 1; i >= 0; i--){
            //查找栈中大于且最接近该元素的父节点
            while(!stack.isEmpty() && stack.peek() > postorder[i]){
                root = stack.pop();
            }
            if(postorder[i] > root) return false;
            stack.push(postorder[i]);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

JZ34 二叉树中和为某一值的路径

• 递归，遍历二叉树所有路径并保存符合条件的路径最后返回
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        //递归存储当前路径和符合条件的路径
        LinkedList<Integer> path = new LinkedList<>();
        LinkedList<List<Integer>> result = new LinkedList<>();
        //判断特殊情况
        if(root == null) return result;
        //开始递归
        recursive(root, target, path, result);
        return result;
    }
    //递归函数，输入当前节点，目标值，当前路径和符合条件的路径集合
    private void recursive(TreeNode root, int target, List<Integer> path, List<List<Integer>> result){
        path.add(root.val); //当前路径
        if(root.left == null && root.right == null){    //到达叶子节点
            if(target == root.val){
                result.add(new LinkedList<>(path));   //存储符合条件的路径，注意新建对象
            }
            return;
        }
        //递归回溯
        if(root.left != null){
            recursive(root.left, target - root.val, path, result);
            path.remove(path.size() - 1);  //回溯
        }
        if(root.right != null){
            recursive(root.right, target - root.val, path, result);
            path.remove(path.size() - 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

JZ35 复杂链表的复制

• 递归新建节点，使用Map存储已经新建的节点，防止死循环
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public Map<Node, Node> nodeMap = new HashMap<>();	//使用Map
    public Node copyRandomList(Node head) {
        //判断特殊情况
        if(head == null) return null;
        Node headNew = creatNode(head);
        return headNew;
    }
    //构建新节点
    private Node creatNode(Node node){
        if(nodeMap.containsKey(node)) return nodeMap.get(node);
        Node nodeNew = new Node(node.val);
        nodeMap.put(node, nodeNew);	//递归前需要加入map，否则死循环
        if(node.next != null) nodeNew.next = creatNode(node.next);
        if(node.random != null && nodeNew.random == null) nodeNew.random = creatNode(node.random);
        return nodeNew;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 迭代同时拆分，将原链表节点指向一个复制新节点（该节点本身，random未定义，第一次遍历），复制新节点指向原链表下一个节点，然后修改新节点的random（第二次遍历），最后拆分两个链表（第三次遍历）。注意：不能修改原链表，因此要将原链表复原
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public Node copyRandomList(Node head) {
        //判断特殊情况
        if(head == null) return null;
        //迭代同时拆分
        Node temp = head;
        //第一次遍历，复制新节点
        while(temp != null){
            Node nodeNew = new Node(temp.val);
            nodeNew.next = temp.next;
            temp.next = nodeNew;
            temp = nodeNew.next;
        }
        //第二次遍历，修改新节点的random
        temp = head;
        while(temp != null){
            if(temp.random != null) temp.next.random = temp.random.next;
            temp = temp.next.next;
        }
        //第三次遍历，拆分两个原链表和新链表
        temp = head.next;
        Node pre = head;
        Node res = head.next;
        while(temp.next != null){
            pre.next = temp.next;
            temp.next = temp.next.next;
            pre = pre.next;
            temp = temp.next;
        }
        pre.next = null;    //复原原链表最后一个节点
        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

JZ36 二叉搜索树与双向链表

• 递归修改左右孩子，中序遍历
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        //判断特殊情况
        if(root == null) return root;
        //递归
        recursive(root);
        //首尾相接
        head.left = pre;
        pre.right = head;
        return head;
    }
    //递归修改左右孩子
    private void recursive(Node cur){
        //中序遍历
        if(cur == null) return;
        recursive(cur.left);
        if(pre != null){
            pre.right = cur;
            cur.left = pre;
        }else{  //保存链表头结点，不一定是二叉树根节点！
            head = cur;
        }
        pre = cur;
        recursive(cur.right);
    }
}
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

JZ37 序列化二叉树

• 层序遍历，使用队列，限定每次处理的元素个数（相当于满二叉树），序列化使用StringBuilder提高效率
  • 时间复杂度O(n)，空间复杂度O(n)

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //层序遍历，使用队列
        Queue<TreeNode> queue = new LinkedList<>();
        LinkedList<String> res = new LinkedList<>();
        //初始化
        queue.offer(root);
        while(!queue.isEmpty()){
            int leng = queue.size();    //每层长度
            for(int i = 0; i < leng; i++){
                TreeNode temp = queue.poll();
                //保存结果
                if(temp != null){
                    queue.offer(temp.left);
                    queue.offer(temp.right);
                    res.add(String.valueOf(temp.val));
                }else{
                    res.add("null");
                }
            }
        }
        String result = "";
        for(int i = 0; i < res.size() - 1; i++){
            result += res.get(i) + ",";
        }
        result += res.get(res.size() - 1);
        return result;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        TreeNode[] nodeArray = new TreeNode[dataArray.length];
        //层序遍历，使用队列
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = null;
        //初始化
        for(int i = 0; i < dataArray.length; i++){
            if(!dataArray[i].equals("null")){
                TreeNode node = new TreeNode(Integer.parseInt(dataArray[i]));
                nodeArray[i] = node;
            }else{
                nodeArray[i] = null;
            }
        }
        queue.offer(nodeArray[0]);
        int leng = 1;   //初始长度
        int index = 1;  //初始位置
        while(!queue.isEmpty() && index < nodeArray.length){
            int l = leng;
            for(int i = 0; i < leng; i++){
                TreeNode cur = queue.poll();
                if(cur != null){
                    if(l == 1) root = cur;    //保存根结点
                    if(nodeArray[index] != null){
                        cur.left = nodeArray[index];
                    }
                    queue.offer(nodeArray[index++]);
                    if(nodeArray[index] != null){
                        cur.right = nodeArray[index];
                    }
                    queue.offer(nodeArray[index++]);
                }
            }
            //下一轮循环
            leng *= 2;
        }
        return 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
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

JZ38 字符串的排列

• 回溯，定义数组标记使用过的元素不能再次使用，在回溯函数内进行遍历！
  • 时间复杂度O(n*n!)，空间复杂度O(n)

class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder sb = new StringBuilder("");
    public String[] permutation(String s) {
        char[] sArr = s.toCharArray();
        Arrays.sort(sArr);
        //定义Map标记使用过的元素不能再次使用
        boolean[] used = new boolean[sArr.length];
        //回溯
        backtracking(sArr, used);
        String[] result = res.toArray(new String[res.size()]);
        return result;
    }
    //回溯函数
    private void backtracking(char[] sArr, boolean[] used){
        if(sb.length() == sArr.length){
            res.add(sb.toString()); //保存结果
            return;
        }
        //递归
        for(int i = 0; i < sArr.length; i++){
            //跳过使用过的元素
            if(i > 0 && sArr[i] == sArr[i - 1] && used[i - 1] == false) continue;
            if(used[i] == true) continue;
            sb.append(sArr[i]);
            used[i] = true;
            //回溯
            backtracking(sArr, used);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = 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

JZ39 数组中出现次数超过一半的数字

• 排序后取中位数，自己写排序的话空间复杂度O(1)，别用
  • 时间复杂度O(n*logn)，空间复杂度O(logn)

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return(nums[nums.length / 2]);
    }
}
1
2
3
4
5
6

• 使用哈希表遍历统计出现次数
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int majorityElement(int[] nums) {
        //遍历统计
        Map<Integer, Integer> map = new HashMap<>();
        int countMax = nums.length / 2;
        int numMax = nums[0];
        for(int num : nums){
            if(!map.containsKey(num)) map.put(num, 0);
            int count = map.get(num) + 1;
            map.put(num, count);
            if(count > countMax) return num;
        }
        return numMax;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 摩尔投票法，设众数票数为+1，其他数票数为-1，则最后总和大于0，遍历数组并假设一个众数，当票数和为0时，剩余数组的众数一定不变（如果假设的众数是正确的，则抵消的所有数字中，有一半是众数；如果假设的众数是错误的，则抵消的所有数字中，众数的数量最少为 0 个，最多为一半）
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int majorityElement(int[] nums) {
        //摩尔投票法
        int res = nums[0];  //假设众数
        int sum = 1;    //票数和
        for(int i = 1; i < nums.length; i++){
            if(sum == 0){
                res = nums[i];  //票数和为0重新假设众数
            }
            if(nums[i] != res){
                sum--;
            }else{
                sum++;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

JZ40 最小的k个数

• 排序后返回前k个数字（可以重复），别用
  • 时间复杂度O(n*logn)，空间复杂度O(logn)

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        //排序
        Arrays.sort(arr);
        int[] res = new int[k];
        if(arr.length == 0 || k == 0) return res;
        for(int i = 0; i < k; i++){
            res[i] = arr[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

• 使用大根堆（前k小）/小根堆（前k大）
  • 时间复杂度O(n*logk)，空间复杂度O(k)

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        //判断特殊情况
        int[] result = new int[k];
        if(arr.length == 0 || k == 0) return result;
        //使用大根堆保存前k小
        Queue<Integer> priqueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for(int a : arr){
            if(priqueue.size() < k){
                priqueue.offer(a);
            }else{
                if(priqueue.peek() > a){
                    priqueue.poll();
                    priqueue.offer(a);
                }
            }
        }
        for(int i = 0; i < k; i++){
            result[i] = priqueue.poll();
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 使用快排思想，随机选定哨兵，小于哨兵的数放在左边，大于的放在右边。选取的哨兵排序后下标为k，则说明哨兵到左侧尽头为最小的k个数；如果返回下标小于k，则递归向右选取哨兵；如果返回下标大于k，则递归向左选取哨兵
  • 局限：需要修改原数组，需要保存所有的数据（堆只保存k个）
  • 时间复杂度O(n)（最坏O(n^2)），空间复杂度O(logn)（最坏O(n)）

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        //判断特殊情况
        int[] result = new int[k];
        if(arr.length == 0 || k == 0) return result;
        //快排思想
        quickSort(arr, k, 0, arr.length - 1);
        for(int i = 0; i < k; i++){
            result[i] = arr[i];
        }
        return result;
    }
    //快排函数，输入排序数组，要求的k个数，左右区间（左闭右闭）
    private void quickSort(int[] arr, int k, int left, int right){
        if(left > right) return;
        //快排
        int i = left;
        int j = right;
        while(i < j){   //选取左边界为哨兵
            while(i < j && arr[j] >= arr[left]) j--;    //这里先移动右下标
            while(i < j && arr[i] <= arr[left]) i++;    //先移动左下标会指向大于哨兵的数
            swap(arr, i, j);    //交换两数
        }
        swap(arr, left, i);    //将哨兵换到中间
        //注意，此时还是要求下标k，因为是相对整个数组的下标
        if(j > k){  //如果返回下标大于k，则递归向左选取哨兵
            quickSort(arr, k, left, j - 1);
        }else if(j < k){    //如果返回下标小于k，则递归向右选取哨兵
            quickSort(arr, k, j + 1, right);
        }
        return;
    }
    //交换函数，输入数组和两个下标，交换数组中两个下标的数
    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
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

JZ41 数据流中的中位数

• 使用两个顶堆，将数据分为较大和较小两部分，一个小顶堆A保存较大的一半，一个大顶堆B保存较小的一半。操作时根据数据总量的奇偶进行讨论
  • 插入：若当前数据总量为偶数，则将新元素插入B，再将B堆顶元素插入A；若为奇数，则将新元素插入A，再将A堆顶元素插入B。查找：偶数返回A和B堆顶元素的平均值，奇数返回A堆顶元素。
  • 时间复杂度O(logn)（其中查找O(1)，插入O(logn)），空间复杂度O(n)

class MedianFinder {
    //使用两个顶堆，将数据分为较大和较小两部分
    //一个小顶堆A保存较大的一半，一个大顶堆B保存较小的一半
    PriorityQueue<Integer> A;
    PriorityQueue<Integer> B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<Integer>((o1, o2) -> o1 - o2);    //小顶堆
        B = new PriorityQueue<Integer>((o1, o2) -> o2 - o1);    //大顶堆
    }
    //插入：
    //若当前数据总量为偶数，则将新元素插入B，再将B堆顶元素插入A；
    //若为奇数，则将新元素插入A，再将A堆顶元素插入B
    public void addNum(int num) {
        if(A.size() == B.size()){
            B.offer(num);
            A.offer(B.poll());
        }else{
            A.offer(num);
            B.offer(A.poll());
        }
    }
    //查找：
    //偶数返回A和B堆顶元素的平均值，奇数返回A堆顶元素
    public double findMedian() {
        if(A.size() == 0) return 0.0;
        if(A.size() == B.size()){
            return (A.peek() + B.peek()) / 2.0;
        }else{
            return A.peek() * 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

JZ42 连续子数组的最大和

• 贪心，求局部最大值，不断更新最大值
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        //贪心
        int sum = -101;
        int max = -101;
        for(int i = 0; i < nums.length; i++){
            if(sum < 0){
                sum = nums[i];
            }else{
                sum += nums[i];
            }
            max = Math.max(sum, max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 贪心，求局部最大值，不断更新最大值
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        //动态规划DP
        // //定义dp数组dp[i]表示数组nums从下标x(-1
        // int[] dp = new int[nums.length];
        // //初始化
        // dp[0] = nums[0];
        //优化
        int dp = nums[0];
        //正序遍历
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            // dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            // max = Math.max(max, dp[i]);
            dp = Math.max(nums[i], dp + nums[i]);
            max = Math.max(max, dp);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 分治法线段树思想*

  • 优势：不仅可以解决区间[0, n - 1]，还可以解决任意子区间问题
  • 时间复杂度O(n)，空间复杂度O(logn)