本文主要是介绍剑指offer第二版（leetcode）Java题解（不断更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 数组中的重复数字
题目
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
思路
所有的数字都在0到n-1，所以可以将数字看做数组的下标。
通过把每个数字放回它的值作为索引的位置，在放置的时候判断目标位置是否已经有正确对应的值
如果没有，就交换，如果有，说明对应位置存在重复值。
代码
class Solution {public int findRepeatNumber(int[] nums) {for(int i =0;i<nums.length;i++){//如果当前数不是应该在的位置，就放过去，交换对应位置的数回来//如果在应该在的位置，这个就跳过去，看下一个。if(nums[i]!=i){int temp = nums[nums[i]];//移动时如果目标位置已经有了一个应该在的数，说明重复了if(temp == nums[i]){return nums[i];}//没有就交换一下nums[nums[i]]=nums[i];nums[i]=temp;i--;}}return 0;}
}
2 二维数组中的查找
题目
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路
代码
class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {int row = matrix.length-1;int col = 0;while(row >=0&&col<matrix[0].length){if(matrix[row][col]==target)return true;if(matrix[row][col]>target){row = row -1;}else{col = col+1;}}return false;}
}
3 替换空格
题目
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
代码
class Solution {public String replaceSpace(String s) {if(s.length()==0)return s;int count =0;//求一下空格的个数确定 array的sizefor(int i= 0;i<s.length();i++)if(s.charAt(i) == ' ')count++;int size = s.length()+count*2;char [] str = new char[size];int j=size-1;//从后往前填写，其实在这道题从前往后也是一样的，从后往前在某些情境下可以实现原地for(int i =s.length()-1;i>=0;i--){if(s.charAt(i)==' '){str[j]='0';str[j-1]='2';str[j-2]='%';j=j-3;}else{str[j]=s.charAt(i);j--;}}return new String(str);}
}
4 从尾到头打印链表
题目
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {//记录长度 创建返回结果 填入即可 当然 链表反转也可以解决public int[] reversePrint(ListNode head) {int len=0;ListNode cur=head;while(cur!=null){len++;cur=cur.next;}int []res=new int[len];for(int i=len-1;i>=0;i--){res[i]=head.val;head=head.next;}return res;}
}
5 重建二叉树
题目
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return rebuild(preorder,inorder,0,preorder.length,0,preorder.length);}public TreeNode rebuild(int [] preOrder, int []inOrder,int lp,int rp,int li,int ri){if(lp>=rp||li>=ri)return null;TreeNode node = new TreeNode(preOrder[lp]);int count = 0;for(int i = li;i<ri;i++){if(inOrder[i]==preOrder[lp])break;count++;}node.left = rebuild(preOrder,inOrder,lp+1,lp+1+count,li,li+count);node.right=rebuild(preOrder,inOrder,lp+count+1,rp,li+count+1,ri);return node;}
}
6 用两个栈实现队列
题目
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
代码
class CQueue {public Stack<Integer> inStack;public Stack<Integer> outStack;public CQueue() {inStack= new Stack();outStack=new Stack();}public void appendTail(int value) {while(outStack.size()!=0){inStack.push(outStack.pop());}inStack.push(value);}public int deleteHead() {while(inStack.size()!=0){outStack.push(inStack.pop());}if(outStack.size()!=0)return outStack.pop();elsereturn -1;}}/*** Your CQueue object will be instantiated and called as such:* CQueue obj = new CQueue();* obj.appendTail(value);* int param_2 = obj.deleteHead();*/
7 斐波那契数列
题目
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
代码
class Solution {public int fib(int n) {int first = 0;int second = 1;if(n==0)return 0;if(n==1)return 1;if(n==2)return 1;int third = 0;for(int i =2 ;i<=n;i++){third = (first+second)%1000000007;first = second;second = third;}return third;}
}
8 青蛙跳台阶
题目
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
代码
class Solution {public int numWays(int n) {if(n==0)return 1;if(n==1)return 1;int first = 1,second =1;int third = 2;for(int i=2;i<=n;i++){third = (first+second)%1000000007;first=second;second=third;}return third;}
}
9 旋转数组中的最小数字（有点东西）
题目
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
代码
class Solution {public int minArray(int[] numbers) {int left = 0,right = numbers.length-1;while(left+1<right){int index = left+(right-left)/2;if(numbers[index]>numbers[right]){left = index;}else if(numbers[index]<numbers[right])right =index;elseright--;}if(numbers[left]<numbers[right])return numbers[left];else{return numbers[right];}}
}
10 矩阵中的路径
题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
代码
class Solution {//设定两个全局的标记public boolean success= false;public boolean[][] flag;public boolean exist(char[][] board, String word) {//避免一下错误输入if(board.length<=0||board[0].length<=0)return false;//根据输入初始化标记数组flag = new boolean [board.length][board[0].length];//所有元素作为入口for(int i = 0;i<board.length;i++){for(int j=0;j<board[0].length;j++){move(board,i,j,word,0);}}return success;}public void move(char [][]board,int i,int j,String word, int index){//有一个成功就不继续了if(success == true)return ;//走完word就是成功if(index == word.length()){success = true;return ;}//越界情况处理掉if(i<0||i>=board.length||j<0||j>=board[0].length)return;//如果flag表示没走过这个点且这个点和word当前字符相同，那就往上下左右继续走if(flag[i][j]==false&&board[i][j]==word.charAt(index)){flag[i][j]=true;move(board,i+1,j,word,index+1);move(board,i-1,j,word,index+1);move(board,i,j+1,word,index+1);move(board,i,j-1,word,index+1);//走完说明上下左右没有匹配到，这个点标记恢复标记，退回上一步的节点继续走flag[i][j]=false;}}
}
11 机器人的运动范围
题目
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
代码
class Solution {//要考虑好最重要的就是走过的路能不能走的问题，实际上遍历就是不能往回走的，但是一样可以遍历到所有的路，还是深度优先遍历没有理解好int count = 0;boolean [][]flag;public int movingCount(int m, int n, int k) {//初始化一个标记数组flag = new boolean[m][n];move(m,n,k,0,0);return count;}public void move(int m,int n,int k,int x,int y){//越界不继续if(x<0||x>=m||y<0||y>=n)return ;//走过不走if(flag[x][y]==true){return;}//如果符合要求就走进来，然后上下左右。if(k>=count(x,y)){flag[x][y]=true;count++;move(m,n,k,x+1,y);move(m,n,k,x-1,y);move(m,n,k,x,y-1);move(m,n,k,x,y+1);}}//实际的业务要求独立出来public int count(int x,int y){int sum =0;while(x>0){sum+=x%10;x=x/10;}while(y>0){sum+=y%10;y=y/10;}return sum;}
}
12 剪绳子I
题目
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
代码
class Solution {public int cuttingRope(int n) {//简单数学证明一下切3 切2 的大小比较if(n==2)return 1;if(n==3)return 2;if(n==4)return n;int sum =1;while(n>=5){sum=sum*3;n=n-3;}if(n>0){sum*=n;}return sum;}
}
13 剪绳子 II
题目
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
代码
class Solution {public int cuttingRope(int n) {//简单证明一下切3 切2 的大小比较if(n==2)return 1;if(n==3)return 2;if(n==4)return n;//这里防止溢出long sum =1;while(n>=5){//这里乘三有溢出的情况，所以取余也莫得用sum=sum*3%1000000007;n=n-3;}if(n>0){sum=sum*n%1000000007;}return (int)sum;}
}
14 二进制中1的个数
题目
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
代码
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {//n是整数，但是负整数也是整数//仗着java有无符号右移，所以这个问题被掩盖了 int count =0;while(n!=0){if((n&1)==1){count++;}n=n>>>1;}return count;}
}
//如果不用无符号右移
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {//n是整数，但是负整数也是整数//仗着java有无符号右移，所以这个问题被掩盖了int count =0;for(int i=0;i<32;i++){if((n&1)==1){count++;}n=n>>1;}return count;}
}
15 数值的整数次方
题目
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
代码
class Solution {public double myPow(double x, int n) {if(n==0)return 1这篇关于剑指offer第二版（leetcode）Java题解（不断更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
