剑指offer｜1-10题解题思路及代码(Java版)
剑指offer1到10题总览：
- 二维数组的查找
- 替换空格
- 从尾到头打印链表
- 重建二叉树
- 用两个栈实现队列
- 旋转数组的最小数字
- 斐波那契数列
- 跳台阶
- 变态跳台阶
- 矩形覆盖
1、二维数组的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
数组从左到右递增，从上到下递增，则如果从左下角开始，往上走则更小，往右走则更大。
注意事项
- 检测输入数据，如果行列为空，返回false。
- 下标边界是array.length-1，有减一。
- 时刻判断是否超出边界。
public class Solution {
public boolean Find(int target, int [][] array) {
if(array.length == 0){return false;}
if(array[0].length == 0){return false;}
int rows = array.length-1;//i的下标边界
int columns = array[0].length-1;//j的下标边界
int i = rows;
int j = 0;
boolean find_flag = false;//一个返回值
while(i>=0 && j<=columns){
if(target > array[i][j]){//target比当前值大，往右走
if(j>=columns){break;}
else{j++;}
}else if(target < array[i][j]){//target比当前值小，往上走
if(i<=0){break;}
else{i--;}
}else{return true;}//找到了target，直接返回true
}
return find_flag;
}
}
2、替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路
首先遍历一遍获得空格的个数，得到替换后的stringBuffer的长度。然后从后向前填写新的字符，防止移动的字符串过多。
注意事项
- stringBuffer获取长度为str.length()，这个是有括号的。
- 将空格换成%20的时候，要倒着填入02%。
- 当oldIndex和newIndex相等时，就可以不用修改字符了，因为前面再没有空格。
- stringBuffer转String的代码为str.toString();。
public class Solution {
public static String replaceSpace(StringBuffer str)
{
int spaceCount = 0;//遍历统计空格的数量
for(int i=0; i<str.length(); i++){
if(str.charAt(i) == ' '){
spaceCount++;
}
}
int oldIndex = str.length()-1;
str.setLength(str.length() + spaceCount*2);//计算新的str的长度并设置新的stringBuffer长度
int newIndex = str.length()-1;
for(; oldIndex>=0 && newIndex>oldIndex; oldIndex--){//当newIndex等于oldIndex的时候，就是前面再没有空格了
if(str.charAt(oldIndex) != ' '){//之前的stringBuffer相应位不为空格时，照搬之前的字符
str.setCharAt(newIndex--, str.charAt(oldIndex));
}else{//之前的stringBuffer相应位为空格时，则填入%20，这个时候要倒着填入02%
str.setCharAt(newIndex--, '0');
str.setCharAt(newIndex--, '2');
str.setCharAt(newIndex--, '%');
}
}
return str.toString();
}
}
3、从尾到头打印链表
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
解题思路
两种思路：
- 用栈
- 用递归
注意事项
- 检测输入：当链表为空时返回空的ArrayList。
栈版本：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
if(listNode == null){return list;}//输入链表为空时，返回空ArrayList
Stack<Integer> stack = new Stack<>();//新建栈
ListNode p = listNode;
while(p.next!=null){//将链表中的数push到栈中
stack.push(p.val);
p = p.next;
}
list.add(p.val);//链表的数还有最后一个没有push到栈中，直接add到ArrayList中
while(!stack.empty()){//将stack中的数全部pop出来到ArrayList中
list.add(stack.pop());
}
return list;
}
}
递归版本：
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList<>();//外部定义一个ArrayList
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null){//检测输入数据，如果输入空链表则返回空ArrayList
return list;
}
if(listNode.next!=null){//如果当前节点还有next，则递归
printListFromTailToHead(listNode.next);
list.add(listNode.val);//当后面的数据递归完了，在加入当前节点的val到list中
}else{//最后一个节点没有next，也要将其加入到list中，并且，这个数是第一个入list的数。
list.add(listNode.val);
}
return list;
}
}
4、重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路
递归方法，pre数组中的第一个数即当前要建的树的根节点，在in数组中找到这个数，将in数组分为左根右三部分。in左边的数即为当前树的左子树中的所有节点，in右边的数即为当前树的右子树中的所有节点。根据左右子树结点的树木，将pre数组也分为根左右三部分。分别递归左边的pre和in、右边的pre和in。
实现的时候，可以拷贝数组，也可以重载一个方法，参数中指定左右部分的索引。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0 || in.length == 0){return null;}//如果pre或in数组长度为0，则根结点为空。默认pre和in长度相等
TreeNode node = new TreeNode(pre[0]);//当前树的根结点即为pre数组的第一个数
int root_index = 0;//遍历in数组找到根结点在in数组中的位置，赋值给root_index
for(int i=0; i<in.length; i++){
if(in[i] == pre[0]){
root_index = i;
break;//找到即可退出循环
}
}
//用拷贝的方法得到左右子树的所有结点
int[] left_pre = new int[root_index];
int[] left_in = new int[root_index];
int[] right_pre = new int[pre.length-root_index-1];
int[] right_in = new int[in.length-root_index-1];
for(int i=0; i<pre.length; i++){//对四个数组赋值
if(i<root_index){
left_pre[i] = pre[i+1];//给左子树的pre赋值
left_in[i] = in[i];//给左子树的in赋值
}else if(i == root_index){
continue;
}else{
right_pre[i-root_index-1] = pre[i];
right_in[i-root_index-1] = in[i];
}
}
node.left = reConstructBinaryTree(left_pre, left_in);//递归得到当前树的左子树
node.right = reConstructBinaryTree(right_pre, right_in);//递归得到当前树的右子树
return node;
}
}
5、用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
以stack1为主，push则直接push到stack1中。pop则将stack1种所有数pop，并push到stack2，将stack1中的数反向存储在stack2中，然后pop出stack2中的栈顶元素。最后将stack2中的元素再pop出，push到stack1中还原。
注意事项
- pop的时候，将stack1中的数倒入stack2中后，取出了栈顶元素，要将stack2中的数再倒入stack1中还原。
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);//push则直接push到stack1中
}
public int pop() {
while(!stack1.empty()){//将stack1中的数倒入stack2中
stack2.push(stack1.pop());
}
int val = stack2.pop();//取出stack2中的栈顶元素
while(!stack2.empty()){//将stack2中的数再倒入stack1中还原
stack1.push(stack2.pop());
}
return val;
}
}
6、旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路
二分法缩小查找范围，旋转数组由两个递增段组成，如果array[mid]大于array[start]，则表明[start, mid]处于前半递增段，我们应取后半部分；如果array[mid]小于array[start]，则表明[start, end]中经历了骤降，我们应取前半部分。
最后我们希望得到array[start]为第一个递增段的最后一个数，array[end]为第二个递增段的第一个数。array[end]即为要返回的值。
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){return 0;}//按题意，数组长度为0返回0
if(array.length == 1){return array[0];}//如果数组长度为1，则最小值为array[0]
int start = 0;
int end = array.length-1;
for(; end - start > 1;){//当[start, end]之间至少有三个数时
int mid = (end + start)/2;//计算mid
if(array[mid] >= array[start]){//如果array[mid]大于array[start]，则[start, mid]处于递增段。我们需要取后半段，改掉start
start = mid;//这里我认为直接start=mid比较好
}else{//如果array[mid]小于array[start]，则我们需要取前半段，改掉end
end = mid;
}
}
return array[end];//当[start, end]之间只有两个数时，则array[start]为前半递增段的最后一个数，array[end]为后半递增段的第一个数。array[end]即为返回值。
}
}
7、斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
解题思路
递推公式
- 递归
- 动态规划。因为递归产生了大量重复计算，所以动态规划将前面已经计算的数存起来。
递归版本：
public class Solution {
public int Fibonacci(int n) {
if(n==0){return 0;}
if(n==1){return 1;}
return Fibonacci(n-1)+Fibonacci(n-2);//F(n-1)计算包括了F(n-2)的计算，造成大量重复
}
}
动态规划版本：
public class Solution {
public int Fibonacci(int n) {
if(n==0){return 0;}
if(n==1){return 1;}
int[] arr = new int[n+1];
arr[0] = 0;
arr[1] = 1;
for(int i=2; i<=n; i++){//将计算的数存入arr数组
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
}
}
8、跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路
最终是一个斐波那契数列。用动态规划的方法：
一级台阶：。跳一级即可。
二级台阶：。1. 跳一级再跳一级；2. 跳两级。
三级台阶：。1. 用F(2)种方法跳到第二级，再跳一级；2. 用F(1)种方法跳到第一级，再跳两级(这里不能跳一级再跳一级，因为F(1)之后跳一级之后可以到达第二级，但是这种方法已经包含在F(2)种了)。
...
n级台阶：。1. 用F(n-1)种方法跳到n-1级，再跳一级；2. 用F(n-2)种方法跳到n-2级，再跳两级。
public class Solution {
public int JumpFloor(int target) {
if(target == 0){return 0;}
if(target == 1){return 1;}
if(target == 2){return 2;}
int[] arr = new int[target+1];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
for(int i=3; i<=target; i++){
arr[i] = arr[i-1] + arr[i-2];
}
return arr[target];
}
}
9、变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路
类似前一题：
一级台阶：。跳一级即可。
二级台阶：。1. 跳一级再跳一级；2. 跳两级。
三级台阶；。1. 用F(2)种方法跳到第二级，再跳一级；2. 用F(1)种方法跳到第一级，再跳两级；3. 从第0级跳到第n级。
四级台阶：
...
n级台阶：综合起来，
public class Solution {
public int JumpFloorII(int target) {
if(target == 0){return 0;}
return (int)Math.pow(2, target-1);
}
}
10、矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路
与第8题思路类似，最终也是一个斐波那契数列。
矩形为2*1：。
矩形为2*2：。1. 用F(1)种方法填满2*1，再放一个；2. 用两个并排的填满2*2。
矩形为2*3：。1. 用F(2)种方法填满2*2，再放一个；2. 用F(1)种方法填满2*1，再并排放两个填满2*2。
矩形为2*4：。1. 用F(3)种方法填满2*3，再放一个；2. 用F(2)种方法填满2*2，再并排放两个填满2*2。
...
矩形为2*n：。
public class Solution {
public int RectCover(int target) {
if(target == 0){return 0;}
if(target == 1){return 1;}
if(target == 2){return 2;}
int[] arr = new int[target+1];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
for(int i=3; i<=target; i++){
arr[i] = arr[i-1] + arr[i-2];
}
return arr[target];
}
}
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
