本文最后更新于2021年10月4日,已超过 2 个月没更新!

26. 树的子结构

递归

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public static boolean recur (TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

27. 二叉树的镜像

递归

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

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{push(root);}};

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

28. 对称的二叉树

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

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

29. 顺时针打印矩阵

模拟

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[0];
        int m = matrix.length, n = matrix[0].length;
        int len = m * n, idx = 0;
        int[] ans = new int[len];
        int endi = n - 1, endj = m - 1, start = 0;
        while (start <= endi && start <= endj) {
            for (int i = start; i <= endi; ++i) {
                ans[idx++] = matrix[start][i];
            }
            if (idx == len) break;
            for (int i = start + 1; i <= endj; ++i) {
                ans[idx++] = matrix[i][endi];
            }
            if (idx == len) break;
            for (int i = endi - 1; i >= start; --i) {
                ans[idx++] = matrix[endj][i];
            }
            if (idx == len) break;
            for (int i = endj - 1; i > start; --i) {
                ans[idx++] = matrix[i][start];
            }
            start++ ;
            endi--;
            endj--;
        }
        return ans;
    }
}

30. 包含min函数的栈

class MinStack {
    Stack<Integer> stackA;
    Stack<Integer> stackB;

    /** initialize your data structure here. */
    public MinStack() {
        stackA = new Stack<>();
        stackB = new Stack<>();
    }

    public void push(int x) {
        // 等于也要加入stackB栈中
        if (stackA.empty() || x <= stackB.peek()) {
            stackB.push(x);
        }
        stackA.push(x);
    }

    public void pop() {
        if (stackA.pop().equals(stackB.peek())) {
            stackB.pop();
        }
    }

    public int top() {
        return stackA.peek();
    }

    public int min() {
        return stackB.peek();
    }
}

31. 栈的压入、弹出序列

模拟(贪心)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 使用一个栈模拟
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.empty() && stack.peek() == popped[j]) {
                stack.pop();
                ++j;
            }
        }
        return stack.empty();
    }
}

32-I. 从上到下打印二叉树

class Solution {
    public int[] levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                list.add(node.val);
                q.offer(node.left);
                q.offer(node.right);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); ++ i) ans[i] = list.get(i);
        return ans;
    }
}

32-II. 从上到下打印二叉树II

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++ i) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            } 
            list.add(level);
        }
        return list;
    }
}

32-III. 从上到下打印二叉树 III

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            LinkedList<Integer> level = new LinkedList<>();
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++ i) {
                TreeNode node = q.poll();
                if (list.size() % 2 == 1) level.addFirst(node.val);
                else level.addLast(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            list.add(level);
        }
        return list;
    }
}

33. 二叉搜索树的后序遍历序列

递归分治

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public boolean recur (int[] postorder, int start, int end) {
        if (start >= end) return true;
        int p = start;
        while (postorder[end] > postorder[p]) ++p;
        int q = p;
        while (postorder[end] < postorder[q]) ++q;
        if (end != q) return false;
        else return recur(postorder, start, p - 1) && recur(postorder, p, end - 1);
    }
}

辅助单调栈⭐⭐

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 表示上一个根节点的元素,这里可以把postorder的最后一个元素root看成无穷大节点的左孩子
        int root = Integer.MAX_VALUE;
        // 逆向遍历,就是翻转的先序遍历
        for (int i = postorder.length - 1; i >= 0; --i) {
            // 左子树元素必须要小于递增栈被peek访问的元素,否则就不是二叉搜索树
            if (postorder[i] > root) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                // 数组元素小于单调栈的元素了,表示往左子树走了,记录下上个根节点
                // 找到这个左子树对应的根节点,之前右子树全部弹出,不再记录,因为不可能在往根节点的右子树走了
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}

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

递归

class Solution {
    LinkedList<List<Integer>> list = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return list;
    }

    private void recur (TreeNode node, int tar) {
        if (node == null) return;
        path.add(node.val);
        tar -= node.val;
        if (tar == 0 && node.left == null && node.right == null) {
            list.add(new LinkedList(path));
        }
        recur(node.left, tar);
        recur(node.right, tar);
        path.removeLast();
    }
}

35. 复杂链表的复制

class Solution {
    HashMap<Node, Node> visitedMap = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) return head;

        if (this.visitedMap.containsKey(head)) {
            return this.visitedMap.get(head);
        }

        Node node = new Node(head.val, null, null);
        this.visitedMap.put(head, node);

        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);
        return node;
    }
}

36. 二叉搜索树与双向链表

递归

class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs (Node node) {
        if (node == null) return;
        dfs(node.left);
        if (pre != null) {
            pre.right = node;
        } else head = node;
        node.left = pre;
        pre = node;
        dfs(node.right);
    }
}

迭代

class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node head = null, pre = null;
        Deque<Node> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null) {
                pre.right = root;
            } else head = root;
            root.left = pre;
            pre = root;
            root = root.right;
        }
        head.left = pre;
        pre.right = head;
        return head;
    }
}

37. 序列化二叉树

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder s = new StringBuilder();
        s.append("[");
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                s.append(node.val + ",");
                q.offer(node.left);
                q.offer(node.right);
            } else {
                s.append("null,");
            }
        }
        s.deleteCharAt(s.length() - 1);
        s.append("]");
        return s.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        Queue<TreeNode> q = new LinkedList<>();
        String[] s = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        q.offer(root);
        int idx = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (!s[idx].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(s[idx]));
                q.offer(node.left);
            }
            ++ idx;
            if (!s[idx].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(s[idx]));
                q.offer(node.right);
            }
            ++ idx;
        }
        return root;
    }
}

38. 字符串的排列

回溯

class Solution {
    public String[] permutation(String s) {
        StringBuilder str = new StringBuilder();
        int[] visited = new int[s.length()];
        Set<String> set = new HashSet<>();
        backTrack(s, str, visited, set);
        return set.toArray(new String[set.size()]);
    }

    private static void backTrack (String s, StringBuilder str, int[] visited, Set<String> set) {
        for (int i = 0; i < s.length(); ++ i) {
            if (visited[i] == 1) continue;
            str.append(s.charAt(i));
            visited[i] = 1;
            if (str.length() == s.length()) {
                set.add(str.toString());
            } else {
                backTrack (s, str, visited, set);
            }
            str.deleteCharAt(str.length() - 1);
            visited[i] = 0;
        }
    }
}

K佬

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复,因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换,将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

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

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1; 
        }
        return x;
    }
}

41. 数据流中的中位数

双堆

class MedianFinder {

    Queue<Integer> A;
    Queue<Integer> B;

    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x, y) -> y - x);
    }

    public void addNum(int num) {
        if (A.size() != B.size()) {
            B.add(num);
            A.add(B.poll());
        } else {
            A.add(num);
            B.add(A.poll());
        }
    }

    public double findMedian() {
        if (A.size() == B.size()) return (double)(A.peek() + B.peek()) / 2;
        return (double)B.peek();
    }
}

42. 连续子数组的最大和

动态规划专题最大子序和


Try and fail, but don't fail to try.