剑指Offer（一）
题目汇总
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);
}
}
