剑指Offer第四章：解决面试题的思路
总结
- 想清楚再编码
- 分析方法：举例子、画图
第1节：画图分析方法
对于二叉树、二维数组、链表等问题，都可以采用画图的方法来分析，例如：
- 面试题19二叉树的镜像：通过画图发现，实质就是在遍历树的同时交换非叶节点的左右子节点。
- 面试题20顺时针打印矩阵：通过画图发现，实质就是一圈一圈的打印数组。
- 面试题26复杂链表的复制：画图，发现复制链表的过程，分三个步骤：复制节点，设置random指针，拆分两个链表。
面试题 19：二叉树的镜像（反转二叉树）
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
题目分析
LeetCode 226. Invert Binary Tree
何为镜像：即照镜子得到的像，与原像是左右颠倒的。
求二叉树镜像：即反转二叉树。
求解思路：对于每个非叶子节点，反转其左右孩子节点。既可以用递归也可以用迭代。
题目典故：著名的Homebrew的作者Max Howell在面试Google时被问到这题，并且没有做出来，原推文
- Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
题目考点及相关题目
问题本质：树的DFS或BFS遍历。
扩展：掌握非递归的实现。
我的代码如下：
1.递归方法：
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}
2.非递归DFS（栈）:
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
final Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()) {
final TreeNode node = stack.pop();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
return root;
}
3.非递归BFS（队列）：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
final Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return root;
}
面试题 20：顺时针打印矩阵
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
题目分析
LeetCode 54. Spiral Matrix
顺时针打印矩阵：即螺旋矩阵输出。
规律：一圈一圈的输出数组里的数据，注意边界条件不好确定时，多画几个图就很清楚了。
边界： “上”肯定要打印，打印“右”的条件是至少有两行，打印“下”至少两行两列；打印“左”至少要有三行两列。
题目考点及相关题目
多画图，帮助理解。
相关题目有：LeetCode 59. Spiral Matrix II
我的代码如下：
解法一：
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if(matrix.length <= 0) return res;
int m = matrix.length, n = matrix[0].length;
int min = Math.min(m, n);
int k = min%2 == 0 ? (min/2 - 1) : min/2;
for(int i = 0; i <= k; i ++)
spiral(matrix, i, res, m, n);
return res;
}
public void spiral(int[][] matrix, int k, List<Integer> res, int m, int n){
// 上
for(int i = k; i < n - k; i ++)
res.add(matrix[k][i]);
// 右
for(int i = k + 1; i < m - k; i ++)
res.add(matrix[i][n-k-1]);
// 下(加判断条件，排除两种情况：只有一列时，只有一行时)
if(k < n - k - 1 && k < m - k - 1){
for(int i = n - k - 2; i >= k; i --)
res.add(matrix[m-k-1][i]);
}
// 左(加判断条件，排除两种情况：只有一列时，只有不超过2行时)
if(k < n - k - 1 && k < m - k - 2){
for(int i = m - k - 2; i > k; i --)
res.add(matrix[i][k]);
}
}
}
解法二：
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if (matrix.length == 0) {
return res;
}
int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for (int j = colBegin; j <= colEnd; j ++) {
res.add(matrix[rowBegin][j]);
}
rowBegin++;
// Traverse Down
for (int j = rowBegin; j <= rowEnd; j ++) {
res.add(matrix[j][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
// Traverse Left
for (int j = colEnd; j >= colBegin; j --) {
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;
if (colBegin <= colEnd) {
// Traver Up
for (int j = rowEnd; j >= rowBegin; j --) {
res.add(matrix[j][colBegin]);
}
}
colBegin ++;
}
return res;
}
}
第2节：举例分析方法
通过举例子，理解题目意思并找到规律；最后也以用例子来测试程序是否完善。
- 面试题22栈的压入、弹出序列：通过举实际栈的例子，来模拟栈的压入和弹出操作，就能发现隐藏的规律。
- 面试题24二叉搜索树的后序遍历序列：理解后续遍历的特点，并找到递归方法的思路。
- 面试题21包含min函数的栈：用一个栈来专门来存储当前栈中的最小值。
面试题 21：包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该函数中，调用min、push、及pop的时间复杂度都是$O(1)$。
题目分析
- 使用两个栈，一个数据栈，一个最小数栈
- 每次存放数据时，若存放的数据比此时最小栈中的栈顶值要大，那么将最小数栈栈顶元素再存一次（即增加一个栈顶元素），如果要存的数据比栈顶元素小，那么就将此值也存入最小值栈。
- 出栈时，两栈都要同时出数据，使得最小数栈的栈顶元素总是目前数据栈中的最小值。两个栈中的元素个数总是保持相等。
题目考点及相关题目
用一个辅助栈来存储最小值元素。
相关题目：LeetCode 239. Sliding Window Maximum
我的代码如下：
class MinStack {
Stack<Integer> data;
Stack<Integer> min;
public MinStack() {
// do initialize if necessary
data = new Stack<Integer>();
min = new Stack<Integer>();
}
public void push(int x) {
if (!min.isEmpty() && min.peek() < x) min.push(min.peek());
else min.push(x);
data.push(x);
}
public void pop() {
min.pop();
data.pop();
}
public int top() {
return data.peek();
}
public int getMin() {
return min.peek();
}
}
面试题 22：栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示 栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列
1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但4、3、5、1、2就不可能是该压栈序列的弹出序列。
题目分析
用一个辅助栈stack来存储压栈序列，如果下一个弹出的数字刚好是辅助栈顶数字，那么直接弹出，并将辅助栈内栈顶数字也弹出；如果下一个弹出的数字不在辅助栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到下一个需要弹出的数字压入栈顶为止。如果 所有的数字都 压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
题目考点及相关题目
栈的压入、弹出操作。
我的代码如下：
public boolean isPopOrder(List<Integer> push, List<Integer> pop){
if(pop.size() != push.size()) return false;
Stack<Integer> stack = new Stack<Integer>();
while(!pop.isEmpty()){
if(stack.isEmpty()) stack.push(push.remove(0));
while(stack.peek() != pop.get(0) && !push.isEmpty()) stack.push(push.remove(0));
if(push.isEmpty() && stack.peek() != pop.get(0)) return false;
else{
stack.pop();
pop.remove(0);
}
}
return true;
}
面试题 23：从上往下打印二叉树
题目：从上往下拓印出二叉树的每个结点，同层的结点 按照从左到右的顺序 打印。
题目分析
LeetCode 102. Binary Tree Level Order Traversal
即树的层次遍历，用到了队列。
题目考点及相关题目
层次遍历，队列。
相关题目：LeetCode 103. Binary Tree Zigzag Level Order Traversal、LeetCode 107. Binary Tree Level Order Traversal II、LeetCode 111. Minimum Depth of Binary Tree
我的代码如下：
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> rs = new ArrayList<List<Integer>>();
LinkedList<TreeNode> level = new LinkedList<TreeNode>();
if(root != null) level.push(root);
while(!level.isEmpty()){
int levelNum = level.size();
List<Integer> tmp = new ArrayList<Integer>();
for(int i=0; i<levelNum; i++){
TreeNode temp = level.removeFirst();
tmp.add(temp.val);
if(temp.left != null) level.add(temp.left);
if(temp.right != null) level.add(temp.right);
}
rs.add(tmp);
}
return rs;
}
}
面试题 24：二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回
true，否则返回false。假设输入的数组的任意两个数字都互不相同。
题目分析
经过分析可知，后序遍历得到的序列的特点：
- 最后一个数字是该二叉搜索树的根节点，前面的序列又可以分成两部分；
- 前一部分是根节点的左子树，它们的值都比根节点值小；
- 后一部分是根节点的右子树，它们的值都比根节点值大。
因此，需要再次判断该二叉树的左子树序列和右子树序列是否满足以上特点。很明显地，这是一个递归操作的过程。
题目考点及相关题目
二叉搜索树的概念以及后序遍历的特点
相关题目：输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历的结果。
我的代码如下：
1.我的递归程序，没有经过完整的校验
public class Solution{
public boolean VerifySequenceOfBST(int[] sequence){
if(sequence.length <= 0) return false;
return verify(sequence, 0, sequence.length - 1);
}
public boolean verify(int[] sequence, int start, int end){
if(start >= end) return true;
int root = sequence[end];
int i = start, j = end - 1;
// 找到左右子序列的分界处，经验证，无论是只有左子树还是只有右子树，或者左右子树均有的情况，都会满足i == j + 1；否则说明该序列不满足二叉搜索树的性质。
while(i < end && sequence[i] < root) i ++;
while(j >= start && sequence[j] > root) j --;
if(i != j + 1) return false;
return verify(sequence, start, j) && verify(sequence, i, end - 1);
}
}
2.标准答案请见P158。
面试题 25：二叉树中和为某一值的路径
题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶子节点所经过的节点形成一条路径。
题目分析
- 首先这种题肯定是对树遍历，而树的遍历要么是深搜，要么是广搜；
- 对于深搜，那就是递归了，关键问题在：怎么计算并存储遍历到当前节点时的和，可以用我的方法，用一个变量来记录到达当前节点的和，或者方法二中比较巧妙的思想。
- 深搜递归总会遇到的问题是：变量（中间结果）在传递的过程中会发生改变，比如方法一中的：list和cur，一定要注意还原，这是非常重要的一步，否则会导致先前的结果仍然在list当中。这也是形参和实参的问题。
- 对于广搜，那么就要用额外的变量存储到达每个节点的和，这种方法的空间复杂度比较高，这里就不仔细介绍了。
题目考点及相关题目
树的前序遍历，也就是DFS
相关题目：Path Sum、Binary Tree Paths
我的代码如下：
1.我的深搜代码
public class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null) return res;
pathSumWithDFS(root, root.val, new ArrayList<Integer>(Arrays.asList(root.val)), sum);
return res;
}
public void pathSumWithDFS(TreeNode root, int cur, List<Integer> list, int sum){
if(root.left == null && root.right == null){
if(cur == sum) {
// 这是十分推荐的写法
List<Integer> temp = new ArrayList<Integer>(list);
res.add(temp);
}
return;
}
//if(cur >= sum) return; 注意这一句不能加，因为可能节点值有负值。
if(root.left != null) {
list.add(root.left.val);
pathSumWithDFS(root.left, cur + root.left.val, list, sum);
// 这一步非常重要
list.remove(list.size()-1);
}
if(root.right != null) {
list.add(root.right.val);
pathSumWithDFS(root.right, cur + root.right.val, list, sum);
// 这一步非常重要
list.remove(list.size()-1);
}
}
}
2.他人更加简洁的代码（用栈更好，而且它这个函数不用记录到目前节点的和，而是用sum-当前节点的值，方法更加巧妙）
public class Solution {
private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
public void pathSumInner(TreeNode root, int sum, Stack<Integer>path) {
path.push(root.val);
if(root.left == null && root.right == null)
if(sum == root.val) resultList.add(new ArrayList<Integer>(path));
if(root.left!=null) pathSumInner(root.left, sum-root.val, path);
if(root.right!=null)pathSumInner(root.right, sum-root.val, path);
// 这一步非常重要
path.pop();
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root==null) return resultList;
Stack<Integer> path = new Stack<Integer>();
pathSumInner(root, sum, path);
return resultList;
}
}
第3节：分解让复杂问题简单化
分治法：先把大问题分解成若干个小问题，然后再逐个解决的思想。
- 面试题27二叉搜索树与双向链表：把大问题分解成左子树和右子树两个小问题，然后再把转换左右子树得到的链表和根结点链接起来就解决了整个问题。
- 面试题28字符串的排列：整个字符串的排列是一个大问题，而第一个字符之后的字符串的排列就是一个小问题，因此分解问题，并采用递归思想解决。
面试题 26：复杂链表的复制
题目：请实现函数
ComplexListNode *Clone(ComplexListNode *pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点，还有一个m_pSibling指向的任意结点或者NULL。
题目分析
LeetCode 138. Copy List with Random Pointer
- 首先，要理解什么是深拷贝。
-深拷贝是指在拷贝对象时，同时会对引用指向的对象进行拷贝。
-相对应的，浅拷贝是指在拷贝对象时，对于基本数据类型的变量会重新复制一份，而对于引用类型的变量只是对引用进行拷贝。- 此题深拷贝链表，主要分为如下两步：
-第一步复制原始链表中的结点，并用next指针连接起来。
-第二步设置每个结点的random指针。- 第一步很容易就可以完成，主要在于第二步，很容易就会犯浅拷贝的错。只是复制了对象的引用，导致结果出错。
- 第二步中复制random指针，应该是根据原链表中节点N的random指针指向的节点S，找到新链表中所对应的S'，而不是简单地将新链表中的N'的random指针指向S。
- 至于如何找到对应的S'，有两种方法：
-要么都从头指针开始遍历经过指针N，N'且经过相同步分别找到S, S'。这样的话，时间复杂度会到O(n^2)。
-要么就是用空间换时间，使用Map存储新旧链表中的对应的节点对<N, N'>- 还有另外一种方法，既不用开辟新的空间来存储节点，也不用从头遍历查找。方法比较巧妙：
>- 在第一步复制原始链表结点时，新结点链接在原结点后面，然后再将新结点的next指针指向原结点的next指针，具体如下：
链表.png
- 第二步链接新结点的random指针就很容易了，它对应在原结点的random指针的后面一个结点，具体如下：
链表二.png
题目考点及相关题目
把复杂链表的复制过程分解成三个步骤：复制结点、设置random指针、拆分两个链表。
相关题目：Clone Graph
我的代码如下：
1.使用HashMap，空间换时间，时间复杂度$O(n)$，空间复杂度$O(n)$。
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) return head;
RandomListNode newHead = new RandomListNode(0);
RandomListNode p = newHead;
RandomListNode s = newHead;
RandomListNode q = head;
RandomListNode r = head;
Map<RandomListNode, RandomListNode> nodes = new HashMap<RandomListNode, RandomListNode>();
while(q != null){
RandomListNode tmp = new RandomListNode(q.label);
p.next = tmp;
p = p.next;
nodes.put(q, p);
q = q.next;
}
//p.next = null;
while(r != null){
s.next.random = nodes.get(r.random);
s = s.next;
r = r.next;
}
return newHead.next;
}
}
2.使用链接方式，方法巧妙，时间复杂度$O(n)$，空间复杂度$O(1)$。
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) return null;
RandomListNode p = head, q = p;
while(p != null){
RandomListNode tmp = new RandomListNode(p.label);
RandomListNode next = p.next;
p.next = tmp;
tmp.next = next;
p = next;
}
while(q != null){
RandomListNode t = q.next;
t.random = q.random == null ? null : q.random.next;
q = t.next;
}
RandomListNode newHead = head.next, s = head;
while(s != null){
RandomListNode n = s.next;
s.next = n.next;
s = s.next;
n.next = s == null ? null : s.next;
}
return newHead;
}
}
面试题 27：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
题目分析
- 注意题目要求：不能创建任何新的结点，只能调整指针的指向
- 因为在二叉树中，每个结点都有两个指向子结点的指针，在双向链表中每个结点也有两个指针，它们分别指向前、后两个结点。因此，在理论上有可能实现二叉搜索树和排序的双向链表的转换。
- 由于要求转换之后双向链表是排好序的，而二叉搜索树的中序遍历刚好是一个有序数组，因此此题的遍历方法肯定是中序遍历二叉搜索树。
- 具体思想：如下图，当遍历到根节点
10时，我们将树看成三部分，根节点10、根节点为6的左子树、根节点为14的右子树，可以想像一下，如果左子树已经排好序成为了双向链表，那么它的最后一个节点（也就是左子树里的最大值8）的右指针将指向10，同理，10的右指针将指向右子树里的最小值12，如下图所示：很明显，上述就是一个递归过程。
中序.png
中序2.png
题目考点及相关题目
分治法的本质：将复杂问题分解成小问题，然后递归调用函数功能，即可完成对复杂问题的求解。
相关题目：LeetCode 114. Flatten Binary Tree to Linked List
我的代码如下：
1.未经验证的Java代码，时间复杂度较高，全耗在了遍历左子树，找到最后一个节点上面， $O(n^2)$。
public TreeNode Convert(TreeNode root){
if(root == null) return null;
TreeNode head = Convert(root.left);
if(head == null) head = root;
else{
TreeNode p = head;
while(p.right != null) p = p.right;
p.right = root;
root.left = p;
}
TreeNode right = Convert(root.right);
root.right = right;
if(right != null)
right.left = root;
return head;
}
2.标准答案见P170
面试题 28：字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符
a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
题目分析
- 先不谈解题思路，先看题目要求：打印出该字符串中字符的所有排列，如果字符串存在相同字符，那么打印出的结果也肯定会包含相同的字符串，但是只从题目字面上理解，是没有让我们去重的，因此可以不用管打印出的字符串中是否存在相同的情况；但是如果让我们去重的话，先使用list.contains(o)判断一下是否存在，再决定是否添加。
- 求解思路：
-将一个字符串看成由两部分组成：第一部分为它的第一个字符，第二部分是后面的所有字符；
-我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换；然后固定第一个字符，求后面所有字符的排列。
-很明显，这是典型的递归思路。
题目考点及相关题目
本质：按照一定要求摆放若干数字，可以先求出这些数字的所有排列，然后再一一判断每个排列是否满足题目所给定的要求。
本题扩展：求字符的所有组合（如对于字符串
abc的所有组合a, b, c, ab, ac, bc, abc），求解思路仍然差不多，将输入的n个字符看成两部分：第一个字符和后面所有字符，在构成长度m的组合时，分两种情况考虑：1）如果包含第一个字符，则需要从后面的所有字符中选取m-1个字符，2）如果不包含第一个字符，则从后面的所有字符中选取m个字符。分析到这里，就感觉可以用动态规划了，递推公式：$f(n,m) = f(n-1, m-1) + f(n-1, m)$，具体实现就不细说了。
相关题目：八皇后问题（回溯）；8个数字放在正方体8个顶点上，问是否有可能使得正方体三组相对的面上的4个顶点的和都相等。
我的代码如下：
public List<String> Permutation(String string){
List<String> res = new ArrayList<String>();
Permutation(new StringBuffer(string), 0, res);
return res;
}
public static void Permutation(StringBuffer sb, int start, List<String> list){
if(start == sb.length()) {
// 这是去重后的结果
/* if(!list.contains(sb.toString())){
list.add(sb.toString());
System.out.println(sb);
}*/
// 不去重的结果
list.add(sb.toString());
}else{
for(int i = start; i < sb.length(); i ++){
char temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(start));
sb.setCharAt(start, temp);
Permutation(sb, start + 1, list);
// 对更改的内容进行还原
temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(start));
sb.setCharAt(start, temp);
}
}
}
第4节：本章小结
当遇到难题，没有任何思路时，一般的求解办法：画图、举例、分解。
具体算法就会涉及到分治法、动态规划法，都是通过分解问题而来。
