剑指offer解析-上（Java实现）

个人技术博客：www.zhenganwen.top

以下题目按照牛客网在线编程排序，所有代码示例代码均已通过牛客网OJ。

二维数组的查找

题目描述

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

public boolean Find(int target, int [][] arr) {

}
复制代码

解析

暴力方法是遍历一遍二维数组，找到target就返回true，时间复杂度为O(M * N)（对于M行N列的二维数组）。

由题可知输入的数据样本具有高度规律性（单独一行的数据来看是有序的，单独一列的数据来看也是有序的），因此考虑能否有一个比较基准在一次的比较中根据有序性淘汰不必再进行遍历比较的数。有序、查找，由此不难联想到二分查找，我们可以借鉴二分查找的思路，每次选出一个数作为比较基准进而淘汰掉一些不必比较的数。二分是选取数组的中位数作为比较基准的，因此能够保证每次都淘汰掉二分之一的数，那么此题中有没有这种特性的数呢？我们不妨举例观察一下：

不难发现上图中对角线上的数是其所在行和所在列形成的序列的中位数，不妨选取右上角的数作为比较基准，如果不相等，那么我们可以淘汰掉所有它左边的数或者它所有下面的，比如对于target = 6，因为(0,3)位置上的4 < 6，因此(0,3)位置及其同一行的左边的所有数都小于6因此可以直接淘汰掉，淘汰掉之后问题就变为了从剩下的三行中找target，这与原始问题是相似的，也就是说每一次都选取右上角的数据为比较基准然后淘汰掉一行或一列，直到某一轮被选取的数就是target或者已经淘汰得只剩下一个数的时候就一定能得出结果了，因此时间复杂度为被淘汰掉的行数和列数之和，即O(M + N)，经过分析后不难写出如下代码：

public boolean Find(int target, int [][] arr) {
    //input check
    if(arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0){
        return false;
    }
    int i = 0, j = arr[0].length - 1;
    while(i != arr.length - 1 && j != 0){
        if(target > arr[i][j]){
            i++;
        }else if(target < arr[i][j]){
            j--;
        }else{
            return true;
        }
    }

    return target == arr[i][j];
}
复制代码

值得注意的是每次选取的数都是第一行最后一个数，因此前提是第一行有数，那么就对应着输入检查的arr[0] == null || arr[0].length == 0，这点比较容易忽略。

总结：经过分析其实不难发现，此题是在一维有序数组使用二分查找元素的一个变种，我们应该充分利用数据本身的规律性来寻找解题思路。

替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public String replaceSpace(StringBuffer str) {
    
}
复制代码

此题考查的是字符串这个数据结构的数组实现（对应的还有链表实现）的相关操作。

解析

String.replace简单粗暴

如果可以使用API，那么可以很容易地写出如下代码：

public String replaceSpace(StringBuffer str) {
    //input check
    //null pointer
    if(str == null){
        return null;
    }
    //empty str or not exist blank
    if(str.length() == 0 || str.indexOf(" ") == -1){
        return str.toString();
    }

    for(int i = 0 ; i < str.length() ; i++){
        if(str.charAt(i) == ' '){
            str.replace(i, i + 1, "%20");
        }
    }

    return str.toString();
}
复制代码

时间O(n)，空间O(n)

但是如果面试官告诉我们不许使用封装好的替换函数，那么目的就是在考查我们对字符串数组实现方式的相关操作。由于是连续空间存储，因此需要在创建实例时指定大小，由于每个空格都使用%20替换，因此替换之后的字符串应该比原串多出空格数 * 2个长度，实现如下：

public String replaceSpace(StringBuffer str) {
    //input check
    //null pointer
    if(str == null){
        return null;
    }
    //empty str or not exist blank
    if(str.length() == 0 || str.indexOf(" ") == -1){
        return str.toString();
    }

    char[] source = str.toString().toCharArray();
    int blankCount = 0;
    for(int i = 0 ; i < source.length ; i++){
        blankCount = (source[i] == ' ') ? blankCount + 1 : blankCount;
    }
    char[] dest = new char[source.length + blankCount * 2];
    for(int i = source.length - 1, j = dest.length - 1 ; i >=0 && j >=0 ; i--, j--){
        if(source[i] == ' '){
            dest[j--] = '0';
            dest[j--] = '2';
            dest[j] = '%';
            continue;
        }else{
            dest[j] = source[i];
        }
    }

    return new String(dest);
}
复制代码

时间O(n)，空间O(1)

如果还要求不能有额外空间，那我们就要考虑如何复用输入的字符串，如果我们从前往后遇到空格就将空格及其之后的两个位置替换为%20，势必会覆盖空格之后的两个字符，比如hello world会被替换成hello%20rld，因此我们需要在长度被扩展后的新串中从后往前确定每个索引上的字符。比如使用一个originalIndex指向原串中的最后一个字符索引，使用newIndex指向新串的最后一个索引，每次将originalIndex上的字符复制到newIndex上并且两个指针前移，如果originalIndex上的字符是空格，则将newIndex依次填充0,2,%，然后两者再前移，直到两者都到首索引位置。

public String replaceSpace(StringBuffer str) {
    //input check
    //null pointer
    if(str == null){
        return null;
    }
    //empty str or not exist blank
    if(str.length() == 0 || str.indexOf(" ") == -1){
        return str.toString();
    }

    int blankCount = 0;
    for(int i = 0 ; i < str.length() ; i++){
        blankCount = (str.charAt(i) == ' ') ? blankCount + 1 : blankCount;
    }
    int originalIndex = str.length() - 1, newIndex = str.length() - 1 + blankCount * 2;
    str.setLength(newIndex + 1); //需要重新设置一下字符串的长度，否则会报越界错误
    while(originalIndex >= 0 && newIndex >= 0){
        if(str.charAt(originalIndex) == ' '){
            str.setCharAt(newIndex--, '0');
            str.setCharAt(newIndex--, '2');
            str.setCharAt(newIndex, '%');
        }else{
            str.setCharAt(newIndex, str.charAt(originalIndex));
        }
        originalIndex--;
        newIndex--;
    }

    return str.toString();
}
复制代码

总结：要把思维打开，对于数组的操作我们习惯性的以for(int i = 0 ; i < arr.length ; i++)的形式从头到尾来操作数组，但是不要忽略了从尾到头遍历也有它的独到之处。

反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

public ListNode ReverseList(ListNode head) {
        
}
复制代码

解析

此题的难点在于无法通过一个单链表结点获取其前驱结点，因此我们不仅要在反转指针之前保存当前结点的前驱结点，还要保存当前结点的后继结点，并在下一次反转之前更新这两个指针。

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public ListNode ReverseList(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode pre = null, p = head, next;
    while(p != null){
        next = p.next;
        p.next = pre;
        pre = p;
        p = next;
    }

    return pre;
}
复制代码

从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      
}
复制代码

解析

此题的难点在于单链表只有指向后继结点的指针，因此我们无法通过当前结点获取前驱结点，因此不要妄想先遍历一遍链表找到尾结点然后再依次从后往前打印。

递归，简洁优雅

由于我们通常是从头到尾遍历链表的，而题目要求从尾到头打印结点，这与前进后出的逻辑是相符的，因此你可以使用一个栈来保存遍历时走过的结点，再通过后进先出的特性实现从尾到头打印结点，但是我们也可以利用递归来帮我们压栈，由于递归简洁不易出错，因此面试中能用递归尽量用递归：只要当前结点不为空，就递归遍历后继结点，当后继结点为空时，递归结束，在递归回溯时将“当前结点”依次添加到集合中

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList();
        //input check
        if(listNode == null){
            return res;
        }
        recursively(res, listNode);
        return res;
    }

    public void recursively(ArrayList<Integer> res, ListNode node){
        //base case
        if(node == null){
            return;
        }
        //node not null
        recursively(res, node.next);
        res.add(node.val);
        return;
    }
}
复制代码

反转链表

还有一种方法就是将链表指针都反转，这样将反转后的链表从头到尾打印就是结果了。需要注意的是我们不应该在访问用户数据时更改存储数据的结构，因此最后要记得反转回来：

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> res = new ArrayList();
    //input check
    if(listNode == null){
        return res;
    }
    return unrecursively(listNode);
}

public ArrayList<Integer> unrecursively(ListNode node){
    ArrayList<Integer> res = new ArrayList<Integer>();
    ListNode newHead = reverse(node);
    ListNode p = newHead;
    while(p != null){
        res.add(p.val);
        p = p.next;
    }
    reverse(newHead);
    return res;
}

public ListNode reverse(ListNode node){
    ListNode pre = null, cur = node, next;
    while(cur != null){
        //save predecessor
        next = cur.next;
        //reverse pointer
        cur.next = pre;
        //move to next
        pre = cur;
        cur = next;
    }
    //cur is null
    return pre;
}
复制代码

总结：面试时能用递归就用递归，当然了如果面试官就是要考查你的指针功底那你也能just so so不是

重建二叉树

题目描述

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

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
   
}
复制代码

解析

先序序列的特点是第一个数就是根结点而后是左子树的先序序列和右子树的先序序列，而中序序列的特点是先是左子树的中序序列，然后是根结点，最后是右子树的中序序列。因此我们可以通过先序序列得到根结点，然后通过在中序序列中查找根结点的索引从而得到左子树和右子树的结点数。然后可以将两序列都一分为三，对于其中的根结点能够直接重建，然后根据对应子序列分别递归重建根结点的左子树和右子树。这是一个典型的将复杂问题划分成子问题分步解决的过程。

递归体的定义，如上图先序序列的左子树序列是2,3,4对应下标1,2,3，而中序序列的左子树序列是3,2,4对应下标0,1,2，因此递归体接收的参数除了保存两个序列的数组之外，还需要指明需要递归重建的子序列分别在两个数组中的索引范围：TreeNode rebuild(int[] pre, int i, int j, int[] in, int m, int n)。然后递归体根据pre的i~j索引范围形成的先序序列和in的m~n索引范围形成的中序序列重建一棵树并返回根结点。

首先根结点就是先序序列的第一个数，即pre[i]，因此TreeNode root = new TreeNode(pre[i])可以直接确定，然后通过在in的m~n中查找出pre[i]的索引index可以求得左子树结点数leftNodes = index - m，右子树结点数rightNodes = n - index，如果左（右）子树结点数为0则表明左（右）子树为null，否则通过root.left = rebuild(pre, i' ,j' ,in ,m' ,n')来重建左（右）子树即可。

这个题的难点也就在这里，即i',j',m',n'的值的确定，笔者曾在此困惑许久，建议通过leftNodes,rightNodes和i,j,m,n来确定：（这个时候了前往不要在脑子里面想这些下标对应关系！！一定要在纸上画，确保准确性和概括性）

于是容易得出如下代码：

if(leftNodes == 0){
    root.left = null;
}else{
    root.left = rebuild(pre, i + 1, i + leftNodes, in, m, m + leftNodes - 1);
}
if(rightNodes == 0){
    root.right = null;
}else{
    root.right = rebuild(pre, i + leftNodes + 1, j, in, n - rightNodes + 1, n);
}
复制代码

笔者曾以中序序列的根节点索引来确定i',j',m',n'的对应关系写出如下错误代码：

if(leftNodes == 0){
    root.left = null;
}else{
    root.left = rebuild(pre, i + 1, index, in, m, index - 1);
}
if(rightNodes == 0){
    root.right = null;
}else{
    root.right = rebuild(pre, index + 1, j, in, index + 1, n);
}
复制代码

这种对应关系乍一看没错，但是不具有概括性（即囊括所有情况），比如对序列2,3,4、3,2,4重建时：

你看这种情况，上述错误代码还适用吗？原因就在于index是在in的m~n中选取的，与数组in是绑定的，和pre没有直接的关系，因此如果用index来表示i',j'自然是不合理的。

此题的正确完整代码如下：

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || in == null || pre.length == 0 || in.length == 0 || pre.length != in.length){
            return null;
        }
        return rebuild(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }
    
    public TreeNode rebuild(int[] pre, int i, int j, int[] in, int m, int n){
        int rootVal = pre[i], index = findIndex(rootVal, in, m, n);
        if(index < 0){
            return null;
        }
        int leftNodes = index - m, rightNodes = n - index;
        TreeNode root = new TreeNode(rootVal);
        if(leftNodes == 0){
            root.left = null;
        }else{
            root.left = rebuild(pre, i + 1, i + leftNodes, in, m, m + leftNodes - 1);
        }
        if(rightNodes == 0){
            root.right = null;
        }else{
            root.right = rebuild(pre, i + leftNodes + 1, j, in, n - rightNodes + 1, n);
        }
        return root;
    }
    
    public int findIndex(int target, int arr[], int from, int to){
        for(int i = from ; i <= to ; i++){
            if(arr[i] == target){
                return i;
            }
        }
        return -1;
    }
}
复制代码

总结：

1. 对于复杂问题，一定要划分成若干子问题，逐一求解。比如二叉树问题，我们通常将其划分成头结点、左子树、右子树。
2. 对于递归过程的参数对应关系，尽量使用和数据样本本身没有直接关系的变量来表示。比如此题应该选取leftNodes和rightNodes来计算i',j',m',n'而不应该使用头结点在中序序列的下标index（它和in是绑定的，那么可能对pre就不适用了）。

用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {

}

public int pop() {
    
}
复制代码

解析

这道题只要记住以下几点即可：

1. 一个栈（如stack1）只能用来存，另一个栈（如stack2）只能用来取
2. 当取元素时首先检查stack2是否为空，如果不空直接stack2.pop()，否则将stack1中的元素全部倒入stack2，如果倒入之后stack2仍为空则需要抛异常，否则stack2.pop()。

代码示例如下：

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        if(stack2.empty()){
            throw new IllegalStateException("no more element！");
        }
        return stack2.pop();
    }
}
复制代码

总结：只要取元素的栈不为空，取元素时直接弹出其栈顶元素即可，只有当其为空时才考虑将存元素的栈倒入进来，并且要一次性倒完。

旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

public int minNumberInRotateArray(int [] arr) {
       
}
复制代码

解析

此题需先认真审题：

1. 若干，涵盖了一个元素都不搬的情况，此时数组是一个非减排序序列，因此首元素就是数组的最小元素。
2. 非减排序，并不代表是递增的，可能会出现若干相邻元素相同的情况，极端的例子是整个数组的所有元素都相同

由此不难得出如下input check：

public int minNumberInRotateArray(int [] arr) {
    //input check
    if(arr == null || arr.length == 0){
        return 0;
    }
    //if only one element or no rotate
    if(arr.length == 1 || arr[0] < arr[arr.length - 1]){
        return arr[0];
    }
    
    //TODO
}
复制代码

上述的arr[0] < arr[arr.length - 1]不能写成arr[0] <= arr[arr.length - 1]，比如可能会有[1,2,3,3,4] -> [3,4,1,2,3] 的情况，这时你不能返回arr[0]=3。

如果走到了程序中的TODO，就可以考虑普遍情况下的推敲，数组可以被分成两部分：大于等于arr[0]的左半部分和小于等于arr[arr.length - 1]右半部分，我们不妨借助两个指针从数组的头、尾向中间靠近，这样就能利用二分的思想快速移动指针从而淘汰一些不在考虑范围之内的数。

如图，我们不能直接通过arr[mid]和arr[l]（或arr[r]）的比较（arr[mid] >= arr[l]）来决定移动l还是r到mid上，因为数组可能存在若干相同且相邻的数，因此我们还需要加上一个限制条件：arr[l + 1] >= arr[l] && arr[mid] >= arr[l]（对于r来说则是arr[r - 1] <= arr[r] && arr[mid] <= arr[r]），即当左半部分（右半部分）不止一个数时，我们才可能去移动l（r）指针。完整代码如下：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] arr) {
         //input check
        if(arr == null || arr.length == 0){
            return 0;
        }
        //if only one element or no rotate
        if(arr.length == 1 || arr[0] < arr[arr.length - 1]){
            return arr[0];
        }
         
        //has rotate, left part is big than right part
        int l = 0, r = arr.length - 1, mid;
        //l~r has more than 3 elements
        while(r > l && r - l != 1){
            //r-l >= 2 -> mid > l
            mid = l + ((r - l) >> 1);
            if(arr[l + 1] >= arr[l] && arr[mid] >= arr[l]){
                l = mid;
            }else{
                r = mid;
            }
        }
         
        return arr[r];
    }
}
复制代码

总结：审题时要充分考虑数据样本的极端情况，以写出鲁棒性较强的代码。

斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

public int Fibonacci(int n) {
      
}
复制代码

解析

递归方式

对于公式f(n) = f(n-1) + f(n-2)，明显就是一个递归调用，因此根据f(0) = 0和f(1) = 1我们不难写出如下代码：

public int Fibonacci(int n) {
    if(n == 0 || n == 1){
        return n;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
复制代码

动态规划

在上述递归过程中，你会发现有很多计算过程是重复的：

动态规划就在使用递归调用自上而下分析过程中发现有很多重复计算的子过程，于是采用自下而上的方式将每个子状态缓存下来，这样对于上层而言只有当需要的子过程结果不在缓存中时才会计算一次，因此每个子过程都只会被计算一次。

public int Fibonacci(int n) {
    if(n == 0 || n == 1){
        return n;
    }
    //n1 -> f(n-1), n2 -> f(n-2)
    int n1 = 1, n2 = 0;
    //从f(2)开始算起
    int N = 2, res = 0;
    while(N++ <= n){
        //每次计算后更新缓存，当然你也可以使用一个一维数组保存每次的计算结果，只额外空间复杂度就变为O(n)了
        res = n1 + n2;
        n2 = n1;
        n1 = res;
    }
    return res;
}
复制代码

上述代码很多人都能写出来，只是没有意识到这就是动态规划。

总结：当你自上而下分析递归时发现有很多子过程被重复计算，那么就应该考虑能否通过自下而上将每个子过程的计算结果缓存下来。

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

public int JumpFloor(int target) {
       
}
复制代码

解析

递归版本

将复杂问题分解：复杂问题就是不断地将target减1或减2（对应跳一级和跳两级台阶）直到target变为1或2（对应只剩下一层或两层台阶）时我们能够很容易地得出结果。因此对于当前的青蛙而言，它能够选择的就是跳一级或跳二级，剩下的台阶有多少种跳法交给子过程来解决：

public int JumpFloor(int target) {
    //input check
    if(target <= 0){
        return 0;
    }
    //base case
    if(target == 1){
        return 1;
    }
    if(target == 2){
        return 2;
    }
    return JumpFloor(target - 1) + JumpFloor(target - 2);
}
复制代码

你会发现这其实就是一个斐波那契数列，只不过是从f(1) = 1,f(2) = 2开始的斐波那契数列罢了。自然你也应该能够写出动态规划版本。

进阶问题

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

解析

递归版本

本质上还是分解，只不过上一个是分解成两步，而这个是分解成n步：

public int JumpFloorII(int target) {
    if(target <= 0){
        return 0;
    }
    //base case，当target=0时表示某个分解分支跳完了所有台阶，这个分支就是一种跳法
    if(target == 0){
        return 1;
    }
    
    //本过程要收集的跳法的总数
    int res = 0;
    for(int i = 1 ; i <= target ; i++){
         //本次选择，选择跳i阶台阶，剩下的台阶交给子过程，每个选择就代表一个分解分支
        res += JumpFloorII(target - i);
    }
    return res;
}
复制代码

动态规划

这个动态规划就有一点难度了，首先我们要确定缓存目标，斐波那契数列中由于f(n)只依赖于f(n-1)和f(n-2)因此我们仅用两个缓存变量实现了动态规划，但是这里f(n)依赖的是f(0),f(1),f(2),...,f(n-1)，因此我们需要通过长度量级为n的表缓存前n个状态（int arr[] = new int[target + 1]，arr[target]表示f(n)）。然后根据递归版本（通常是base case）确定哪些状态的值是可以直接确定的，比如由if(target == 0){ return 1 }可知arr[0] = 1，从f(N = 1)开始的所有状态都需要依赖之前（f(n < N)）的所有状态：

int res = 0;
for(int i = 1 ; i <= target ; i++){
    res += JumpFloorII(target - i);
}
return res
复制代码

因此我们可以据此自下而上计算出每个子状态的值：

public int JumpFloorII(int target) {
    if(target <= 0){
        return 0;
    }

    int arr[] = new int[target + 1];
    arr[0] = 1;
    for(int i = 1 ; i < arr.length ; i++){
        for(int j = 0 ; j < i ; j++){
            arr[i] += arr[j];
        }
    }

    return arr[target];
}
复制代码

但这仍不是最优解，因为观察循环体你会发现，每次f(n)的计算都要从f(0)累加到f(n-1)，我们完全可以将这个累加值缓存起来preSum，每计算出一次f(N)之后都将缓存更新为preSum += f(N)。如此得到最优解：

public int JumpFloorII(int target) {
    if(target <= 0){
        return 0;
    }

    int arr[] = new int[target + 1];
    arr[0] = 1;
    int preSum = arr[0];
    for(int i = 1 ; i < arr.length ; i++){
        arr[i] = preSum;
        preSum += arr[i];
    }

    return arr[target];
}
复制代码

矩形覆盖

题目描述

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

public int RectCover(int target) {
        
}
复制代码

解析

递归版本

有了之前的历练，我们能很快的写出递归版本：先竖着放一个或者先横着放两个，剩下的交给递归处理：

//target 大矩形的边长，也是剩余小矩形的个数
public int RectCover(int target) {
    if(target <= 0){
        return 0;
    }
    if(target == 1 || target == 2){
        return target;
    }
    return RectCover(target - 1) + RectCover(target - 2);
}
复制代码

动态规划

这仍然是个以f(1)=1,f(2)=2开头的斐波那契数列：

//target 大矩形的边长，也是剩余小矩形的个数
public int RectCover(int target) {
    if(target <= 0){
        return 0;
    }
    if(target == 1 || target == 2){
        return target;
    }
    //n_1->f(n-1), n_2->f(n-2)，从f(N=3)开始算起
    int n_1 = 2, n_2 = 1, N = 3, res = 0;
    while(N++ <= target){
        res = n_1 + n_2;
        n_2 = n_1;
        n_1 = res;
    }

    return res;
}
复制代码

二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

public int NumberOf1(int n) {
       
}
复制代码

解析

题目已经给我们降低了难度：负数用补码（取反加1）表示表明输入的参数为均为正数，我们只需统计其二进制表示中1的个数、运算时只考虑无符号移位即可。

典型的判断某个二进制位上是否为1的方法是将该二进制数右移至该二进制位为最低位然后与1相与&，由于1的二进制表示中只有最低位为1其余位均为0，因此相与后的结果与该二进制位上的数相同。据此不难写出如下代码：

public int NumberOf1(int n) {
    int count = 0;
    for(int i = 0 ; i < 32 ; i++){
        count += ((n >> i) & 1);
    }
    return count;
}
复制代码

当然了，还有一种比较秀的解法就是利用n = n & (n - 1)将n的二进制位中为1的最低位置为0（只要n不为0就说明含有二进位制为1的位，如此这样的操作能做多少次就说明有多少个二进制位为1的位）：

public int NumberOf1(int n) {
    int count = 0;
    while(n != 0){
        count++;
        n &= (n - 1);
    }
    return count;
}
复制代码

数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

public double Power(double base, int exponent) {
        
}
复制代码

解析

这是一道充满危险色彩的题，求职者可能会内心窃喜不假思索的写出如下代码：

public double Power(double base, int exponent) {
    double res = 1;
    for(int i = 1 ; i <= exponent ; i++){
        res *= base;
    }
	return res;
}
复制代码

但是你有没有想过底数base和幂exponent都是可正、可负、可为0的。如果幂为负数，那么底数就不能为0，否则应该抛出算术异常：

//是否是负数
boolean minus = false;
//如果存在分母
if(exponent < 0){
    minus = true;
    exponent = -exponent;
    if(base == 0){
        throw new ArithmeticException("/ by zero");
    }
}
复制代码

如果幂为0，那么根据任何不为0的数的0次方为1，0的0次方未定义，应该有如下判断：

//如果指数为0
if(exponent == 0){
    if(base != 0){
        return 1;
    }else{
        throw new ArithmeticException("0^0 is undefined");
    }
}
复制代码

剩下的就是计算乘方结果，但是不要忘了如果幂为负需要将结果取倒数：

//指数不为0且分母也不为0，正常计算并返回整数或分数
double res = 1;
for(int i = 1 ; i <= exponent ; i++){
    res *= base;
}

if(minus){
    return 1/res;
}else{
    return res;
}
复制代码

也许你还可以锦上添花为幂乘方的计算引入二分计算（当幂为偶数时2^n = 2^(n/2) * 2^(n/2)）：

public double binaryPower(double base, int exp){
    if(exp == 1){
        return base;
    }
    double res = 1;
    res *= (binaryPower(base, exp/2) * binaryPower(base, exp/2));
    return exp % 2 == 0 ? res : res * base;
}
复制代码

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

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public void reOrderArray(int [] arr) {
      
}
复制代码

解析

读题之后发现这个跟快排的partition思路很像，都是选取一个比较基准将数组分成两部分，当然你也可以以arr[i] % 2 == 0为基准将奇数放前半部分，将偶数放有半部分，但是虽然只需O(n)的时间复杂度但不能保证调整后奇数之间、偶数之间的相对位置：

public void reOrderArray(int [] arr) {
    if(arr == null || arr.length == 0){
        return;
    }

    int odd = -1;
    for(int i = 0 ; i < arr.length ; i++){
        if(arr[i] % 2 == 1){
            swap(arr, ++odd, i);
        }
    }
}

public void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
复制代码

涉及到排序稳定性，我们自然能够想到插入排序，从数组的第二个元素开始向后依次确定每个元素应处的位置，确定的逻辑是：将该数与前一个数比较，如果比前一个数小则与前一个数交换位置并在交换位置后继续与前一个数比较直到前一个数小于等于该数或者已达数组首部停止。

此题不过是将比较的逻辑由数值的大小改为：当前的数是否是奇数并且前一个数是偶数，是则递归向前交换位置。代码示例如下：

public void reOrderArray(int [] arr) {
    if(arr == null || arr.length == 0){
        return;
    }

    int odd = -1;
    for(int i = 1 ; i < arr.length ; i++){
        for(int j = i ; j >= 1 ; j--){
            if(arr[j] % 2 == 1 && arr[j - 1] % 2 == 0){
                swap(arr, j, j - 1);
            }
        }
    }
}
复制代码

链表中倒数第K个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

public ListNode FindKthToTail(ListNode head,int k) {
    
}
复制代码

解析

倒数，这又是一个从尾到头的遍历逻辑，而链表对从尾到头遍历是敏感的，前面我们有通过压栈/递归、反转链表的方式实现这个遍历逻辑，自然对于此题同样适用，但是那样未免太麻烦了，我们可以通过两个间距为（k-1）个结点的链表指针来达到此目的。

public ListNode FindKthToTail(ListNode head,int k) {
    //input check
    if(head == null || k <= 0){
        return null;
    }
    ListNode tmp = new ListNode(0);
    tmp.next = head;
    ListNode p1 = tmp, p2 = tmp;
    while(k > 0 && p1.next != null){
        p1 = p1.next;
        k--;
    }
    //length < k
    if(k != 0){
        return null;
    }
    while(p1 != null){
        p1 = p1.next;
        p2 = p2.next;
    }
    
    tmp = null; //help gc

    return p2;
}
复制代码

这里使用了一个技巧，就是创建一个临时结点tmp作为两个指针的初始指向，以模拟p1先走k步之后，p2才开始走，没走时停留在初始位置的逻辑，有利于帮我们梳理指针在对应位置上的意义，这样当p1走到头时（p1=null），p2就是倒数第k个结点。

这里还有一个坑就是，笔者层试图为了简化代码将上述的9 ~ 12行写成如下偷懒模式而导致排错许久：

while(k-- > 0 && p1.next != null){
        p1 = p1.next;
}
复制代码

原因是将k--写在while()中，无论判断是否通过都会执行k = k - 1，因此代码总是会在if(k != 0)处返回null，希望读者不要和笔者一样粗心。

总结：当遇到复杂的指针操作时，我们不妨试图多引入几个指针或者临时结点，以方便梳理我们的思路，加强代码的逻辑化，这些空间复杂度O(1)的操作通常也不会影响性能。

合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

public ListNode Merge(ListNode list1,ListNode list2) {
    
}
复制代码

解析

public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1 == null || list2 == null){
        return list1 == null ? list2 : list1;
    }
    ListNode newHead = list1.val < list2.val ? list1 : list2;
    ListNode p1 = (newHead == list1) ? list1.next : list1;
    ListNode p2 = (newHead == list2) ? list2.next : list2;
    ListNode p = newHead;
    while(p1 != null && p2 != null){
        if(p1.val <= p2.val){
            p.next = p1;
            p1 = p1.next;
        }else{
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }

    while(p1 != null){
        p.next = p1;
        p = p.next;
        p1 = p1.next;
    }
    while(p2 != null){
        p.next = p2;
        p = p.next;
        p2 = p2.next;
    }

    return newHead;
}
复制代码

树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1 == null || root2 == null){
        return false;
    }

    return process(root1, root2);
}
复制代码

解析

这是一道典型的分解求解的复杂问题。典型的二叉树分解：遍历头结点、遍历左子树、遍历右子树。首先按照root1和root2的值是否相等划分为两种情况：

1. 两个头结点的值相等，并且root2.left也是roo1.left的子结构（递归）、root2.right也是root1.right的子结构（递归），那么可返回true。
2. 否则，要看只有当root2为root1.left的子结构或者root2为root1.right的子结构时，才能返回true

据上述两点很容易得出如下递归逻辑：

if(root1.val == root2.val){
    if(process(root1.left, root2.left) && process(root1.right, root2.right)){
        return true;
    }
}

return process(root1.left, root2) || process(root1.right, root2);
复制代码

接下来确定递归的终止条件，如果某个子过程root2=null那么说明在自上而下的比较过程中root2的结点已被罗列比较完了，这时无论root1是否为null，该子过程都应该返回true：

if(root2 == null){
    return true;
}
复制代码

但是如果root2 != null而root1 = null，则应返回false

if(root1 == null && root2 != null){
    return false;
} 
复制代码

完整代码如下：

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null){
            return false;
        }

        return process(root1, root2);
    }

    public boolean process(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null && root2 != null){
            return false;
        }  

        if(root1.val == root2.val){
            if(process(root1.left, root2.left) && process(root1.right, root2.right)){
                return true;
            }
        }

        return process(root1.left, root2) || process(root1.right, root2);
    }
}
复制代码

二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

public void Mirror(TreeNode root) {
        
}
复制代码

解析

由图可知获取二叉树的镜像就是将原树的每个结点的左右孩子交换一下位置（这个规律一定要会找），也就是说我们只需遍历每个结点并交换left,right的引用指向就可以了，而我们有成熟的先序遍历：

public void Mirror(TreeNode root) {
    if(root == null){
        return;
    }

    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    Mirror(root.left);
    Mirror(root.right);
}
复制代码

顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

public ArrayList<Integer> printMatrix(int [][] matrix) {
        
}
复制代码

解析

只要分析清楚了打印思路（左上角和右下角即可确定一条打印轨迹）后，此题主要考查条件控制的把握。只要给我一个左上角的点(i,j)和右下角的点(m,n)，就可以将这一圈的打印分解为四步：

但是如果左上角和右下角的点在一行或一列上那就没必要分解，直接打印改行或该列即可，打印的逻辑如下：

public void printEdge(int[][] matrix, int i, int j, int m, int n, ArrayList<Integer> res){
    if(i == m && j == n){
        res.add(matrix[i][j]);
        return;
    }

    if(i == m || j == n){
        //only one while will be execute
        while(i < m){
            res.add(matrix[i++][j]);
        }
        while(j < n){
            res.add(matrix[i][j++]);
        }
        res.add(matrix[m][n]);
        return;
    }

    int p = i, q = j;
    while(q < n){
        res.add(matrix[p][q++]);
    }
    //q == n
    while(p < m){
        res.add(matrix[p++][q]);
    }
    //p == m
    while(q > j){
        res.add(matrix[p][q--]);
    }
    //q == j
    while(p > i){
        res.add(matrix[p--][q]);
    }
    //p == i
}
复制代码

接着我们将每个圈的左上角和右下角传入该函数即可：

public ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0){
        return res;
    }
    int i = 0, j = 0, m = matrix.length - 1, n = matrix[0].length - 1;
    while(i <= m && j <= n){
        printEdge(matrix, i++, j++, m--, n--, res);
    }
    return res;
}
复制代码

包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

public class Solution {

    
    public void push(int node) {
        
    }
    
    public void pop() {
        
    }
    
    public int top() {
        
    }
    
    public int min() {
        
    }
}
复制代码

解析

最直接的思路是使用一个变量保存栈中现有元素的最小值，但这只对只存不取的栈有效，当弹出的值不是最小值时还没什么影响，但当弹出最小值后我们就无法获取当前栈中的最小值。解决思路是使用一个最小值栈，栈顶总是保存当前栈中的最小值，每次数据栈存入数据时最小值栈就要相应的将存入后的最小值压入栈顶：

private Stack<Integer> dataStack = new Stack();
private Stack<Integer> minStack = new Stack();

public void push(int node) {
    dataStack.push(node);
    if(!minStack.empty() && minStack.peek() < node){
        minStack.push(minStack.peek());
    }else{
        minStack.push(node);
    }
}

public void pop() {
    if(!dataStack.empty()){
        dataStack.pop();
        minStack.pop();
    }
}

public int top() {
    if(!dataStack.empty()){
        return dataStack.peek();
    }
    throw new IllegalStateException("stack is empty");
}

public int min() {
    if(!dataStack.empty()){
        return minStack.peek();
    }
    throw new IllegalStateException("stack is empty");
}
复制代码

栈的压入、弹出序列

题目描述

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

public boolean IsPopOrder(int [] arr1,int [] arr2) {
     
}
复制代码

解析

可以使用两个指针i,j，初始时i指向压入序列的第一个，j指向弹出序列的第一个，试图将压入序列按照顺序压入栈中：

1. 如果arr1[i] != arr2[j]，那么将arr1[i]压入栈中并后移i（表示arr1[i]还没到该它弹出的时刻）
2. 如果某次后移i之后发现arr1[i] == arr2[j]，那么说明此刻的arr1[i]被压入后应该被立即弹出才会产生给定的弹出序列，于是不压入arr1[i]（表示压入并弹出了）并后移i，j也要后移（表示弹出序列的arr2[j]记录已产生，接着产生或许的弹出记录即可）。
3. 因为步骤2和3都会后移i，因此循环的终止条件是i到达arr1.length，此时若栈中还有元素，那么从栈顶到栈底形成的序列必须与arr2中j之后的序列相同才能返回true。

public boolean IsPopOrder(int [] arr1,int [] arr2) {
    //input check
    if(arr1 == null || arr2 == null || arr1.length != arr2.length || arr1.length == 0){
        return false;
    }
    Stack<Integer> stack = new Stack();
    int length = arr1.length;
    int i = 0, j = 0;
    while(i < length && j < length){
        if(arr1[i] != arr2[j]){
            stack.push(arr1[i++]);
        }else{
            i++;
            j++;
        }
    }

    while(j < length){
        if(arr2[j] != stack.peek()){
            return false;
        }else{
            stack.pop();
            j++;
        }
    }

    return stack.empty() && j == length;
}
复制代码

从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
       
}
复制代码

解析

使用一个队列来保存当前遍历结点的孩子结点，首先将根节点加入队列中，然后进行队列非空循环：

1. 从队列头取出一个结点，将该结点的值打印
2. 如果取出的结点左孩子不空，则将其左孩子放入队列尾部
3. 如果取出的结点右孩子不空，则将其右孩子放入队列尾部

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(root == null){
        return res;
    }
    LinkedList<TreeNode> queue = new LinkedList();
    queue.addLast(root);
    while(queue.size() > 0){
        TreeNode node = queue.pollFirst();
        res.add(node.val);
        if(node.left != null){
            queue.addLast(node.left);
        }
        if(node.right != null){
            queue.addLast(node.right);
        }
    }

    return res;
}
复制代码

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

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

public boolean VerifySquenceOfBST(int [] sequence) {
        
}
复制代码

解析

对于二叉树的后序序列，我们能够确定最后一个数就是根结点，还能确定的是前一半部分是左子树的后序序列，后一部分是右子树的后序序列。

遇到这种复杂问题，我们仍能采用三步走战略（根结点、左子树、右子树）：

1. 如果当前根结点的左子树是BST且其右子树也是BST，那么才可能是BST
2. 在1的条件下，如果左子树的最大值小于根结点且右子树的最小值大于根结点，那么这棵树就是BST

据此我们需要定义一个递归体，该递归体需要收集的信息如下：下层需要向我返回其最大值、最小值、以及是否是BST

class Info{
    boolean isBST;
    int max;
    int min;
    Info(boolean isBST, int max, int min){
        this.isBST = isBST;
        this.max = max;
        this.min = min;
    }
}
复制代码

递归体的定义如下：

public Info process(int[] arr, int start, int end){
    if(start < 0 || end > arr.length - 1 || start > end){
        throw new IllegalArgumentException("invalid input");
    }
    //base case : only one node
    if(start == end){
        return new Info(true, arr[end], arr[end]);
    }

    int root = arr[end];
    Info left, right;
    //not exist left child
    if(arr[start] > root){
        right = process(arr, start, end - 1);
        return new Info(root < right.min && right.isBST, 
                        Math.max(root, right.max), Math.min(root, right.min));
    }
    //not exist right child
    if(arr[end - 1] < root){
        left = process(arr, start, end - 1);
        return new Info(root > left.max && left.isBST, 
                        Math.max(root, left.max), Math.min(root, left.min));
    }

    int l = 0, r = end - 1;
    while(r > l && r - l != 1){
        int mid = l + ((r - l) >> 1);
        if(arr[mid] > root){
            r = mid;
        }else{
            l = mid;
        }
    }
    left = process(arr, start, l);
    right = process(arr, r, end - 1);
    return new Info(left.isBST && right.isBST && root > left.max && root < right.min, 
                    right.max, left.min);
}
复制代码

总结：二叉树相关的信息收集问题分步走：

1. 分析当前状态需要收集的信息
2. 根据下层传来的信息加工出当前状态的信息
3. 确定递归终止条件

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

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        
}
复制代码

解析

审题可知，我们需要有一个自上而下从根结点到每个叶子结点的遍历思路，而先序遍历刚好可以拿来用，我们只需在来到当前结点时将当前结点值加入到栈中，在离开当前结点时再将栈中保存的当前结点的值弹出即可使用栈模拟保存自上而下经过的结点，从而实现在来到每个叶子结点时只需判断栈中数值之和是否为target即可。

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList();
    if(root == null){
        return res;
    }
    Stack<Integer> stack = new Stack<Integer>();
    preOrder(root, stack, 0, target, res);
    return res;
}

public void preOrder(TreeNode root, Stack<Integer> stack, int sum, int target, ArrayList<ArrayList<Integer>> res){
    if(root == null){
        return;
    }

    stack.push(root.val);
    sum += root.val;
    //leaf node
    if(root.left == null && root.right == null && sum == target){
        ArrayList<Integer> one = new ArrayList();
        one.addAll(stack);
        res.add(one);
    }

    preOrder(root.left, stack, sum, target, res);
    preOrder(root.right, stack, sum, target, res);

    sum -= stack.pop();
}
复制代码

复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        
    }
}
复制代码

解析

此题主要的难点在于random指针的处理。

方法一：使用哈希表，额外空间O(n)

可以将链表中的结点都复制一份，用一个哈希表来保存，key是源结点，value就是副本结点，然后遍历key取出每个对应的value将副本结点的next指针和random指针设置好：

public RandomListNode Clone(RandomListNode pHead){
    if(pHead == null){
        return null;
    }
    HashMap<RandomListNode, RandomListNode> map = new HashMap();
    RandomListNode p = pHead;
    //copy
    while(p != null){
        RandomListNode cp = new RandomListNode(p.label);
        map.put(p, cp);
        p = p.next;
    }
    //link
    p = pHead;
    while(p != null){
        RandomListNode cp = map.get(p);
        cp.next = (p.next == null) ? null : map.get(p.next);
        cp.random = (p.random == null) ? null : map.get(p.random);
        p = p.next;
    }

    return map.get(pHead);
}
复制代码

方法二：追加结点，额外空间O(1)

首先将每个结点复制一份并插入到对应结点之后，然后遍历链表将副本结点的random指针设置好，最后将源结点和副本结点分离成两个链表

public RandomListNode Clone(RandomListNode pHead){
    if(pHead == null){
        return null;
    }

    RandomListNode p = pHead;
    while(p != null){
        RandomListNode cp = new RandomListNode(p.label);
        cp.next = p.next;
        p.next = cp;
        p = p.next.next;
    }

    //more than two node
    //link random pointer
    p = pHead;
    RandomListNode cp;
    while(p != null){
        cp = p.next;
        cp.random = (p.random == null) ? null : p.random.next;
        p = p.next.next;
    }

    //split source and copy
    p = pHead;
    RandomListNode newHead = p.next;
    //p != null -> p.next != null
    while(p != null){
        cp = p.next;
        p.next = p.next.next;
        p = p.next;
        cp.next = (p == null) ? null : p.next;
    }

    return newHead;
}
复制代码