剑指Offer（一）

作者: 今天柚稚了么 | 来源:发表于2020-02-03 13:42 被阅读0次

题目汇总
03.数组中重复的数字（简单），本题考查数组
04.二维数组中的查找（简单），本题考查数组
05.替换空格，本题考查字符串
06.从尾到头打印链表（简单），本题考查链表
07.重建二叉树（中等），本题考查树
08.二叉树的下一个结点（简单），本题考查树
09.用两个栈实现队列（简单），本题考查栈和队列
10.斐波那契数列（简单）

03.数组中重复的数字（简单），本题考查数组

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路一：排序

将数组中的元素进行排序，判断相邻位置的元素是否相同。时间复杂度O(nlogn)

import java.util.Arrays;
public class Solution {
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:   true if the input is valid, and there are some duplications in the array number
    //  otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length==0||numbers==null)
            return false;
        Arrays.sort(numbers);
        for(int i=0;i<length-1;i++){
            if(numbers[i]==numbers[i+1]){
                duplication[0]=numbers[i];
                return true;
            }
        }
    return false;
    }
}

思路二：哈希表

利用HashSet存储对象，从头到尾扫描数组中的每个数，如果哈希表里还没有这个数字，就把它加入哈希表；如果哈希表中已经存在该数字，就找到一个重复的数字。时间复杂度O(n)

import java.util.HashSet;
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<length;i++){
            if(set.contains(numbers[i])){
                duplication[0]=numbers[i];
                return true;
            }else{
                set.add(numbers[i]);
             }
        }
    return false;
    }
}

补充内容：

区别.PNG

思路三：利用特性

数组中的数字都在0~n-1的范围内。如果这个数组没有重复的数字，那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字，有些位置可能存在多个数字，有些位置可能没有数字。从头到尾扫描这个数组中的每个数字，当扫描到下标为i的数字时，首先比较这个数字m是不是等于i。如果是，则接着扫描下一个数字，如果不是，再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复这个比较交换的过程，直到发现重复的数字。时间复杂度O(n)

public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers==null||length==0)
            return false;
        for(int i=0;i<length;i++){
            if(numbers[i]<0||numbers[i]>length-1)
                return false;
        }
        for(int i=0;i<length;i++){
            while(numbers[i]!=i){
                if(numbers[i]==numbers[numbers[i]]){
                    duplication[0]=numbers[i];
                    return true;
                }
                else{
                    int temp=numbers[i];
                    numbers[i]=numbers[temp];
                    numbers[temp]=temp;
                }
            }
        }
    return false;
    }

04.二维数组中的查找（简单），本题考查数组

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

思路一：暴力法遍历数组。时间复杂度：O(n^2)

public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[i].length;j++){
                if(array[i][j]==target)
                    return true;
            }
        }
    return false;
    }
}

思路二：从右上角开始找。时间复杂度O(行高 + 列宽)

首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，逐步缩小范围。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;//行数
        if(rows==0){
            return false;
        }
        int columns = array[0].length;//列数
        if(columns==0){
            return false;
        }
        int row = 0;
        int col = columns - 1;
        while(row<rows&&col>=0){
            if(array[row][col]>target){
                col--;
            }
            else if(array[row][col]<target){
                row++;
            }
            else{
                return true;
            }
        }
    return false;
    }
}

思路三：从左下角开始找，原理同思路二，时间复杂度O(行高 + 列宽)

注意：不能选择左上角和右下角数字，因为这个时候无法缩小查找的范围。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;//行数
        if(rows==0){
            return false;
        }
        int columns = array[0].length;//列数
        if(columns==0){
            return false;
        }
        int row = rows - 1;
        int col = 0;
        while(row>=0 && col<columns){
            if(array[row][col] < target){
                col++;
            }else if(array[row][col] > target){
                row--;
            }else{
                return true;
            }
        }
    return false;
    }
}

05.替换空格，本题考查字符串

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

思路一：调用自带函数

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replace(" ", "%20");
    }
}

思路二：创建新的字符串

public class Solution {
   public String replaceSpace(StringBuffer str) {
       if(str==null)
           return null;
       StringBuffer res = new StringBuffer();
       for(int i=0;i<str.length();i++){
           if(str.charAt(i)==' ')
               res.append("%20");
           else
               res.append(str.charAt(i));
       }
    return res.toString();
   }
}

注意：如果试图改变String的内容，则改变后的值只能通过返回值得到。用String进行连续多次修改，每一次修改都会产生一个临时对象，这样开销太大会影响效率，为此使用新的与字符串相关的类型StringBuilder，它能容纳修改后的结果。因此，如果要连续多次修改字符串内容，用StringBuilder是更好的选择。
当对字符串进行修改的时候，需要使用 StringBuffer 和 StringBuilder 类。
和 String 类不同的是，StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。
StringBuilder 类在 Java 5 中被提出，它和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的（不能同步访问）。
由于 StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使用 StringBuilder 类。然而在应用程序要求线程安全的情况下，则必须使用 StringBuffer 类。

思路三：在当前字符串上进行替换（不会，没想过）

先遍历一遍字符串，统计出字符串中空格的总数，由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后的字符串的长度等于原来的长度加2乘以空格数目。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int spacenum = 0;
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == ' '){
                spacenum++;
            }
        }
        int oldLength = str.length();//原始字符串的长度
        int oldIndex = oldLength - 1;//原始字符串末尾
        int newLength = oldLength + spacenum*2;//替换之后的字符串的总长度
        str.setLength(newLength);
        int newIndex = newLength - 1;//替换之后的字符串的末尾
        for(; oldIndex >= 0 && oldLength < newLength; oldIndex--){
            if(str.charAt(oldIndex) == ' '){
                str.setCharAt(newIndex--, '0');
                str.setCharAt(newIndex--, '2');
                str.setCharAt(newIndex--, '%');
            }else{
                str.setCharAt(newIndex--, str.charAt(oldIndex));
            }
        }
        return str.toString();
    }
}

06.从尾到头打印链表（简单），本题考查链表

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

思路一：使用栈

从尾到头打印链表这是典型的后进先出的问题，可以用栈实现这种顺序。每经过一个节点的时候，把该节点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时输出的节点的顺序已经反转过来了。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while(listNode!=null){
            stack.add(listNode.val);
            listNode = listNode.next;//将当前对象的下一个节点对象赋给listNode对象
        }
        ArrayList<Integer> ret = new ArrayList<>();
        while(!stack.isEmpty())
            ret.add(stack.pop());//出栈
        return ret;
    }
}

思路二：递归

递归在本质上是一个栈结构，实现反向输出链表，每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点本身。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
    return list;
    }
}

但是当链表很长的时候，就会导致函数调用的层级很深，从而有可能导致调用栈溢出，用栈基于循环实现的代码的鲁棒性更好一些。

07.重建二叉树（中等），本题考查树

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

思路：递归

根据中序遍历和前序遍历可以确定二叉树，具体过程为：
根据前序序列第一个结点确定根结点
根据根结点在中序序列中的位置分割出左右两个子序列
对左子树和右子树分别递归使用同样的方法继续分解

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0||in.length==0)
            return null;
        TreeNode root = new TreeNode(pre[0]);
        for(int i=0;i<pre.length;i++){
            if(in[i]==pre[0]){
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
            
        }
    return root;
    }
}

copyOfRange(oringinal,int from, int to)方法是从original数组的下标from开始复制，到下标to结束，左闭右开。

08.二叉树的下一个结点（简单），本题考查树

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

思路：

1.如果一个结点有右子树，那么它的下一个结点就是它的右子树中的最左子结点。
2.如果一个结点没有右子树并且该结点是它父结点的左子结点，那么它的下一个结点就是它的父结点。
3.如果一个结点没有右子树并且该结点是它父结点的右子结点，那么需要沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是要找的下一个结点。

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode.right!=null){//有右子树
            TreeLinkNode prightNode = pNode.right;
            while(prightNode.left!=null){
                prightNode = prightNode.left;
            }
            return prightNode;
        }
        if(pNode.next!=null&&pNode.next.left==pNode){//无右子树，且结点是该结点父结点的左子树
            return pNode.next;
        }
        if(pNode.next!=null){//无右子树，且结点是该结点父结点的右子树，这步一直写错，看的某位兄台的题解
            TreeLinkNode pNextNode = pNode.next;
            while(pNextNode.next!=null&&pNextNode.next.right==pNextNode){
                pNextNode = pNextNode.next;
            }
            return pNextNode.next;
        }//后两个if分支可以合并
        return null;
    }
}

09.用两个栈实现队列（简单），本题考查栈和队列

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

思路：

一个队列包含了两个栈stack1和stack2，操作两个先进后出的栈实现一个先进先出的队列
（1）插入时，直接插入 stack1
（2）删除时，当 stack2 不为空，在stack2的栈顶元素是最先进入队列的元素，可以弹出，如果 stack2 为空，将 stack1 中的元素逐个弹出并压入 stack2，由于先进入队列的元素被压到stack1的底端，经过弹出和压入操作之后就处于stack2的顶端，又可以直接弹出。
通过画图让抽象的问题形象化

用两个栈模拟队列

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.size() <= 0) {
            while (stack1.size() != 0) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

举一反三：同理用两个队列实现栈

用两个队列模拟栈

过程如上图：先往栈内压入一个元素a。由于两个队列都是空的，可以选择把a插入两个队列中的任意一个，比如把a插入queue1。接下来继续往栈内压入两个元素b和c，都插入到queue1。此时queue1包含3个元素a,b,c，a位于队列的头部，c位于队列的尾部。
从栈中弹出一个元素。根据栈的后入先出原则，最后被压入栈的c应该最先被弹出。由于c位于queue1的尾部，而每次只能从队列的头部删除元素，因此可以先从queue1中依次删除元素a，b并插入queue2，再从queue1中删除元素c。这就相当于从栈中弹出元素c，同样的方法可以从栈内弹出元素b。

10.斐波那契数列（简单），本题考查递归和循环

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

斐波那契数列定义.png

思路一：递归

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1)
            return n;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

运行时间：1116ms 占用内存：9112k
可以看出上述的递归解法有严重的效率问题，时间复杂度为O(2^n)

思路二：优化递归

上述的递归解法之所以慢是因为重复的计算太多，优化递归要想办法避免重复计算。可以把已经得到的数列中间项保存起来，在下次需要计算的时候先查找一下，如果前面已经计算过就不用再重复计算了，最简单的办法就是从下往上计算。

public class Solution {
    public int Fibonacci(int n) {
        int result[] = new int[40];
        result[0] = 0;
        result[1] = 1;
        for(int i=2;i<=n;i++){
            result[i] = result[i-1] + result[i-2];
        }
        return result[n];
    }
}

运行时间：15ms 占用内存：9168k
把递归的算法用循环实现，提高了时间效率，时间复杂度为O(n)

斐波那契数列的应用—跳台阶与矩形覆盖

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

思路：

跳n级台阶相当于n-1和n-2级台阶的和，f(n)=f(n-1)+f(n-2)

public class Solution {
    public int JumpFloor(int target) {
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        /*if(target==3)
            return 3;*/
        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

斐波那契数列的应用—跳台阶

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

思路：

依然是斐波那契数列的应用问题，可以用数学归纳法证明f(n)=2^(n-1)

public class Solution {
    public int JumpFloorII(int target) {
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        if(target==3)
            return 4;
        return 2*JumpFloorII(target-1);
    }
}

斐波那契数列的应用—矩形覆盖

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

思路：

依然是斐波那契数列的应用问题，可以用数学归纳法证明f(n)=f(n-1)+f(n-2)

public class Solution {
    public int RectCover(int target) {
        if(target<=2)
            return target;
         return RectCover(target-1)+RectCover(target-2);
    }
}