LeetCode刷题笔记——《剑指Offer》面试题（3）

算法
, , ,

画图让抽象问题形象化

二叉树的镜像

思路：使用递归，对左右子树分别取镜像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void Mirror(TreeNode root) {
        root = reverse(root);
    }

    public TreeNode reverse(TreeNode root) {
        if (root == null) return root;
        TreeNode left = reverse(root.left);
        TreeNode right = reverse(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

对称的二叉树

思路：

  1. 判断是否同时为null或不为null。
  2. 判断根节点是否相等。
  3. 递归判断左右子树是否满足以上性质。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    boolean isSymmetrical(TreeNode pRoot){
        if (pRoot==null) return true;
        return isSymmetrical(pRoot.left, pRoot.right);
    }

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

顺时针打印矩阵

思路：此题的关键在于判断循环终止的条件。

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[] spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m==0) return new int[]{};
        int n = matrix[0].length;
        if (n==0) return new int[]{};
        int[] res = new int[m*n];
        int l=0, r=n-1, t=0, b=m-1;
        int a=0;
        while (a<m*n) {
            for (int i=l; i<=r; i++) {
                res[a] = matrix[t][i];
                a++;
            }
            t++;
            if (t>b) break;
            for (int i=t; i<=b; i++) {
                res[a] = matrix[i][r];
                a++;
            }
            r--;
            if (r<l) break;
            for (int i=r; i>=l; i--) {
                res[a] = matrix[b][i];
                a++;
            }
            b--;
            if (t>b) break;
            for (int i=b; i>=t; i--) {
                res[a] = matrix[i][l];
                a++;
            }
            l++;
            if (l>r) break;
        }
        return res;
    }
}

举例让抽象问题具体化

包含min函数的栈

思路：使用辅助栈保存最小值。当有新元素压入，将其与辅助栈栈顶值比较，若新元素较小，则将其压入辅助栈，否则复制栈顶元素，这样就保证辅助栈栈顶一直为最小值。当需要弹出元素时，最小栈也同时弹出栈顶元素。

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 Stack<Integer> stack;
    public Stack<Integer> helper;

    public MinStack() {
        stack = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (!helper.isEmpty() && helper.peek()<x) {
            helper.push(helper.peek());
        } else {
            helper.push(x);
        }
    }

    public void pop() {
        stack.pop();
        helper.pop();
    }

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

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

栈的压入、弹出序列

思路：使用一个栈来模拟栈的压入、弹出序列。当有元素压入时，比较其与弹出序列相应的值，若相等则弹出并且弹出序列指针+1，否则继续压入元素。最后检查栈是否为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length!=popped.length) return false;
        if (pushed.length==0) return true;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i=0; i<pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && j<popped.length && popped[j]==stack.peek()) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

从上往下打印二叉树

思路：即二叉树的层次遍历，使用队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root == null) return res;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.removeFirst();
            res.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return res;
    }
}

分行从上往下打印二叉树

思路：在层次遍历的基础上，使用两个标记：toBePrinted标记当前层剩余待打印元素的数量，nextLevel标记下一层需要打印的数量。当toBePrinted==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
class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int toBePrinted = 1;
        int nextLevel = 0;
        ArrayList<Integer> temp = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.removeFirst();
            temp.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                nextLevel++;
            }
            if (node.right != null) {
                queue.add(node.right);
                nextLevel++;
            }
            toBePrinted--;
            if (toBePrinted==0) {
                res.add(temp);
                temp = new ArrayList<>();
                toBePrinted = nextLevel;
                nextLevel = 0;
            }
        }
        return res;
    }
}

之字形打印二叉树

思路：使用两个栈分别保存奇数行和偶数行的节点。根节点入栈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
class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot==null) return res;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(pRoot);
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            ArrayList<Integer> temp = new ArrayList<>();
            if (!stack1.isEmpty()) {
                while (!stack1.isEmpty()) {
                    TreeNode root = stack1.pop();
                    temp.add(root.val);
                    if (root.left!=null) stack2.push(root.left);
                    if (root.right!=null) stack2.push(root.right);
                }
            } else {
                while (!stack2.isEmpty()) {
                    TreeNode root = stack2.pop();
                    temp.add(root.val);
                    if (root.right!=null) stack1.push(root.right);
                    if (root.left!=null) stack1.push(root.left);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

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

思路：在后序遍历中，最末位的是根节点，序列中小于根节点值的是左子树，大于根节点值的是右子树，据此递归判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) return false;
        return VerifySquenceOfBST(sequence, 0, sequence.length-1);
    }

    public boolean VerifySquenceOfBST(int[] sequence, int l, int r) {
        if (l >= r) return true;
        int root = sequence[r], m = l;
        while (sequence[m] < root) m++;
        for (int j=m; j<r; j++) {
            if (sequence[j] < root) return false;
        }
        return VerifySquenceOfBST(sequence, l, m-1) && VerifySquenceOfBST(sequence, m, r-1);
    }
}

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

思路：DFS。访问到某一个节点，记录这个路径点，并把路径上的和与目标值比较，如果一个节点是叶子节点并且路径和等于目标，则输出，否则回到父节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if(root == null) return res;
        path.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<Integer>(path));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        path.remove(path.size()-1);
        return res;
    }
}

分解让复杂问题简单化

复杂链表的复制

思路：

  1. 复制节点，接在原节点的后面。
  2. 为复制节点复制random指针。
  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
class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return null;
        RandomListNode cur = pHead;
        while (cur != null) {
            RandomListNode pClone = new RandomListNode(cur.label);
            pClone.next = cur.next;
            cur.next = pClone;
            cur = pClone.next;
        }
        cur = pHead;
        while (cur != null) {
            if (cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        cur = pHead;
        RandomListNode pCloneHead = pHead.next;
        while (cur != null && cur.next != null) {
            RandomListNode temp = cur.next;
            cur.next = temp.next;
            cur = temp;
        }
        return pCloneHead;
    }
}

二叉搜索树与双向链表

思路：二叉搜索树的中序遍历是排序的，改造中序遍历使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
class Solution {

    public Node prev;
    public Node head;

    public Node treeToDoublyList(Node root) {
        if (root==null) return root;
        prev = null;
        head = null;
        inorder(root);
        prev.right = head;
        head.left = prev;
        return head;
    }

    public void inorder(Node root) {
        if (root==null) return;
        inorder(root.left);
        if (prev!=null) prev.right = root;
        else head = root;
        root.left = prev;
        prev = root;
        inorder(root.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Codec {

    public String serialize(TreeNode root) {
        if (root==null) return "[]";
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node!=null) {
                sb.append(node.val+",");
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                sb.append("null,");
            }
        }
        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        String[] nodes = data.substring(1, data.length()-1).split(",");
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        int i=1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!nodes[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));
                node.left = left;
                queue.offer(left);
            }
            i++;
            if (!nodes[i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(nodes[i]));
                node.right = right;
                queue.offer(right);
            }
            i++;
        }
        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
class Solution {

    ArrayList<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public String[] permutation(String s) {
        char[] ch = s.toCharArray();
        Arrays.sort(ch);//排序，避免重复
        int[] used = new int[ch.length];
        dfs(ch, used, 0);
        String[] ans = new String[res.size()];
        for (int i=0; i<res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    public void dfs(char[] ch, int[] used, int i) {
        if (sb.length()==ch.length) {
            res.add(sb.toString());
            return;
        }
        for (int j=0; j<ch.length; j++) {
            if (used[j]==1) continue;
            if (j>0 && ch[j-1]==ch[j] && used[j-1]==1) continue;//去重
            sb.append(ch[j]);
            used[j] = 1;
            dfs(ch, used, j);
            used[j] = 0;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}