剑指 Offer 题解

吹梦到西洲

算法

发布于：May 10, 2020

次浏览

前言

本文档中所有内容均采用 CC BY-NC 4.0 许可协议。

你可以复制共享、演绎创作，但不得用于商业目的。

本文档起源于本人于 $2020$ 年 $4$ 月起在 LeetCode 中《剑指 Offer》 所做的笔记。

看别人题解时的状态：一看就会，一听就懂，一做就错。

于是决定采用边阅读，边手敲题解，就算抄我也要抄一遍的方式进行学习，使用这种方法确实有一定作用。在手敲的过程中往往会有一些独特的体会以及更深刻的记忆，有时候自己也补上几句，久而久之，断断续续过去了三四个月，随着秋招的全面开启，这份笔记也越来越长，逐渐变成了现在这个样子。

$NOTE$: 本文档仅用于个人学习目的，旨在为准备校招的同学们以及其他对算法感兴趣的朋友提供一份便利，同时为了宣传 LeetCode-Krahets 的智慧结晶。

因为，这么精致的内容不让更多人看到实在是太说不过去了！

喜欢网页版的同学建议前往大佬的博客，其中有许多更形象生动的 $GIF$ 图。

喜欢 $PDF$ 的同学自然推荐这个。

我不是知识的生产者，只是知识的搬运工。

写于 $2020$ 年 $8$ 月 $9$ 日 $22$ 时 $35$ 分。

致谢

Credits are Krahets ‘s!

此中题解大部分出自 $LeetCode-Krahets$，大佬博客 $Krahets’s Blog$。

第一次看到大佬的题解时就有一种赏心悦目的感觉，排版精良，一丝不苟，哪怕只是一个再寻常不过的数字 $0$ 都会用 $LaTex$ 所修饰。毕竟，态度决定高度，细节决定成败。

本文中仍然存在很多问题，包括但不限于排版风格尚未完全统一、中英文标点符号不恰当、汉字错误、部分数学内容没有被 $LaTex$ 所渲染，以后将会逐渐完善。

可以说，如果不是这位大佬严谨细致题解，我很难坚持把 $LeetCode$ 上《剑指 $Offer$》系列题目看一遍。每当有题目没有头绪时，习惯性地在题解中寻找大佬的头像，阅读完后总有一种醍醐灌顶的感觉，感慨：山重水复疑无路，柳暗花明又一村。

题目来源

1. LeetCode中国 - 《剑指 Offer》 系列
2. 牛客网 - 《剑指 Offer》 系列

其他参考

• CS-Notes - 剑指Offer题解
• 《剑指Offer：名企面试官精讲典型编程题》，何海涛。

Tips

链表结点定义

1
2
3
4
5
6
7
8
9

/**
* 单链表结点定义
* 如不特殊说明，后文 链表结点 均采用此结构。
*/
public class ListNode {
    private int val;
    private ListNode next;
    public ListNode(int val) { this.val = val; }
}

二叉树节点定义

1
2
3
4
5
6
7
8
9
10

/**
* 二叉树节点定义
* 如不特殊说明，后文 树节点 均采用此结构。
*/
public class TreeNode {
    private int val;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int val) { this.val = val; }
}

名词约定

• 链表中的 $Node$ 中文为 结点；
• 树中的 $TreeNode$ 中文为 节点。

经验

很多考研的同学都知道下面这个口诀
$$
🐶-sin 🐶 \approx \frac{1}{6}🐶^3 ,\quad 🐶 \rightarrow 0
$$
算法里针对某类特定的题也应该有类似的口诀， 比如：

• 看到有序数组的问题首先想到二分法；
• 二叉搜索树中：二叉搜索树的中序遍历结果时递增序列；
• 关于搜索问题必须想到 $DFS$、$BFS$；
• 想到以后再添加$\dots$

3. 数组中重复的数字

题目描述

在一个长度为 $n$ 的数组里的所有数字都在 $0$ 到 $n-1$ 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

1
2
3
4
5
6
7

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

2, 3, 1, 0, 2, 5

Solution 1 - 计数

采用“计数”的思想，申请一个长度为 $n$ 的数组 validation (当然也可以用 map or set ，但是数组效率更高一些)，刚申请时每个元素都为 $0$，此时遍历一遍原数组，将原数组 nums 中的元素作为 validation 中的下标，并将 validation 中的元素加 $1$ ，表示元素出现了一次。在将原数组扫描一遍后，validation 中记录了每个元素出现的次数，再扫描一遍 validation，凡是 $\ge 1$ 的元素均为重复元素，返回第一个 $\ge 1$ 的元素即可。

1
2
3
4
5
6
7
8
9
10

public int findRepeatNumber(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    int[] count = new int[nums.length];
    for (int i = 0; i < nums.length; i++)
        count[nums[i]]++;
    for (int i = 0; i < count.length; i++)
        if (count[i] > 1)
            return i;
    return -1;
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

Solution 2 - 遍历一次

对于这种数组元素在$ [0, n-1]$ 范围内的问题，可以将值为 $i$ 的元素调整到第 $i$ 个位置上进行求解。本题要求找出重复的数字，因此在调整过程中，如果第 $i$ 位置上已经有一个值为 $i$ 的元素，就可以知道 $i$ 值重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int findRepeatNumber(int[] nums) {
    if (nums == null || nums.length == 0)
        return -1;
    for (int i = 0; i < nums.length; i++) {
        // 如果当前索引处的数值不等于索引
        // 将当前索引处的值调整到 i = nums[i] 或者找到重复值为止
        while (i != nums[i]) {
            // 如果相等说明已出现了重复
            if (nums[i] == nums[nums[i]])
                return nums[i];
            else
                swap(nums, i, nums[i]);
        }
    }
    return -1;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(1)$。

4. 二维数组中的查找

题目描述

在一个 $m\times n$ 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1
2
3
4
5
6
7
8
9
10
11

Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

Solution - 逼近

利用二维数组每一行从左到右递增，每一列从上到下递增的特点，可以从数组右上角开始：

• 如果扫描到的元素比 target 小，则在当前列从上到下搜索；
• 如果扫描到的元素比 target 大，则在当前行从右向左搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean findNumberIn2DArray(int target, int [][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return false;
    int rows = matrix.length, cols = matrix[0].length;
    int row = 0, col = cols - 1;
    while (row < rows && col >= 0) { // 从右上角开始寻找
        if (target == matrix[row][col])
            return true;
        else if (target > matrix[row][col])
            row++; // 向下寻找
		else col--;
    }
    return false;
}

• 时间复杂度: $O(rows+cols)$。
• 空间复杂度: $O(1)$。

5. 替换空格

题目描述

将一个字符串中的空格替换成 "%20"。

1
2
3
4
5

Input:
"A B"

Output:
"A%20B"

Solution 1 - “倒排索引”

① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。

② 令 $P1$ 指向字符串原来的末尾位置，$P2$ 指向字符串现在的末尾位置。$P1$ 和 $P2$ 从后向前遍历，当 $P1$ 遍历到一个空格时，就需要令 $P2$ 指向的位置依次填充 02%（注意是逆序的），否则就填充上 $P1$ 指向字符的值。从后向前遍历是为了在改变 $P2$ 所指向的内容时，不会影响到 $P1$ 遍历原来字符串的内容。

③ 当 $P2$ 遇到 $P1$ 时（$P2 \le P1$），或者遍历结束（$P1 < 0$），退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public String replaceSpace(String s) {
    if (s == null || s.length() == 0)
        return "";
    StringBuilder builder = new StringBuilder(s);
    int leftIndex = s.length() - 1;
    for (int i = 0; i <= leftIndex; i++) // 注意这里是 <= 而不是 <
        if (builder.charAt(i) == ' ')
            builder.append("  ");
    // 下面需要的是索引，索引一定要考虑可能会越界的情况
    // 比如, 左右索引都是 length() - 1, 而不是 length().
    int rightIndex = builder.length() - 1;
    while (leftIndex >= 0 && rightIndex > leftIndex) {
        char c = builder.charAt(leftIndex--);
        if (c == ' ') {
            builder.setCharAt(rightIndex--, '0');
            builder.setCharAt(rightIndex--, '2');
            builder.setCharAt(rightIndex--, '%');
        } else {
            builder.setCharAt(rightIndex--, c);
        }
    }
    return builder.toString();
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

Solution 2 - 遍历添加

1
2
3
4
5
6
7
8
9
10
11
12

public String replaceSpace(String s) {
    return s.replace(" ", "%20");
}

public String replaceSpace(String s) {
    StringBuilder res = new StringBuilder();
    for (Character c : s.toCharArray()) {
        if (c == ' ') res.append("%20");
        else res.append(c);
    }
    return res.toString();
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

6. 从尾到头打印链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

Solution 1 - 栈

利用“栈”先进后出的特点，可以实现逆序的效果。

在 $JDK$ 的使用文档里，对于 java.util.Stack 有这样一句话：

“A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. ” For example:

1

Deque<Integer> stack = new ArrayDeque<Integer>();

意思就是推荐使用 $Deque$ 来作为 $Stack$ 的替代品，用 $ArrayDeque$ 作为其实现类，也可以使用 $LinkedList$，具体问题具体分析，看是增删多，还是查询多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int[] reversePrint(ListNode head) {
    if (head == null)
        return new int[0];
    Deque<Integer> stack = new ArrayDeque<>();
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    int index = 0;
    int[] res = new int[stack.size()];
    while (!stack.isEmpty())
        res[index++] = stack.pop();
    return res;
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

Solution 2 - 递归

要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个结点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。

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

public class Solution {

    private List<Integer> tmp = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }

    public void recur(ListNode head) {
        if(head == null)
            return;
        recur(head.next);
        tmp.add(head.val);
    }
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

Solution 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

/**
* 效率更差，只是为了回忆 头插倒序 这个知识点。
*/
public int[] reversePrint(ListNode head) {
    ListNode tmpHead = new ListNode(-1);
    while (head != null) {
        // 保存下一个结点，否则当前结点插入后便找不到下一个开始的目标
        ListNode nextNode = head.next;
        head.next = tmpHead.next;
        tmpHead.next = head;
        head = nextNode;
    }
    List<Integer> result = new ArrayList<>();
    tmpHead = tmpHead.next;
    while (tmpHead != null) { // 当还未遍历到尾部时
        result.add(tmpHead.val);
        tmpHead = tmpHead.next;
    }
    int[] res = new int[result.size()];
    int index = 0;
    for (int num : result)
        res[index++] = num;
    return res;
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

Solution 4 - 两次遍历

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

public int[] reversePrint(ListNode head) {
    // 先获取链表长度，创建对应长度数组
    ListNode currNode = head;
    int len = 0;
    while(currNode != null){
        len++;
        currNode = currNode.next;
    }
    int[] result = new int[len];
    // 再次遍历链表，将值倒序填充至结果数组
    currNode = head;
    while(currNode != null){
        result[len - 1] = currNode.val;
        len--;
        currNode = currNode.next;
    }
    return result;
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$。

7(🌲) . 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 ${1,2,4,7,3,5,6,8}$ 和中序遍历序列 ${4,7,2,1,5,3,8,6}$ ，则重建二叉树并返回。

Solution - 递归

前序遍历：根、左、右

中序遍历：左、根、右

根据前序遍历与中序遍历可以确定一棵二叉树，有以下几个要点(假设序列如题目描述中)：

• 前序遍历的首个结点为当前子树的根节点 $root$，即 $1$
• 在中序遍历中找到当前子树的根节点，那么处于根节点左边的则为左子树中的结点，处于根节点右边的则为左、右子树中的节点。将中序遍历划分为 [left | root | right]，即[4,7,2 | 1 | 5, 3, 8, 6]
• 根据中序遍历[left | root | right]中的左右子树中节点的数量，再将前序遍历划分为[root | left | right]，即[1 | 2, 4, 7 | 3, 5, 6, 8]
• 经过以上三步后可以确定三个结点，即
  • 根节点root(1)
  • 左子树根节点root.left(2)
  • 右子树根节点root.right(3)

递归解析

• 递推参数： 前序遍历中根节点的索引preRoot、中序遍历左边界inLeft、中序遍历右边界inRight

• 终止条件： 当 inLeft > inRight，子树中序遍历为空，说明已经越过叶子节点，此时返回 null。

• 递推工作：

  1. 建立根节点root： 值为前序遍历中索引为preRoot的节点值。
  2. 搜索根节点root在中序遍历的索引i： 为了提升搜索效率，使用哈希表 dic 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 $O(1)$；
  3. 构建根节点root的左子树和右子树： 通过调用 recur() 方法开启下一层递归。
     1. 左子树： 根节点索引为 preRoot + 1 ，中序遍历的左子树的左右边界分别为 inLeft 和i - 1；
     2. 右子树： 根节点索引为 i - inLeft + preRoot + 1（即：根节点索引 $+$ 左子树长度 $ + 1$），中序遍历的右子树的左右边界分别为i + 1和inRight。

• 返回值： 返回 root，含义是当前递归层级建立的根节点 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

class Solution {
    
    private Map<Integer, Integer> dic = new HashMap<>();

    private int[] po; // pre order

    public TreeNode buildTree(int[] preorder, int[] inorder) {
		po = preorder;
        for (int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i); // 存储中序遍历中的结点及其索引
        return recur(0, 0, inorder.length - 1);
	}

    private TreeNode recur(int preRoot, int inLeft, int inRight) {
        // 如果左索引大于了右索引，说明已经到头了。
        if (inLeft > inRight) return null;
        // 1. 构造子树根结点
        TreeNode root = new TreeNode(po[preRoot]);
        // 获取要构造的子树根节点在中序遍历中的位置
        // 然后它左边的都是左子树中的结点
        // 右边的都是右子树中的结点。
        int i = dic.get(po[preRoot]); 
        // 2. 构造子树根节点的左子结点
        root.left = recur(preRoot + 1, inLeft, i - 1);
        // 3. 构造子树根节点的右子结点
        root.right = recur(preRoot + i - inLeft + 1, i + 1, inRight);
        return root;
    }
}

• 时间复杂度：$O(n)$，遍历中序序列 $O(n)$，递归共建立 $n$ 个节点，每层递归中的节点建立、搜索操作占用 $O(1)$，因此递归占用 $O(n)$。

• 空间复杂度：$O(n)$，$HashMap$ 使用 $O(n)$；递归操作递归栈使用 $O(n)$。

8(🌲). 二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个节点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的节点不仅包含左右子节点，同时包含指向父节点的指针。节点结构如下：

1
2
3
4
5
6
7
8
9
10
11
12

public class TreeLinkNode {

    private int val;

    private TreeLinkNode left;

    private TreeLinkNode right;

    private TreeLinkNode next; // 指向父结点的指针

    TreeLinkNode(int val) { this.val = val; }
}

Solution

中序遍历的顺序是左、根、右，所以中序遍历中的第一个节点位于二叉树中最左侧。在中序遍历的过程中：

• 如果一个节点 $root$ 的右子树非空，那么它的下一节点是右子树中的最左节点；
• 否则，向上回溯寻找第一个左指针指向 $root$ 的祖先节点。

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

public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode.right != null) {
        TreeLinkNode node = pNode.right;
        // 寻找当前节点右子树的最左节点，因为遍历顺序左、根、右
        while (node.left != null)
            node = node.left;
        return node;
    } else {
        // 如果右节点为空，则向上寻找第一个左指针指向 root 的祖先节点
        while (pNode.next != null) {
            TreeLinkNode parent = pNode.next;
            if (parent.left == pNode)
                return parent;
            pNode = pNode.next;
        }
    }
    return null;
}

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(1)$。

9. 用两个栈实现队列

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能(若队列中没有元素，deleteHead 操作返回 -1)。

1
2
3
4
5

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]

输出：[null,null,3,-1]

Solution - 辅助栈

队列为先进先出，栈为先进后出，那么利用两个栈，一个作为入栈 stack1，一个作为出栈 stack2，便可以实现队列的先进先出功能。

• 入队操作：将元素压入 stack1 中。
• 出队操作：首先将 stack1 中的元素弹出并且压入到 stack2 中，再将 stack2 中的元素弹出并压入到 stack1 中。

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

/**
* 使用 数组 实现栈的功能
* 54ms, 86.71%
*/
class CQueue {

    private Deque<Integer> stack1, stack2;

    public CQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        // 1. 如果 stack2 非空，顶部本身就是整个头结点。
        if (!stack2.isEmpty())
            return stack2.pop();
        // 2. 在 1 的基础上，stack1 也空，自然删除失败。
        while (stack1.isEmpty())
            return -1;
        // 3. 将 1 中的元素转到 2 中
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
        return stack2.pop();
    }
}

/**
* 使用 链表 实现栈的功能
* 可以看到，在这个过程中主要是插入删除操作
* 而链表相对于数组更适合增删操作，所以本题效率也更高。
* 52ms, 91.92%
*/
class CQueue {

    private LinkedList<Integer> A, B;

    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

    public void appendTail(int value) {
        A.addLast(value);
    }

    public int deleteHead() {
        if(!B.isEmpty())
            return B.removeLast();
        if(A.isEmpty())
            return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }
}

• 时间复杂度：$O(n)$，appendTail用时 $O(1)$, deleteHead用时 $O(n)$。
• 空间复杂度：$O(n)$，最坏情况下，$A、B$ 共保存 $n$ 个元素。

10 - I. 斐波那契数列

接下里的 10-II ~ 10-IV 都是斐波那契数列的衍生题。

题目描述

写一个函数，输入 $n$ ，求斐波那契（$Fibonacci$）数列的第 $n$ 项。斐波那契数列的定义如下：

1
2

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 $0$ 和 $1$ 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 $1e9+7$（$1000000007$），如计算初始结果为：$1000000008$，请返回 $1$。

Solution 1 - 暴力法(自顶向下)

1
2
3
4
5

// 暴力递归 不可取
public int Fibonacci(int n) {
	if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

• 时间复杂度：$O(2^n)$。

Solution 2 - 动态规划(自下而上)

1
2
3
4
5
6
7
8
9

// 动态规划 - 状态转移方程
public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    return dp[n];
}

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

Solution 3 - 记忆化搜索

1
2
3
4
5
6
7
8
9
10
11

// 考虑到第 i 项只与第 i-1 和第 i-2 项有关
// 因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。
public int fib(int n) {
    int pre1 = 0, pre2 = 1, sum;
    for(int i = 0; i < n; i++){
        sum = (pre1 + pre2) % 1000000007;
        pre1 = pre2;
        pre2 = sum;
    }
    return pre1;
}

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

Solution 4 - 快速幂

根据斐波那契数列自身的性质，可以构造如下关系式
$$
\begin{cases}
F_2 = F_1 +F_0 \
F_1 = F_1
\end{cases}{\tag 1}
$$
而表达式 $(1)$ 可以用矩阵表示为
$$
\begin{bmatrix} F_2 \ F_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F_1 \ F_0 \end{bmatrix}
$$

那么
$$
\begin{bmatrix} F_3 \ F_2 \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F_2 \ F_1 \end{bmatrix}=\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^2 \times \begin{bmatrix} F_2 \ F_1 \end{bmatrix}
$$
递推下去可以得到
$$
\begin{bmatrix} F_n \ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F_2 \ F_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} F_1 \ F_0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} 1 \ 0 \end{bmatrix}
$$
Java实现矩阵比较麻烦，学有余力的同学可以看看。

• 时间复杂度：$O(\lg n)$。

10 - II. 青蛙跳台阶问题

题目描述

一只青蛙一次可以跳上 $1$ 级台阶，也可以跳上 $2$ 级台阶。求该青蛙跳上一个 $n$ 级的台阶总共有多少种跳法。

答案需要取模 $1e9+7$（$1000000007$），如计算初始结果为：$1000000008$，请返回 $1$。

Solution - 记忆化搜索

真正的粉丝都是直奔 $Solution$ 🤓

此类求有多少可能性的题目一般都具有递推性质，即 $f(n)$ 依赖于 $f(1),f(2),\dots,f(n-1)$。

假设青蛙跳上第 $n$ 级台阶有 $f(n)$ 种方式，那它可以从第 $n-1$ 级台阶跳一级台阶，也可以从第 $n-2$ 级台阶一次跳两级台阶。也就是：
$$
f(n)=f(n-1)+f(n-2)
$$
这个递推式是不是和斐波那契递推式有点相似？但是它们的初值呢？

• 🐇 斐波那契： $f(0)=0,f(1)=f(2)=1$
• 🐸 青蛙跳： $f(0)=1,f(1)=1,f(2)=2$

1
2
3
4
5
6
7
8
9

public int numWays(int n) {
    int pre2 = 1, pre1 = 1, numWays;
    for (int i = 0; i < n; i++) {
        numWays = (pre2 + pre1) % 1000000007;
        pre2 = pre1;
        pre1 = numWays;
    }
    return pre2;
}

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

10 - III 变态跳台阶

题目描述

一只青蛙一次可以跳上 $1$ 级台阶，也可以跳上 $2$ 级 $\dots$ 它也可以跳上 $n$ 级。求该青蛙跳上一个 $n$ 级的台阶总共有多少种跳法。

Solution - 1: 数学推导

跳上 $n-1$ 级台阶，可以从 $n-2$ 级跳 $1$ 级上去，也可以从 $n-3$ 级跳 $2$ 级上去… 那么
$$
f(n-1) = f(n-2) + f(n-3) + \dots + f(0) {\tag 1}
$$
同样，跳上 $n$ 级台阶，可以从 $n-1$ 级跳 $1$ 级上去，也可以从 $n-2$ 级跳 $2$ 级上去… ，那么
$$
f(n) = f(n-1) + f(n-2) + \dots + f(0) {\tag 2}
$$
由 $(2) - (1)$ 可得 $f(n)=2f(n-1)$。

所以，以 $1$ 为首项，$2$ 为公比的等比数列。

1
2
3

public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}

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

Solution 2 - 动态规划

1
2
3
4
5
6
7
8

public int JumpFloorII(int target) {
    int[] dp = new int[target];
    Arrays.fill(dp, 1);
    for (int i = 1; i < target; i++)
        for (int j = 0; j < i; j++)
            dp[i] += dp[j];
    return dp[target - 1];
}

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n)$。

10 - IV 矩形覆盖

可以用 $2\times1$ 的小矩形横着或者竖着去覆盖更大的矩形。请问用 $n$ 个 $2\times 1$ 的小矩形无重叠地覆盖一个 $2\times n$ 的大矩形，总共有多少种方法？

Solution - 动态规划

当 $n$ 为 $1$ 时，只有一种覆盖方法；当 $n$ 为 $2$ 时，有两种覆盖方法。

要覆盖 $2 \times n$ 的矩形，可以先覆盖 $2 \times 1$ ，再覆盖 $2 \times (n-1)$ 的矩形，或者先覆盖 $2 \times 2$ ，再覆盖 $2 \times (n-2)$ 的矩形。而覆盖 $2\times (n-1)$ 和 $2\times (n-2)$ 的矩形可以看成是子问题。
$$
f(n)=
\begin{cases}
1 &, n=1 \
2 &, n=2 \
f(n-1)+f(n-2) &, n\ge3
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11

public int RectCover(int target) {
    if (target <= 2) return target;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 3; i <= target; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}

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

11. 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 $[3,4,5,1,2]$ 为 $[1,2,3,4,5]$ 的一个旋转，该数组的最小值为 $1$。

1
2

输入：[3,4,5,1,2]
输出：1

$NOTE$：给出的所有元素都大于 $0$，若数组大小为 $0$，请返回 $0$。

Solution - 1 暴力搜索

不就是要求数组里的最小数字嘛，我直接搜索一遍不行吗？净拿修饰词扰乱军心！

1
2
3
4
5
6

public int minArray(int[] numbers) {
    int min = Integer.MAX_VALUE;
    for (int num : numbers)
        min = Math.min(num, min);
    return min;
}

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

Solution - 2 二分搜索

使用暴力搜索，遍历一遍数组就可以获得数组中的最小元素，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。但是题目描述了那么多，肯定不是为了让你使用暴力搜索的。

如果利用数组部分有序这个特点，可以将时间复杂度降低到 $O(\lg n)$。

在数组操作中，只要读出了 有序 的明示或者暗示，无论数据类型是整型还是字符串，首先想到 二分搜索。

在示例 $[3,4,5,1,2]$ 中，可以把 $1$ 看作一个 波谷，也可以认为是一个转折点。可以看到，在 $1$ 的左侧的 $[3,4,5]$ 是有序(升序)的，而在包含 $1$ 在内的 $[1,2]$ 也是有序(升序)的，所以可以认为转折点将数组分成了两个有序数组。

设置 start,end,mid 三个变量，分别代表数组左右两端，以及中间。

• $numbers[mid] > numbers[end]$ : 如果是升序，mid 应该小于 end，但是这里是大于，说明 mid 左侧都是有序的，旋转点 $x$ 一定在 $[mid+1, end]$ 之间，所以接下来应该在 $[mid+1, end]$ 之间寻找旋转点，同时修改 start = mid + 1。
• $numbers[mid] < numbers[end]$ : 说明 mid 右侧是有序的，而旋转点 $x$ 一定在 $[start, mid]$ 之间，所以接下来应该在之 $[start, mid]$ 间寻找旋转点，同时修改 end = mid。
• $numbers[mid] == numbers[end]$ ：例如 $[5,0,1,1,1,1]$，执行end-- 缩小搜索区间。

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

public int minArray(int[] numbers) {
    if (numbers == null || numbers.length == 0)
        return 0;
    int start = 0, end = numbers.length - 1;
    while (start < end) {
        // 二分搜索算法于 1946 年提出，然而第一个没有 bug 的二分搜索算法在 1962 年才出现
        // 原因是 mid = (start + end) / 2 会出现数值溢出
        // 如果 start, end 都在 Integer.MAX_VALUE 的一半左右，相加的结果呢？
        int mid = start + (end - start) / 2;
        if (numbers[mid] > numbers[end]) {
            start = mid + 1;
        } else if (numbers[mid] < numbers[end]) {
        	end = mid;   
        } else end--;
    }
    return numbers[start];
}

• 时间复杂度：$O(\lg n)$，但是在 $[1,1,1,1,1,1,\dots]$ 这种特例下，会退化成 $O(n)$。
• 时间复杂度：$O(1)$。

12. 矩阵中的路径

设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的 $3\times 4$ 的矩阵中包含一条字符串"bfce"的路径。

1
2
3
4
5

[
["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]
]

但矩阵中不包含字符串"abfb"的路径，因为字符串的第一个字符 "b" 占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

Solution - DFS

关于搜索问题，首先想到两种常用的搜索算法，$DFS$、$BFS$。

解题思路： 本问题是典型的矩阵搜索问题，可使用深度优先搜索($DFS$) $+$ 剪枝操作解决。

算法原理：

• 深度优先搜索： 可以理解为暴力方法遍历矩阵中所有字符串可能性，$DFS$ 通过递归，先朝一个方向搜索到底，再回溯至上个结点，沿一个之前未搜索过的方向搜索，如此反复。
• 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况，则立即返回，称之为可行性剪枝。

算法流程

• 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j，当前目标字符在 word 中的索引 k。
• 终止条件：
  • 返回 $true$ : 字符串 word 已全部匹配，即 k = len(word) - 1；
  • 返回 $false$ : $(1)$ 行或列索引越界 $(2)$ 当前矩阵元素与目标字符不符 $(3)$ 当前矩阵元素已访问过。
• 递推工作：
  • 标记当前矩阵元素： 将 board[i][j] 值暂存于变量 tmp，并修改为字符 /，代表此元素已访问过，防止之后搜索时重复访问。
  • 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 || 连接(或运算，代表只需要存在一条可行路径)，并记录结果到 res。
  • 还原当前矩阵元素： 将tmp暂存值还原至 board[i][j] 元素。
• 回溯返回值： 返回 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
34

public boolean exist(char[][] board, String word) {
	char[] words = word.toCharArray();
	for (int i = 0; i < board.length; i++)
		for (int j = 0; j < board[0].length; j++)
			if (dfs(board, i, j, words, 0));
				return true;
	return false;
}

public boolean dfs(char[][] board, int i, int j, char[] words, int k) {
	// 1. 剪枝
	if (i >= board.length || i < 0 || j <  0 || j >= board.length || board[i][j] != words[k])
		return false;

	// 2. 剪枝
	if (k == words.length - 1) return true;

	// 3. 存储矩阵中的当前字符
	char tmp = board[i][j];

	// 4. 置标志位
	board[i][j] = '/';

	// 5. 开始沿四个方向搜索
	boolean res = dfs(board, i + 1, j, words, k + 1)
					|| dfs(board, i - 1, j, words, k + 1)
					|| dfs(board, i, j + 1, words, k + 1)
					|| dfs(board, i, j - 1, words, k + 1);

	// 6. 回填
	board[i][j] = tmp;

	return res;
}

• 时间复杂度：$O(3^kmn)$，最差情况下，需要遍历矩阵中长度为 $k$ 字符串的所有解决方案，时间复杂度为 $O(3^k)$ ；矩阵中共有 $mn$ 个元素可做起始点，时间复杂度为 $O(mn)$ 。
• 空间复杂度：$O(k)$，搜索过程中的递归深度不超过 $k$ ，因此系统递归栈占用 $O(k)$ ，最坏情况下 $k=mn$ 。

13. 机器人的运动范围

题目描述

地上有一个 $m$ 行和 $n$ 列的方格。一个机器人从坐标 $(0,0)$ 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 $k$ 的格子。 例如，当 $k$ 为 $18$ 时，机器人能够进入方格 $(35,37)$，因为 $3+5+3+7 = 18$。但是，它不能进入方格 $(35,38)$，因为 $3+5+3+8 = 19$。请问该机器人能够达到多少个格子？

1
2
3
4
5

输入：m = 2, n = 3, k = 1
输出：3

1 <= n,m <= 100
0 <= k <= 20

本题与矩阵中的路径类似，是典型的矩阵搜索问题。此类问题通常可使用 深度优先搜索($DFS$) 或 广度优先搜索($BFS$)解决。

在介绍 $DFS / BFS$ 算法之前，为提升计算效率，首先讲述两项前置工作：数位之和计算、 搜索方向简化。

数位之和计算：

• 设某数字 $x$ ，向下取整符号 $//$ ，求余符号 $\odot$ ，则有：
  • $x \odot 10$ : 得到 $x$ 的个位数字；
  • $x // 10$ : 令 $x$ 的十进制数向右移动一位，即删除个位数字。
• 因此可通过循环求得数位和 $s$。

1
2
3
4
5
6

def sum(s):
    s = 0
    while x != 0:
        s += x % 10
        x = x // 10
    return s

• 由于机器人每次只能移动一格，因此每次只需要计算 $x$ 到 $x \pm 1$ 的数位和增量。本题说明 $1 \le n,m \le 100$ ，以下公式仅在此范围内适用。
• 数位和增量表达式： 设 $x$ 的数位和为 $s_x$ ， $x+1$ 的数位和为 $s_{x+1}$
  • 当 $(x+1)\odot 10 = 0$ 时： $s_{x+1}=s_x - 8$ ，例如 $19，20$ 的数位和分别为 $10，2$
  • 当 $(x+1)\odot 10 \ne 0$ 时： $s_{x+1}=s_x + 1$ ，例如 $1，2$ 的数位和分别为 $1，2$

1

(x + 1) % 10 != 0 ? s_x + 1 : s_x - 8

搜索方向简化

• 数位和特点: 根据数位和增量公式得知，数位和每逢 进位 突变一次。
• 解的三角形结构:
  • 根据数位和特点，矩阵中 满足数位和的解 构成的几何形状形如多个 等腰直角三角形 ，每个三角形的直角顶点位于 $0,10,20,\dots,0,10,20,\dots$ 等数位和突变的矩阵索引处 。
  • 三角形内的解虽然都满足数位和要求，但由于机器人每步只能走一个单元格，而三角形间不一定是连通的，因此机器人不一定能到达，称之为 不可达解 ; 同理，可到达的解称为 可达解 （本题求此解） 。
• 结论：根据可达解的结构，易推出机器人可仅通过向右和向下移动，访问所有可达解
  • 三角形内部： 全部连通，易证；
  • 两三角形连通处： 若某三角形内的解为可达解，则必与其左边或上边的三角形连通（即相交），即机器人必可从左边或上边走进此三角形。

Solution 1 - DFS

算法解析：

• 递归参数： 当前元素在矩阵中的行列索引 $i,j$ ，两者的数位和 $si,sj$ 。
• 终止条件： 当 $(1)$ 行列索引越界或 $(2)$ 数位和超出目标值 $k$ 或 $(3)$ 当前元素已访问过时，返回 $0$ ，代表不计入可达解。
• 递推工作：
  • 标记当前单元格： 将索引 $(i,j)$ ，存入 $Set$ visited 中，代表此单元格已被访问过。
  • 搜索下一单元格： 计算当前元素的下、右两个方向元素的数位和，并开启下层递归。
• 回溯返回值： 返回1 + 右侧搜索的可达解总数 + 下方搜索的可达解总数，代表本单元格递归搜索的可达解总数。

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

class Solution {

    private int m, n, k;

    private boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    private int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}

• 时间复杂度：$O(mn)$，最差情况下需要遍历所有单元格。
• 空间复杂度：$O(mn)$，$Set$ 内存储所有单元格的索引。

Solution 2 - BFS

算法解析：

• 初始化： 将机器人初始点 $(0, 0)$ 加入队列 queue ；
• 迭代终止条件： queue 为空，代表已遍历完所有可达解。
• 迭代工作：
  1. 单元格出队： 将队首单元格的 索引、数位和 弹出，作为当前搜索单元格。
  2. 判断是否跳过： 当 $(1)$ 行列索引越界 $(2)$ 数位和超出目标值 $k$ $(3)$ 当前元素已访问过时，执行 continue 。
  3. 标记当前单元格 ：将单元格索引 (i, j) 存入 $Set$ visited 中，代表此单元格 已被访问过 。
  4. 单元格入队： 将当前元素的 下方、右方 单元格的 索引、数位和 加入 queue 。
• 返回值： $Set$ visited 的长度 len(visited) ，即可达解的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int movingCount(int m, int n, int k) {
    boolean[][] visited = new boolean[m][n];
    int res = 0;
    Queue<int[]> queue= new LinkedList<>();
    queue.add(new int[] { 0, 0, 0, 0 });
    while(queue.size() > 0) {
        int[] x = queue.poll();
        int i = x[0], j = x[1], si = x[2], sj = x[3];
        if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
        visited[i][j] = true;
        res ++;
        queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
        queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
    }
    return res;
}

• 时间复杂度：$O(mn)$，最差情况下需要遍历所有单元格。
• 空间复杂度：$O(mn)$，$Set$ 内存储所有单元格的索引。

14- I. 剪绳子

题目描述

给定一个正整数 $n$，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回可以获得的最大乘积。

1
2
3
4
5

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

2 <= n <= 58

Solution 1 - 函数极值

• 将正整数 $n$ 拆分为 $a$ 个小数字: $n = n_1 + n_2 + \dots + n_a$；
• 本题等价于求解：$max(n_1 \times n_2 \times \dots n_a)$。

在均值不等式中有
$$
\frac{n_1 + n_2 + \dots + n_a}{a} \ge \sqrt{n_1n_2\dots n_a}
$$
当且仅当 $n_1=n_2=\dots = n_a$ 时等式成立。

推导

• 将绳子按照 $x$ 等分为 $a$ 段，即 $n = ax$ ，则其乘积为 $x^a$ 。观察等式 $(1)$ ，由于 $n$ 为常数，因此当 $x^{\frac{1}{x}}$ 取最大值时，乘积取到最大值。

$$
x^a=x^{\frac{n}{x}}=(x^{\frac{1}{x}})^n \tag{1}
$$

• 所以，将原问题转化为求 $y=x^{\frac{1}{x}}$ 的极大值，因此按照微积分中幂指函数微分求导的方法：

$$
\begin{align*}

两边同时取自然对数得: \quad lny &= \frac{1}{x}lnx\tag{2} \

隐函数求导: \quad \frac{1}{y}y^{‘}&=\frac{1-lnx}{x^2}\tag{3} \

回代\ y=x^{\frac{1}{x}}\ 得: \quad y^{‘}&=\frac{1-lnx}{x^2}x^{\frac{1}{x}}\tag{4}
\end{align*}
$$

令等式 $y^{‘}=0$ ，解得驻点 $x_0=e \approx 2.718$，由题意得：

• 当 $x\in (0,e]$ 时，$y^{‘}\ge0 $，所以 $y$ 单调递增；
• 当 $x \in [e, +\infty)$ 时，$y^{‘}\le0 $，所以 $y$ 单调递减。

所以，$x_0$ 为 $y$ 的极大值点。

• 根据题意可知切分长度需要为整数，因此取 $x=2$ 或 $x=3$ , 而

$$
y_{(3)}^6=(3^{\frac{1}{3}})^6 = 9 \
y_{(2)}^6=(2^{\frac{1}{2}})^6 = 8
$$

经过以上推导之后可以发现拆分规则：

• 最优：将数字 $n$ 拆分成尽可能多个 $3$，余数可能为 $0、1、2$；
• 次优：若余数为 $2$，则保留，不再拆分为 $1+1$；
• 最差：若余数为 $1$；则应把一份 $3+1$ 替换为 $2+2$。

算法流程：

• 当 $n \le 3$ 时，按照规则不应该拆分，但由于题目要求必须拆分，因为必须拆出一个因子 $1$，返回 $n-1$；
• 当 $n > 3$ 时，求 $n$ 除以 $3$ 的整数部分 $a$ 和余数部分 $b$ ，并分为以下三种情况：
  • $b=0$，直接返回 $3^a$；
  • $b=1$，将一个 $1+3$ 替换为 $2+2$，返回 $3^{a-1}\times 4$；
  • $b=2$，返回 $3^a \times 2$。

1
2
3
4
5
6
7

public int integerBreak(int n) {
    if (n <= 3) return n - 1;
    int a = n / 3, b = n % 3;
    if (b == 0) return (int) Math.pow(3, a);
    if (b == 1) return (int) Math.pow(3, a - 1) * 4;
    return (int) Math.pow(3, a) * 2;
}

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

Solution 2 - 动态规划

对于正整数 $n$，当 $n \ge 2$ 时，可以拆分成两个正整数之和。假设 $k$ 是拆分出的第一个正整数，则剩余部分为 $n - k$， $n - k$ 可以不拆分，或者继续拆分成至少两个正整数之和。由于每个正整数对应的最大乘积取决于比它小的正整数的最大乘积，因此可用动态规划求解。

• 状态定义：设 $dp$ 数组为动态规划数组，$dp[i]$ 表示在将正整数 $i$ 拆分成至少两个正整数之和时，目前所有拆分数的最大乘积。
• 状态转移：对于正整数 $i$ ，假设拆出的数为 $j$ 则余下的部分为 $i-j$ ，而对于 $i-j$ 亦有两种选择，要么就此为止，要么继续拆。则
  • 就此为止：此时乘积为 $j \times (i-j)$；
  • 继续拆：即将 $i-j$ 继续拆分，此时乘积为 $j \times dp[i-j]$。

因此状态转移方程为：
$$
dp[i]=max(j\times (i - j), j * dp[i - j]), 1 \le j < i
$$

• 初始值：对于数字 $0$，不可拆，赋值为 $dp[0] = 0$，数字 $1$ 需要拆分成 $0$ 和 $1$，因此 $dp[1] = 0 \times 1 = 0$。

1
2
3
4
5
6
7
8
9
10
11

public int cuttingRope(int n) {
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        int curMax = 0;
        for (int j = 1; j < i; j++) {
            curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
        }
        dp[i] = curMax;
    }
    return dp[n];
}

• 时间复杂度：$O(n^2)$，其中 $n$ 是给定的正整数。对于从 $2$ 到 $n$ 的每一个整数都要计算对应的 $dp$ 值，计算一个整数对应的 $dp$ 值需要 $O(n)$ 的时间复杂度，因此总的时间复杂度为 $O(n^2)$。
• 空间复杂度：$O(n)$，其中 $n$ 是给定的正整数。创建一个数组 $dp$，其长度为 $n + 1$。

14- II. 剪绳子 II

题目描述

给你一根长度为 $n$ 的绳子，请把绳子剪成整数长度的 $m$ 段（$m、n$都是整数，$n>1$并且 $m>1$），每段绳子的长度记为 $k[0],k[1], \dots ,k[m - 1]$ 。请问 $k[0]\times k[1]\times \cdots \times k[m - 1]$ 可能的最大乘积是多少？

例如，当绳子的长度是 $8$ 时，我们把它剪成长度分别为 $2、3、3$ 的三段，此时得到的最大乘积是 $18$。

答案需要取模 $1e9+7（1000000007）$，如计算初始结果为：$1000000008$，请返回 $1$。

Solution - 二分法: 点我去看

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3;
        for (int a = n / 3 - 1; a > 0; a /= 2) {
            if (a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if (b == 0) return (int) (rem * 3 % p);
        if (b == 1) return (int) (rem * 4 % p);
        return (int) (rem * 6 % p);
    }
}

• 时间复杂度：$O(log_2 N)$。其中 $N = a$，二分法为对数级别复杂度，每轮仅有求整、求余、次方运算。
• 空间复杂度：$O(1)$。变量 $a, b, p, x, rem$ 使用常数大小额外空间。

15. 二进制中 1 的个数

题目描述

输入一个整数，输出该数二进制表示中 $1$ 的个数。

Solution 1 - 位运算

如果一个整数不为 $0$，那么这个整数至少有一位是 $1$。如果我们把这个整数减 $1$，那么原来处在整数最右边的 $1$ 就会变为 $0$，原来在 $1$ 后面的所有的 $0$ 都会变成 $1$ (如果最右边的 $1$ 后面还有 $0$ 的话)。其余所有位将不会受到影响。

1
2
3

n   	= 10101000
n-1     = 10100111
n&(n-1) = 10100000

• 减 $1$ 的结果是把最右边的一个 $1$ 开始的所有位都取反了。
• 把一个整数减去 $1$ ，再和原整数做(与&)运算，会把该整数最右边一个 $1$ 变成 $0$。
• 那么一个整数的二进制有多少个 $1$，就可以进行多少次这样的操作。

1
2
3
4
5
6
7
8

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count++;
        n &= (n - 1);
    }
    return count;
}

• 时间复杂度：$O(n)$，最坏情况下 $n$ 的二进制表示中含有 $n$ 个 $1$。
• 空间复杂度： $O(1)$。

Solution 2 - 逐位与

逐位判断

• 根据 与运算 定义，设二进制数字 $n$ ，则有：
  • 若 $n & 1 = 0$ ，则 $n$ 二进制位最右一位为 $0$；
  • 若 $n & 1 = 1$ ，则 $n$ 二进制位最右一位为 $1$。
• 循环判断
  • 若 $n$ 最右一位为 $1$ ，结果加 $1$；
  • 将 $n$ 右移一位(本题要求把数字看作无符号数，因此采用无符号右移。)

1
2
3
4
5
6
7
8

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;
}

• 时间复杂度：$O(\log_2 M)$，其中 $M$ 代表输入数字 $n$ 中最高位 $1$ 的位置，例如输入 $16$，则 $16_{10}=1111_2$，那么 $M = log_2 16 = 4$。
• 空间复杂度： $O(1)$。

Solution 3 - JDK

1
2
3

public int hammingWeight(int n) {
    return Integer.bitCount(n);
}

16. 数值的整数次方

题目描述

给定一个 $double$ 类型的浮点数 $base$ 和 $int$ 类型的整数 $exponent$。求 $base$ 的 $exponent$ 次方。保证 $base$ 和 $exponent$ 不同时为 $0$。不得使用库函数，同时不需要考虑大数问题。

Solution - 快速幂

二进制角度

设 $x=base, n=exponent$。

• 十进制整数 $n$ 可以表示为二进制的 $b_m\dots b_3b_2b_1$ ，则有
  • 二进制转十进制： $n=1b_1+2b_2+4b_3+\cdots+2^{m-1}b_m$
  • 幂的二进制展开： $x^n=x^{1b_1+2b_2+4b_3+\cdots + 2^{m-1}b_m}=x^{1b_1}x^{2b_2}x^{4b_3}\dots x^{2^{m-1}b_m}$
• 因此，根据以上操作，可在循环中计算 $x^{2^0b_1},x^{2^1b_2},\dots,x^{2^{m-1}b_m}$ 的值，并将所有 $x^{2^{i-1}b_i}$ 累积相乘即可。
  • 当 $b_i=0$ 时， $x^{2{i-1}}b_i=1$。
  • 当 $b_i=1$ 时， $x^{2{i-1}}b_i=x^{2^{i-1}}$。

二分角度
$$
x^n=
\begin{cases}
x^{\frac{n}{2}}·x^{\frac{n}{2}}, & n%2=0\
x·x^{\frac{n}{2}}·x^{\frac{n}{2}}, & n%2=1
\end{cases}
$$

• 幂结果获取
  • 根据二分推导，可通过循环 $x=x^2$ 操作，每次把幂从 $n$ 降至 $n/2$ ，直至将幂降为 $0$ ；
  • 设 $res = 1$ ，则初始状态 $x^n=x^n\times res$ 。在循环二分时，每当 $n$ 为奇数时，将多出的一项 $x$ 乘入 $res$ ，则最终可转化为 $x^n=x^0 \times res = res$。
• 转化为位运算
  • 向下取整 $n/2$ 等价于右移一位 $n>>1$；
  • 判断奇偶性操作 $n%2$ 等价于 $n&1$。
• 注意点：当 $n<0$ 时，把问题转化至 $n\ge 0$ 的范围内，即执行 $x=1/x,n=-n$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public double myPow(double x, int n) {
    if (x == 0) return 0;
    long b = n;
    double res = 1.0;
    if (b < 0) {
        x = 1 / x;
        b = -b;
    }
    while (b > 0) {
        // 如果为奇数时
        if ((b & 1) == 1) res *= x;
        x *= x;
        b >>= 1; // 相当于 b / 2
    }
    return res;
}

• 时间复杂度：$O(\log_2n)$，二分的时间复杂度为对数级别。
• 时间复杂度：$O(1)$，有限个变量。

17. 打印从1到最大的n位数

题目描述

输入数字 $n$，按顺序打印出从 $1$ 到最大的 $n$ 位十进制数。比如输入 $3$，则打印出 $1、2、3$ 一直到最大的 $3$ 位数 $999$ 。

Solution-分治算法

根据题目要求，需要考虑两个问题：

• 最大的 $n$ 位数(记为 $end$ )和位数 $n$ 的关系：例如最大的 $1$ 位数是 $9$ ，最大的二位数是 $99$ ，因此可以得到：

$$
end = 10^n - 1
$$

• 大数越界问题：根据题意，不用考虑。

因此，只需要定义区间 $[1,10^n-1]$ 和步长 $1$，通过 $for$ 循环生成列表 $res$ 并返回即可。

实际上，本题的主要考点是大数越界情况下的打印。需要解决以下三个问题：

• 表示大数的数据类型：无论是 short/int/long 及其他变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。
• 生成数字的字符串集：
  • 使用 int 类型时，每轮可通过 +1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 “$9999$” 至 “$10000$” 需要从个位到千位循环判断，进位 $4$ 次。
  • 观察可知，生成的列表实际上是 $n$ 位 $0\sim9$ 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。
• 递归生成全排列：先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 $n=2$ 时(数字范围 $1 \sim 99$ )，固定十位为 $0 \sim 9$ ，按顺序依次开启递归，固定个位 $0 \sim 9$ ，终止递归并添加数字字符串。

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 {

    private int[] res;

    private int nine = 0, count = 0, start, n;

    private char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public int[] printNumbers(int n) {
		this.n = n;
        res = new int[(int) Math.pow(10, n) - 1];
        num = new char[n];
        start = n - 1; // 字符左边界
        dfs(0);
        return res;
	}

    void dfs(int x) {
        if (x == n) {
            String s = String.valueOf(num).substring(start);
            if (!s.equals("0")) res[count++] = Integer.parseInt(s);
            if (n - start == nine) start--;
            return;
        }
        for (char i : loop) {
            if (i == '9') nine++;
            num[x] = i;
            dfs[x + 1];
        }
        nine--;
    }
}

• 时间复杂度：$O(10^n)$，递归生成的排列数量为 $10^n$。
• 空间复杂度：$O(n)$，字符列表 $num$ 使用线性大小的额外空间。

18. 删除链表中的结点

题目描述

给定单向链表的头指针和一个要删除的结点的值，定义一个函数删除该结点。返回删除后的链表的头结点。

题目保证链表中节点的值互不相同。

1
2
3

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

Solution - 双指针

删除值为 val 的节点可分为两步：定位节点、修改引用。

• 定位结点：遍历链表，直到找到 node.val == val 时跳出，即可定位目标结点。
• 修改结点：设 cur 指向当前结点，pre 为 cur 的前驱结点，cur.next 为 cur 的后继结点，则执行 pre.next = cur.next，实现删除 cur 结点的功能。

算法流程

• 特例处理：当应删除头结点 head 时，直接返回 head.next 即可。
• 初始化：pre = head; cur = head.next;
• 定位结点：当 cur 为空，或者 cur.val == val 时跳出遍历。
  • 保存当前结点索引，执行 pre = cur；
  • 遍历下一结点，即 cur = cur.next。
• 删除结点：
  • 若 cur 指向某结点(即找到了与 val 值相等的结点)，则执行 pre.next = cur.next ，实现删除结点的操作。
  • 若 cur == null，代表链表中不包含 val 的结点。
• 返回值：返回头结点 head 即可。

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

public ListNode deleteNode(ListNode head, int val) {
    if (head.val == val)
        return head.next;
    ListNode pre = head, cur = head.next;
    while (cur != null && cur.val != val) {
        // 如果当前结点不等于空(未到链表尾部) 并且当前结点的值不是目标值时
        // 从头开始遍历 寻找值等于 val 的结点
        pre = cur;
        cur = cur.next;
    }
    // 既然上面的 while 循环条件是 && 条件 而 && 条件存在短路效应
    // 所以循环后的结果存在 || 结果
    // 也就是经过上面的 while 循环后，可能找到了链表中值等于 val 的结点
    // 也可能未找到结点 只有在找到结点时才进行删除
    if (cur.val == val)
        pre.next = cur.next;
    // 反正最后要返回 head, 所以不判断 if (head == null) 了.
    return head;
}

• 时间复杂度：$O(n)$，可能需要遍历整个链表搜索要删除的结点。
• 空间复杂度：$O(1)$，两个辅助结点。

19. 正则表达式匹配

请实现一个函数用来匹配包含 . 和 * 的正则表达式。模式中的字符 . 表示任意一个字符，而 * 表示它前面的字符可以出现任意次(含 $0$ 次)。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 aaa 与模式 a.a 和 ab*ac*a 匹配，但与 aa.a 和 ab*a 均不匹配。

1
2
3
4
5
6
7
8
9
10
11

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

Solution - 动态规划

感慨一下，自己现在终于能做出 DP 的题了。

关于为什么考虑动态规划？

1. 经验：只要读题时思维乱成一团，八成就是动态规划。关于字符串的很多复杂问题也都要用到动态规划，典型的有：最长公共子序列、最长公共子串、最长上升子序列等。
2. 理论：本题具有最优子结构性质，但是不容易发现。
3. 通常拥有数学中递推性质的都可以用动态规划来解决。

题目中的匹配是一个「逐步匹配」的过程：我们每次从字符串 $p$ 中取出一个字符或者「字符 + *」的组合，并在 $s$ 中进行匹配。对于 $p$ 中一个字符而言，它只能在 $s$ 中匹配一个字符，匹配的方法具有唯一性；而对于$p$ 中「字符 + *」的组合而言，它可以在 $s$ 中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。

不少前辈说「动态规划」问题最难的地方在于「定义状态转移方程」，但是本题最困难的地方在于「定义状态」，也就是读懂题意。在诸如问「最大最小最多最少」的问题中一般问题最后要求的结果是什么，「状态定义」就是什么。

状态定义：$f[i][j]$ 表示 $s$ 的前 $i$ 个字符能否与 $p$ 中前 $j$ 个字符匹配。

状态转移：在一维 $DP$ 中， $dp[i]$ 通常与 $dp[i-1]$ 有关系，但条件限定的话也可能与 $dp[i-1]、dp[i-3]$ 有直接关系；在二维 $DP$ 中， $dp[i][j]$ 通常与 $dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]$ 有关系，如果条件限定的话，步长可能也会大一点；在三维及之后的问题，我想你已经明白我的意思了。

在高中数学中有种方法叫做归纳推理法，它的核心思想是假设 $n=k$ 时结论成立，那么 $n=k+1$ 时也成立，这是一种从前向后的方法，而寻找「状态转移方程」的过程可以简单理解为这个方法的逆过程，也就是从后向前的过程寻找状态，也就是我想要达到 $dp[i][j]$ 这个状态，我需要 $dp[i-1][j],dp[i][j-1],dp[i-1][j-1]$ 中的一种或多种状态满足什么样的条件。在计算「最大最小最多最少」问题时还可以想到高中排列组合中的「分步用乘法，分类用加法」这句话。

铺垫了这么多， $f[i][j]$ 与 $f[i-1][j],f[i][j-1],f[i-1][j-1]$ 建立关系时需要满足什么样的条件？

• 如果 $p$ 的第 $j$ 个字符是字母，那么想要匹配的话， $s$ 中的第 $i$ 个字母需要与其相同，即

$$
f[i][j]=
\begin{cases}
f[i-1][j-1], &s[i]=p[j] \
false,&s[i]\ne p[j]
\end{cases}
$$

• 如果 $p$ 的第 $j$ 个字符是「*」，那么可以使用 $p$ 的第 $j-1$ 个字母零次或多次。匹配零次时有

$$
f[i][j]=f[i][j-2]
$$

意思是，第 $j$ 位字符「*」没有用，第 $j-1$ 位又跟 $s$ 的第 $i$ 位不等，那就只能依靠 $p$ 的第 $i-2$ 位了。

在匹配多次时，有
$$
f[i][j]=
\begin{cases}
f[i][j]=f[i-1][j-2], \quad s[i]=p[j-1] \
f[i][j]=f[i-2][j-2], \quad s[i-1]=s[i]=p[j-1] \
f[i][j]=f[i-3][j-2], \quad s[i-1]=s[i-1]=s[i]=p[j-1] \
\dots
\end{cases}
$$
「字母 + *」的组合在匹配的过程中，本质上只会有两种情况：

1. 匹配 $s$ 末尾的字符，将该字符丢弃之后，组合仍可以继续匹配；
2. 不匹配字符，将该组合丢弃，不再进行匹配。

于是得到
$$
f[i][j]=
\begin{cases}
f[i-1][j]\ or\ f[i][j-2], & s[i]=p[j-1]\
f[i][j-2], & s[i]\ne p[j-1]
\end{cases}
$$

• 如果 $p$ 的第 $j$ 个字符是「.」，那么 $p[j]$ 一定成功匹配 $s$ 中的任意一个小写字母。

三种情况下的状态转移方程合并
$$
f[i][j]=
\begin{cases}
if(p[j]\ne 「*」)=
\begin{cases}
f[i-1][j-1], &matches(s[i],p[j]) \
false, &otherwise
\end{cases} \
otherwise=
\begin{cases}
f[i-1][j]\ or\ f[i][j-2], &matches(s[i],p[j-1]) \
f[i][j-2], &otherwise
\end{cases}
\end{cases}
$$
其中，matches(a, b) 函数用于判断字符是否匹配。

状态初始化：$f[0][0]=true$，即两个空字符串是匹配的。

返回值：$f[m][n]$，其中 $m,\ n$ 分别问两个字符串的长度，这里 $dp$ 数组多开一行一列，但是不用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length() - 1;
    boolean[][] f = new boolean[m + 1][n + 1];
    f[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[j][j] = f[i][j - 2];
                if (matches(s, p, i, j - 1))
                    f[i][j] = f[i][j] || f[i - 1][j];
            } else {
                if (matches(s, p, i, j))
                    f[i][j] = f[i - 1][j - 1];
            }
        }
    }
    return f[m][n];
}

public boolean matches(String s, String p, int i, int j) {
    if (i == 0) return false;
    if (p.charAt(j - 1) == '.') return true;
    return s.charAt(i - 1) == p.charAt(j - 1);
}

• 时间复杂度：$O(mn)$，需要计算出所有的状态，并且每个状态在进行转移时的时间复杂度为 $O(1)$。
• 空间复杂度：$O(mn)$，即为存储所有状态使用的空间。

20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”$+100$”、”$5e2$”、”$-123$”、”$3.1416$”、”$0123$”都表示数值，但”$12e$”、”$1a3.14$”、”$1.2.3$”、”$+-5$”都不是。

Solution-有限状态自动机

本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。

字符类型：空格「 」，数字「$0 \sim 9$」，正负号「$+-$」，小数点「$.$」幂符号「$e$」。

状态定义：按照字符串从左到右的顺序，定义以下 $9$ 种状态。

• 开始的空格
• 幂符号前的正负号
• 小数点前的数字
• 小数点、小数点后的数字
• 当小数点前为空格时，小数点、小数点后的数字
• 幂符号
• 幂符号后的正负号
• 幂符号后的数字
• 结尾的空格

合法的结束状态有：$2,3,7,8$。

算法流程：

• 初始化：
  • 状态转移表 $states$ ，设 $states[i]$ ，其中 $i$ 为所处状态， $states[i]$ 使用哈希表存储可转移至的状态。键值对 $(key,value)$ 含义：若输入 $key$ ，则可从状态 $i$ 转移至状态 $value$ 。
  • 当前状态 $p$ ：起始状态初始化为 $p=0$ 。
• 状态转移循环：遍历字符串 $s$ 的每个字符 $c$
  • 记录字符类型 $t$ ：分为三种情况
    • 当 $c$ 为正负号时， t = 's'；
    • 当 $c$ 为数字时，t = 'd'；
    • 否则，t = c，即用字符本身表示字符类。
  • 终止条件：若字符类型 $t$ 不在哈希表 $states[p]$ 中，说明无法转移至下一状态，因此直接返回 $False$。
  • 状态转移：状态 $p$ 转移至 $states[p][t]$。
• 返回值：跳出循环后，若状态 $p \in 2,3,7,8$ ，说明结尾合法，返回 $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

class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else t = c;
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

• 时间复杂度：$O(n)$，其中 $n$ 为字符串 $s$ 的长度，判断需遍历字符串，每轮状态转移使用 $O(1)$ 时间。
• 空间复杂度：$O(1)$， $states,p$ 使用常数大小的额外空间。

21. 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

1
2
3
4
5
6

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

1 <= nums.length <= 50000
1 <= nums[i] <= 10000

Solution 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

public int[] exchange(int[] nums) {
    // 考虑对撞指针
    // 左指针从左向右扫描，右指针从右向左扫描
    // 当左指针扫描到偶数时停下，右指针扫描到奇数时停下, 然后交换数值。
    if (nums == null || nums.length == 0 || nums.length == 1)
        return nums;
    int l = 0, r = nums.length - 1;
    while (l < r) {
        while (l < r && !isEven(nums[l])) l++;
        while (l < r && isEven(nums[r])) r--;
        swap(nums, l, r);
    }
    return nums;
}

// 在计算机中, 偶数的最后一位是0, 而奇数的最后一位是1
public boolean isEven(int num) { // 是否偶数
    return (num & 1) == 0;
}

private void swap(int[] nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}

• 时间复杂度：$O(n)$，扫描一遍数组。
• 空间复杂度：$O(1)$，有限个变量。

Solution 2 : 快慢指针

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

class Solution {
    public int[] exchange(int[] nums) {
        // 快慢指针
        // 慢指针用来找偶数 快指针用来找奇数 然后交换
        // 在交换之前能够保证慢指针左边都是奇数，慢指针与快指针之间的都是偶数
        // 在交换后，指针移动一格，快指针继续向后寻找
        if (nums == null || nums.length == 0 || nums.length == 1)
            return nums;
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (!isEven(nums[fast])) {
                swap(nums, slow, fast);
                slow++;
            }
            fast++;
        }
        return nums;
    }

    // 在计算机中, 偶数的最后一位是 0, 而奇数的最后一位是 1。
    public boolean isEven(int num) { // 是否偶数
        return (num & 1) == 0;
    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

• 时间复杂度：$O(n)$，扫描一遍数组。
• 空间复杂度：$O(1)$，有限个变量。

22. 链表中倒数第k个节点

题目描述

输入一个链表，输出该链表中倒数第 $k$ 个节点。为了符合大多数人的习惯，本题从 $1$ 开始计数，即链表的尾节点是倒数第 $1$ 个节点。例如，一个链表有 $6$ 个节点，从头节点开始，它们的值依次是 $1、2、3、4、5、6$。这个链表的倒数第 $3$ 个节点是值为 $4$ 的节点。

1
2
3

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

Solution-双指针

两个解题思路：

• 遍历链表一次，获取链表的长度 $n$ ，然后再遍历一次链表，但是这次只遍历到 $n-k$ 这个位置即可，此时即为链表的倒数第 $k$ 个结点。
• 使用双指针，让快的指针先走 $k$ 步，那么当快的指针到达到达链表尾部时，慢的指针正好到达倒数第 $k$ 个结点。

算法流程：

• 初始化：设快指针为 former，慢指针为 latter，初始时都指向头结点 head。
• 创建步差：让 former 先走 $k$ 步。
• 同步前进：循环中，让 former 和 latter 同步前进，直至 former 走过链表尾结点时跳出循环。
• 返回值：返回 latter。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null || k < 0) return head;
        ListNode former = head;
        while (former != null && k-- > 0) p1 = p1.next;
         // 说明链表总结点个数不足 k 个
        if (k > 0) return null;
        ListNode latter = head;
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

• 时间复杂度：$O(n)$，遍历一次链表。
• 空间复杂度：$O(1)$。 两个辅助结点。

LeetCode链表常见问题

24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

1
2
3
4
5
6
7

反转一个单链表。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

Solution 1 -双指针

算法流程：

• 初始化：定义两个指针，cur 指向当前结点， pre 指针指向当前结点的下一个结点。
• 局部反转：每次让 pre.next 指向 cur。
• 同步移动：pre 和 cur 同步移动一个结点。
• 返回值：当 pre == null 时，返回 cur.

1
2
3
4
5
6
7
8
9
10
11
12

public ListNode reverseList(ListNode head) {
    if (head == null) return null;
    ListNode pre = null, temp = null;
    ListNode cur = head;
    while (cur != null) {
        temp = cur.next; // 临时保存当前结点的下一个结点
        cur.next = pre; // 将当前结点指向前一个结点
        pre = cur; //  之前的结点移动一次
        cur = temp; // 当前结点移动一次
    }
    return pre;
}

• 时间复杂度：$O(n)$，遍历一次链表。
• 空间复杂度：$O(1)$。 两个辅助结点。

Solution 2 - 递归

在实现逆序或者反转相关的操作时可以考虑使用“栈”这种数据结构，要么自己实现，要么调用系统栈，而提到系统栈，首先就要想到递归。递归可能不太好理解，这里有个幻灯片解释。

1
2
3
4
5
6
7
8
9
10
11
12

public ListNode reverseList(ListNode head) {
    // 1. 递归一定要有终止条件
    if (head == null || head.next == null) return head;
    // 2. 这一步获取的是链表的最后一个结点
    ListNode tail = reverseList(head.next);
    // 3. 从尾到头重新链接上
    // 1->2->3->4->5 变为 1->2->3->4 5，上面的 tail 指向 5, head.next = tail
    // 接下来要做的就是让 5 指向 4(head)
    head.next.next = head;
    head.next = null;
    return tail;
}

• 时间复杂度：$O(n)$，遍历一次链表，每次链接链表的操作为 $O(1)$。
• 空间复杂度：$O(n)$, 系统递归栈需要存储链表中的所有结点。

25. 合并两个已排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

Solution - 双指针

两个重要的隐含条件：有序、递增。

所以可以考虑使用双指针 $l_1,l_2$ 分别遍历两链表，根据 $l_1.val,l_2.val$ 的大小关系来确定结点添加顺序，两结点指针交替前进，直至遍历完毕。

由于初始状态合并链表中无结点，所以需要设置一个头结点。

算法流程：

1. 初始化：创建伪头结点 $dummy$，结点 $cur$ 指向 $dummy$。
2. 循环合并：当 $l_1$ 或 $l_2$ 为空时跳出。
   1. 当 $l_1.val < l_2.val$ 时: $cur$ 的后继结点指定为 $l1$ ， $l_1$ 向前走一步；
   2. 当 $l_1.val \ge l_2.val$ 时: $cur$ 的后继结点指定为 $l2$ ， $l_2$ 向前走一步；
   3. 结点 $cur$ 向前走一步，即 $cur = cur.next$。
3. 合并剩余尾部：跳出时有两种情况，即 $l_1$ 为空或 $l_2$ 为空。
   1. 若 $l_1\ne null$ ，将 $l_1$ 添加至结点 $cur$ 结点之后；
   2. 否则，将 $l_2$ 添加至结点 $cur$ 之后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;
        ListNode dummy = new ListNode(0), cur = dummy;
        while (l2 != null && l1 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 != null ? l1 : l2);
        return dummy.next;
    }
}

• 时间复杂度：$O(m+n)$，需要遍历两个链表。
• 空间复杂度：$O(1)$，两个辅助结点。

26(🌲). 树的子结构

题目描述

输入两棵二叉树 $A$ 和 $B$ ，判断 $B$ 是不是 $A$ 的子结构。(约定空树不是任意一个树的子结构)。

$B$ 是 $A$ 的子结构， 即 $A$ 中有出现和 $B$ 相同的结构和节点值。

Solution - 先序遍历

若树 $B$ 是树 $A$ 的子结构，则子结构的根节点可能为树 $A$ 的任意一个节点。因此，判断树 $B$ 是否是树 的子结 $A$ 构，需完成以下两步工作：

1. 先序遍历 $A$ 的每个节点 $n_A$ ，isSubStructure(A, B)
2. 判断树 $A$ 中以 $n_A$ 为根节点的子树是否包含树 $B$ ，recur(A, B)

名词规定：树 $A$ 的根节点记作 节点 $A$ ，树 $B$ 的根节点称为节点 $B$ 。

recur(A, B)函数：

1. 终止条件：
   1. 当结点 $B$ 为空：说明树 $B$ 已匹配完成，返回 $true$
   2. 当结点 $A$ 为空：说明已经越过树 $A$ 叶子结点，即匹配失败，返回 $false$
   3. 当结点 $A、B$ 的值不同：说明匹配失败，返回 $false$
2. 返回值：
   1. 判断 $A$ 和 $B$ 的左子结点是否相等，即recur(A.left, B.left)
   2. 判断 $A$ 和 $B$ 的右子结点是否相等，即recur(A.right, B.right)

isSubstructure(A, B)函数：

1. 特例处理：当树 $A$ 为空或树 $B$ 为空时，直接返回 $false$。
2. 返回值：若树 $B$ 是树 $A$ 的子结构，则必须满足以下三种情况之一，因此可用或 || 连接。
   1. 以 节点 $A$ 为根节点的子树 包含树 $B$ ，对应 recur(A, B)；
   2. 树 $B$ 是 树 $A$ 左子树 的子结构，对应 isSubStructure(A.left, B)；
   3. 树 $B$ 是 树 $A$ 右子树 的子结构，对应 isSubStructure(A.right, B)。

      1 2 3 4 5 6 7 8 9 10 11 12 13 14

      public boolean isSubStructure(TreeNode A, TreeNode B) { // 只有在 A B 均不为空时才有可能出现子结构 // 1. 以 A 为根结点的子树包含 B recur(A, B) // 2. 以 A 的左结点为根结点的子树包含 B isSubStructure(A.left, B) // 3. 以 A 的右结点为根结点的子树包含 B isSubStructure(A.right, B) return (A != null && B != null) || (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)); } public boolean recur(TreeNode A, TreeNode B) { if (B == null) return true; // 如果 B 的子树为空 说明已经到达了B的叶子结点，也就是说整个树B都包含在了A中 if (A == null || A.val != B.val) return false; // 如果 A 的子树为空，说明已经到达了A的叶子结点，不会再有子树 // 继续判断 A B 的左右子结点是否相同 return recur(A.left, B.left) && recur(A.right, B.right); }

• 时间复杂度：$O(MN)$，其中 $M,N$ 分别为两树种结点的数量。
• 空间复杂度：$O(M)$，当$A、B$ 都退化为链表时，递归调用深度最大。

27(🌲).二叉树的镜像

题目描述

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

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

输入：
	 4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：
	 4
   /   \
  7     2
 / \   / \
9   6 3   1

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

0 <= 节点个数 <= 1000

Solution 1 - 递归

递归遍历二叉树，交换每个节点的 左/右 子节点，即可生成二叉树的镜像。

递归解析

1. 终止条件：当节点 $root$ 为空时返回 $null$ ；
2. 递推工作：
   1. 初始化节点 $tmp$，用于暂存 $root$ 的左子节点；
   2. 递归右子节点，将返回值作为 $root$ 的左子节点；
   3. 递归左子节点，将返回值作为 $root$ 的右子节点。
3. 返回值：返回 $root$。

Question: 为何要暂存 $root$ 左子节点？

Answer：在递归右子节点完毕后，$root.left$ 的值已发生改变。

1
2
3
4
5
6
7

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

• 时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 $O(n)$ 时间。
• 空间复杂度： $O(n)$ ，最差情况下（当二叉树退化为链表），递归时系统需使用 $O(n)$ 大小的栈空间。

扩展：

• 本题竟是 $Homebrew$ 之父当年没能写出的 226. 翻转二叉树
• 前序、中序、后序、层次遍历解本题

Solution 2 - 辅助栈

利用栈（或队列）遍历树的所有节点 $node$ ，并交换每个 $node$ 的左 / 右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode t = stack.pop();
        if (t.left != null) stack.push(t.left);
        if (t.right != null) stack.push(t.right);
        TreeNode temp = t.left;
        t.left = t.right;
        t.right = temp;
    }
    return root;
}

• 时间复杂度： $O(n)$ ，其中 $n$ 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 $O(n)$ 时间。
• 空间复杂度： $O(n)$ ，最差情况下（当为满二叉树时），栈 $stack$ 最多同时存储 $n/2$ 个节点，占用 $O(n)$ 额外空间。

28(🌲). 对称的二叉树

题目描述

实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 $[1,2,2,3,4,4,3]$ 是对称的。

1
2
3
4
5
6
7

    1
   / \
  2   2
 / \ / \
3  4 4  3

0 <= 节点个数 <= 1000

Solution - 递归

大部分人看到本题时应该都已经有思路了，本题最大的问题其实并不是思路的问题，而是是否有能力把思路表达出来的问题。

除去递归终止条件，要判断的主要有三点，

• 两个指针指向的节点的 $val$ 是否相等；
• $L$ 的左子树是否与 $R$ 的右子树对称；
• $L$ 的右子树是否与 $R$ 的左子树对称。

递归终止条件：

• 两个指针都为 $null$ 则返回 $true$ ；
• 两个指针其中之一为 $null$ 则返回 $false$ 。

1
2
3
4
5
6
7
8
9
10
11

public boolean isSymmetric(TreeNode root) {
    if (root == null) return false;
    // 如果树不为空
    return recur(root.left, root.right);
}

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

• 时间复杂度：$O(n)$，$n$ 为节点数量，每次递归可以判断一对节点是否对称，最多执行 $n/2$ 次；
• 空间复杂度：$O(n)$，二叉树退化为链表时系统使用 $O(n)$ 栈空间。

29. 顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

1
2

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

Solution - 收缩

逆时针打印矩阵，也可以理解为打印顺序为：从左向右，自上而下，从右向左，自下而上。因此考虑设置矩阵的上、下、左、右四个边界，模拟矩阵收缩。

算法流程：

1. 空值处理：当 matrix 为空时，直接返回空列表。
2. 初始化：设置上下左右四边界，top,bottom,left,right，用于矩阵向内收缩。
3. 循环打印：按”从左向右，自上而下，从右向左，自下而上”的方式循环，每个方向打印的过程中包括以下三件事：
   1. 根据边界打印，将结果存储到 res 中尾部；
   2. 边界向内收缩 $1$；
   3. 判断边界是否相遇，若相遇则跳出。
4. 返回值：返回结果 res。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public int[] spiralOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return new int[0];
    int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    int x = 0;
    int[] res = new int[(bottom + 1) * (right + 1)];
    while (true) {
        // 从左向右
        for (int i = left; i <= right; i++) res[x++] = matrix[top][i];
        if (++top > bottom) break; // 上边界向下收缩
        // 自上而下
        for (int i = top; i <= bottom; i++) res[x++] = matrix[i][right];
        if (--right < left) break; // 右边界向左收缩
        // 从右向左
        for (int i = right; i >= left; i--) res[x++] = matrix[bottom][i];
        if (--bottom < top) break; // 下边界向上收缩
        // 自下而上
        for (int i = bottom; i >= top; i--) res[x++] = matrix[i][left];
        if (++left > right) break; // 左边界向右收缩
    }
    return res;
}

• 时间复杂度：$O(MN)$，其中 $M,N$ 分别为矩阵行列。
• 空间复杂度：$O(1)$，四个方向值。

30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 $min$ 函数在该栈中，调用 $min,push$ 及 $pop$ 的时间复杂度都是 $O(1)$。

1
2
3
4
5
6
7
8
9
10

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

各函数的调用总次数不超过 20000 次

Solution-辅助栈

将 min() 函数复杂度降为 $O(1)$ ，可通过建立辅助栈实现

• 数据栈 stackData: 用于存储所有元素，保证入栈 push()、pop()、top() 等功能。
• 辅助栈 stackHelper: 用于以非严格降序存储stackData中的数据，stackHelper 的栈顶元素始终为 stackData 中的最小元素，返回 stackHelper 的栈顶元素，即可实现 min() 函数的功能。

在操作的过程中为了保证 stackData 的非严格单调性，需要注意：

• 在 push() 操作时，设待 push 的元素为 e，如果 stackHelper 为空或者 e <= stackHelper.peek()，那么将 e 也 push 到 stackHelper 中；
• 在 pop() 操作时，设待 pop() 的元素为 e，如果 e == stackHelper.peek()，那么从 stackHelper 也进行 pop()。

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

public class MinStack {

    private Stack<Integer> stackData, stackHelper;

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

    public void push(int x) {
		stackData.add(x);
        if (stackHelper.isEmpty() || x <= stackHelper.peek())
            stackHelper.add(x);
    }

    public void pop() {
        if (!stackData.isEmpty())
            if (stackData.pop().equals(stackHelper.peek()))
                stackHelper.pop();
    }

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

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

• 时间复杂度：$O(1)$，不必多言。
• 空间复杂度：$O(n)$，最坏情况下，比如输入一个单调递减的数列，那么 stackHelper 将需要存储所有元素。

31. 栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 ${1,2,3,4,5}$ 是某栈的压栈序列，序列 ${4,5,3,2,1}$ 是该压栈序列对应的一个弹出序列，但 ${4,3,5,1,2}$ 就不可能是该压栈序列的弹出序列。

1
2
3
4
5

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Solution

因为栈的数据操作具有 先入后出 的特性，因此某些弹出序列是无法实现的。考虑借用一个辅助栈 $stack$ ，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。

• 入栈操作：按照压栈序列的顺序执行；
• 出栈操作：每次入栈后，循环判断“栈顶元素=弹出序列的当前元素”是否成立，降负荷弹出序列顺序的栈顶元素全部弹出。

算法流程：

1. 初始化：辅助栈 $stack$ ，弹出序列的索引 $i$。
2. 遍历压栈序列：设各元素为 $num$
   1. $num$ 入栈；
   2. 循环出栈：若 $stack$ 的栈顶元素=弹出序列元素 $popped[i]$ ，则执行出栈与 i++。
3. 返回值：若 $stack$ 为空，则此弹出序列合法。

1
2
3
4
5
6
7
8
9
10
11
12

public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new ArrayDeque<>();
    int i = 0;
    for (int num : pushed) {
        stack.push(num);
        while (!stack.isEmpty() && stack.peek() == popped[i]) {
            stack.pop();
            i++;
        }
    }
    return stack.isEmpty();
}

• 时间复杂度 $O(N)$ ： 其中 $N$ 为列表 $pushed$ 的长度；每个元素最多入栈与出栈一次，即最多共 $2N$ 次出入栈操作。
• 空间复杂度 $O(N)$ ： 辅助栈 $stack$ 最多同时存储 $N$ 个元素。

32(🌲). 从上到下打印二叉树 I

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

1
2
3
4
5
6
7
8
9
10

给定二叉树: [3,9,20,null,null,15,7]
	3
   / \
  9  20
    /  \
   15   7

输出：[3,9,20,15,7]

节点总数 <= 1000

Solution - 层次遍历

树的遍历除了前序遍历、中序遍历、后序遍历之外，还有层次遍历，题目描述其实就是对层次遍历的解释。

在层次遍历中使用 $BFS$ 需要用到队列，在 $DFS$ 中往往需要用到栈。

算法流程

1. 特例处理：当树的根节点为空，则直接返回空列表 [] ；
2. 初始化：打印结果列表 res = [] ，包含根节点的队列 queue = [root]；
3. $BFS$ 循环：当队列 queue 为空时跳出；
   1. 出队：队首元素出队，记为 node；
   2. 打印：将 node.val 添加至列表 tmp 尾部；
   3. 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue。
4. 返回值：返回 res 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

• 时间复杂度 $O(n)$ ： $n$ 为二叉树的节点数量，即 $BFS$ 需循环 $n$ 次。
• 空间复杂度 $O(n)$ ： 最差情况下，即当树为满二叉树时，最多有 $n/2$ 个树节点同时在 $queue$ 中，使用 $O(n)$ 大小的额外空间。

32(🌲). 从上到下打印二叉树 II

题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

给定二叉树: [3,9,20,null,null,15,7]

	3
   / \
  9  20
    /  \
   15   7

输出结果:
[
  [3],
  [9,20],
  [15,7]
]

节点总数 <= 1000

Solution - 层次遍历

本题解法与上题几乎完全相同，唯一的不同点在与 $BFS$ 循环中对每层结点进行分层。

算法流程

1. 特例处理：当树的根节点为空，则直接返回空列表 [] ；
2. 初始化：打印结果列表 res = [] ，包含根节点的队列 queue = [root]；
3. $BFS$ 循环：当队列 queue 为空时跳出；
   1. 申请一个用于存储当前层节点的临时列表 tmp；
   2. 当前层打印循环：循环次数为 queue.size()
      1. 出队：队首元素出队，记为 node；
      2. 打印：将 node.val 添加至列表 tmp 尾部；
      3. 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
4. 返回值：返回 res 即可。

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

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> tmp = new ArrayList<>();
        for (int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            tmp.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(temp);
    }
    return res;
}