剑指offer专题题解
1.二维数组中的查找（简单题）
思路：初始在数组的左下角进行查找，若a[i][j]>target，则说明可能在上面的行中，i--；若a[i][j]<target，则说明可能在右边的列中，j++；若a[i][j]==target，则说明找到。
public class Solution {
public boolean Find(int target, int [][] array) {
int i=array.length-1,j=0;//刚开始在左下角
while(i>=0&&j>=0&&j<array[0].length&&i<array.length){
if(array[i][j]==target) return true;
else if(array[i][j]>target) i--;//大于目标数，往上找
else j++;//小于目标数，往右找
}
return false;
}
} 2.替换空格（简单题）
思路：使用StringBuffer，String的一些方法，例如：toString()，append(),charAt()
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer s1 = new StringBuffer();
String s2 = str.toString();
char c = ' ';
for(int i = 0;i < s2.length();i++){
if(c == s2.charAt(i)) s1.append("%20");
else s1.append(s2.charAt(i));
}
return s1.toString();
}
} 3.从尾到头打印链表（多种解法）
（1） 递归方式
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
//递归方式
ArrayList<Integer> a = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null){
printListFromTailToHead(listNode.next);
a.add(listNode.val);
}
return a;
}
} (2)遍历（非递归）方式
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> a = new ArrayList<Integer>();
while(listNode != null){
a.add(0,listNode.val);
listNode = listNode.next;
}
return a;
}
} 4.重建二叉树
首先我们先了解一下二叉树的先序和中序和后序遍历序列
先序遍历：根节点，左子树，右子树
中序遍历：左子树，根节点，右子树
后序遍历：左子树，右子树，根节点
然后我们来模拟一下如何通过先序和中序遍历序列重建二叉树
输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
（1）首先我们通过先序遍历序列，可以知道根节点为1，通过中序遍历序列我们可以知道根节点1的左子数为{4，7，2}，右子树为{5，3，8，6}
（2）对于左子数{4，7，2}，其先序遍历序列为{2，4，7}，中序遍历序列为{4，7，2} ，我们可以知道该左子数的根节点为2，其左子数为{4，7}，右子树为空
（3）同理我们可以知道右子树的根节点以及其左右子树
（4）按照这样的方法我们可以重建二叉树
/**
* 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]);
//找出i使其in[i]==pre[0]
for(int i = 0;i < pre.length;i++){
if(in[i] == pre[0]){
//copyOfRange是左闭右开
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;
}
} 5.跳台阶
public class Solution {
//动态规划 dp[n] = dp[n-1]+dp[n-2]
public int JumpFloor(int target) {
if(target == 1) return 1;
if(target == 2) return 2;
return JumpFloor(target-1) + JumpFloor(target-2);
}
} 6.用两个栈实现队列
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
//把B中的所有数转入A中，然后把node存入A中
while(!stack2.empty()){
stack1.push(stack2.peek());
stack2.pop();
}
stack1.push(node);
}
public int pop() {
//把A中的所有数转入B中，然后弹出栈B的顶元素
while(!stack1.empty()){
stack2.push(stack1.peek());
stack1.pop();
}
return stack2.pop();
}
} 7.旋转数组的最小数字
(1)遍历法
时间复杂度：o(n) ; 空间复杂度：O(1)
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0)
return 0;
//当a[i]>a[i+1]时，输出a[i+1],若无这样的数，输出a[0]
int mint = array[0];
for(int i = 0;i < array.length - 1;i++){
if(array[i] > array[i+1]){ //注意i的取值范围
mint = array[i+1];
break;
}
}
return mint ;
}
} (2)二分查找变种
时间复杂度：o(log(n)) ; 空间复杂度：O(1)
思路：采用二分去缩小范围，模拟：3，4，5，1，2
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0) return 0;
int low = 0,high = array.length-1,mid = 0;
while(low<=high){
if(array[low]<array[high]) return array[low];
mid = (low + high)>>1;
if(array[low]>array[mid]) high = mid; //51234
else if(array[high]<array[mid]) low = mid + 1; //34512
else low++;//解决：面对11101这种情况
}
return array[mid];
}
} 8.变态跳台阶
public class Solution {
//解题：F[0]=1; F[n] = F[n-1]+F[n-2]+...+F[0];
public int JumpFloorII(int target) {
if(target == 1)return 1;
int t = 1;
for(int i = 1;i<target;i++){
t+=t;
}
return t;
}
} 9.矩形覆盖
public class Solution {
//题解：dp[n] = dp[n-1] + dp[n-2];
public int RectCover(int target) {
if(target <= 3) return target;
return RectCover(target-1) + RectCover(target-2);
}
} 10.二进制中1的个数
public class Solution {
public int NumberOf1(int n) {
int t=0;
char[]ch=Integer.toBinaryString(n).toCharArray();
for(int i=0;i<ch.length;i++){
if(ch[i]=='1'){
t++;
}
}
return t;
}
} 11.求1+2+3+...+n
思路一:sum=(n^2+n)/2public class Solution {
public int Sum_Solution(int n) {
//n*(n+1)/2;
int sum = (int)(Math.pow(n,2) + n);
return sum>>1;
}
} 思路二： 短路求值原理
&&和||运算符具有短路求值原理
对于&&来说，如果左边表达式是错误的，那么该语句直接判断为错误，不进行右边表达式运算
对于||来说，如果左边表达式是正确的，那么该语句直接判断为正确，不进行右边表达式运算
public class Solution {
public int Sum_Solution(int n) {
int ans = n;
boolean a = (n>0) && ((ans = ans + Sum_Solution(n - 1))>0);
return ans;
}
} 12.数值的整数次方
思路一：简单快速幂
public class Solution {
public double Power(double base, int exponent) {
boolean flag = false;
if(exponent < 0){
exponent = -exponent;
flag = true;
}
double ans = 1.0;
while(exponent != 0){
if(exponent%2==1){
ans = ans * base;
}
base *= base;
exponent >>= 1;
}
return flag ? 1/ans : ans;
}
} 13.调整数组顺序使奇数位于偶数前面
思路一：第一遍遍历数组a存入奇数，第二遍遍历数组a存入偶数，然后数组array等于数组apublic class Solution {
public void reOrderArray(int [] array) {
//思路：第一遍遍历数组a存奇数，第二遍遍历数组a存偶数
int[] a = new int[array.length];
int t=0;
for(int i = 0;i<array.length;i++){
if(array[i]%2==1){
a[t++]=array[i];
}
}
for(int i = 0;i<array.length;i++){
if(array[i]%2==0){
a[t++]=array[i];
}
}
for(int i = 0;i<array.length;i++){
array[i] = a[i];
}
}
} 思路二: 从末尾遍历，若元素为偶数，则在该元素的左边找到最接近的奇数，使得 奇数 与 偶数元素块 互换位置
public class Solution {
public void reOrderArray(int [] array) {
//1 3 2 4 7 5 6 4
if(array.length == 0) return ;
for(int i = 0;i < array.length-1;i++){
if(array[i] %2 == 1) continue;
for(int j = i + 1;j < array.length;j++){//这步的目的是把a[i]这个偶数变为奇数
if(array[j] %2 == 1){//找到奇数，奇数a[j]与偶数块(a[i]--a[j-1])互换
int temp1 = array[j];
for(int h = j;h > i;h--){
array[h] = array[h-1];
}
array[i] = temp1;
break;
}
}
}
}
} 思路三：类似冒泡排序思想 public class Solution {
public void reOrderArray(int [] array) {
//思路：类似冒泡排序
for(int i = 0 ; i < array.length -1 ; i++){
for(int j = array.length - 1;j > 0;j--){
if((array[j]%2==1)&&(array[j-1]%2==0)){
int t = array[j];array[j]=array[j-1];array[j-1]=t;
}
}
}
}
} 14.链表中倒数第k个结点
审题：使返回倒数第k个结点 思路一：得到该链表的总个数num，然后输出第num-k+1个结点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode t = head;
int num = 0;//该链表的总结点
while(t!=null){
t=t.next;
num++;
}
if(k>num){
return null;
}
else{
k = num - k + 1;//倒数第k个结点在正序num - k + 1个结点中
while((--k)!=0){
head=head.next;
}
return head;
}
}
} 思路二：快慢指针利用快慢指针，快指针先走k-1步，然后快慢指针一起走，直到快指针无法再走（已到达链表的尽头），此时慢指针所之指向的链表的下一个即我们要求的倒数第k个链表
再稍微分析一下：假设链表总个数为num，快慢指针最初都为head结点
快指针已走k-1步，离走到尽头还差num-k步
而对于慢指针走num-k步正好到达倒数第k个链表 注意边界!!!!!!
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//快慢指针
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode fast = head,low = head;
int t = 0;
while(low!=null){
low = low.next;
t++;
if(t>k){
fast = fast.next;
}
}
if(t<k){ //注意边界：k不能大于链表总结点数
return null;
}
else
return fast;
}
} 15.树的子结构
明确子树与子结构的概念！
对于非空数而言，子树存在3个（树本身，整个左子树，整个右子树），
而子结构不小于3个（树本身，整个左子树，整个右子树，子树继续划分...）
代码：
判断B是不是A的子树：
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return IschildTree(root1,root2)||IschildTree(root1.left,root2)||IschildTree(root1.right,root2);
}
//判断子树，其实是判断root1与root2是否完全相等
public boolean IschildTree(TreeNode root1,TreeNode root2){
if(root2==null){//如果root2先为空，则说明它为子树
return true;
}
if(root1==null){//如果root1先为空，则说明root2不为子树
return false;
}
if(root1.val == root2.val){
return IschildTree(root1.left,root2.left)&&IschildTree(root1.right,root2.right);
}
return false;//如果发现root1.val!=root2.val，则说明root2一定不是root1的子树
}
} 判断B是不是A的子结构：/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return IschildTree(root1,root2)||IschildTree(root1.left,root2)||IschildTree(root1.right,root2);
}
//判断子结构
public boolean IschildTree(TreeNode root1,TreeNode root2){
if(root2==null){//如果root2先为空，则说明它为子结构
return true;
}
if(root1==null){//如果root1先为空，则说明root2不为子结构
return false;
}
if(root1.val == root2.val){
return IschildTree(root1.left,root2.left)&&IschildTree(root1.right,root2.right);
}
//如果发现root1.val!=root2.val，则继续向下判断
return IschildTree(root1.left,root2)||IschildTree(root1.right,root2);
}
} 16.二叉树的镜像
二叉树的镜像定义：
源二叉树
8
/ \
l r
/ \ / \
ll lr rl rr
镜像二叉树
8
/ \
r l
/ \ / \
rr rl lr ll
8
/ \
l r
/ \ / \
ll lr rl rr
镜像二叉树
8
/ \
r l
/ \ / \
rr rl lr ll
递归解法：
public class Solution {
public void Mirror(TreeNode root) {
//交换二叉树的左右子节点
if(root == null) return ;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
} 非递归解法： 栈
import java.util.Stack;
//非递归写法
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) return;
//建立一个TreeNode的栈容器
Stack<TreeNode> stackNode = new Stack<TreeNode>();
stackNode.push(root);
while(!stackNode.empty()){
//取出栈顶
TreeNode tree=stackNode.peek();
stackNode.pop();
//交换tree的左右节点
if(tree.left!=null || tree.right!=null){
TreeNode ptemp=tree.left;
tree.left=tree.right;
tree.right=ptemp;
}
//对左子树入栈操作
if(tree.left!=null)
stackNode.push(tree.left);
//对右子树入栈操作
if(tree.right!=null)
stackNode.push(tree.right);
}
}
} 队列 import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) return;
Queue<TreeNode> nodes = new LinkedList<TreeNode>();
TreeNode temp;
nodes.offer(root);
while(!nodes.isEmpty()){
int len = nodes.size();
while((len--)!=0){
root = nodes.poll();
temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null) nodes.offer(root.left);
if(root.right != null) nodes.offer(root.right);
}
}
}
} 17.顺时针打印矩阵
思路一：递归
递归“圈数”，递归结束条件：假设递归到第cnt+1圈，当(cnt * 2 + 1) > height || ((cnt * 2 + 1) > weight) || vis[cnt][cnt] == 1)时递归结束。
对每层遍历，遍历的起始位置为：(i,i) ；其中每层的遍历依据方向：右下左上。
另外防止打印重复，使用vis数组进行标记。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> a = new ArrayList<Integer>();
int height = matrix.length;
int weight = matrix[0].length;
int [][] vis = new int [height][weight];
AddNumber(0,a,matrix,vis);//cnt表示第cnt+1外层
return a;
}
public static void AddNumber(int cnt,ArrayList<Integer> a,int [][] matrix,int [][] vis){
int height = matrix.length;
int weight = matrix[0].length;
if ((cnt * 2 + 1) > height || ((cnt * 2 + 1) > weight) || vis[cnt][cnt] == 1)
return;
for (int i = cnt; i < weight - cnt; i++) {
if(vis[cnt][i]==0){
a.add(matrix[cnt][i]);
vis[cnt][i] = 1;
}
}
for (int i = cnt + 1; i < height - cnt; i++) {
if(vis[i][weight - cnt - 1]==0){
a.add(matrix[i][weight - cnt - 1]);
vis[i][weight - cnt - 1] = 1;
}
}
for (int i = weight - cnt - 2; i >= cnt; i--) {
if(vis[height - 1 - cnt][i]==0){
a.add(matrix[height - 1 - cnt][i]);
vis[height - 1 - cnt][i] = 1;
}
}
for (int i = height - cnt - 2; i >= cnt + 1; i--) {
if(vis[i][cnt]==0){
a.add(matrix[i][cnt]);
vis[i][cnt] = 1;
}
}
AddNumber(cnt + 1, a, matrix, vis);
}
} 思路二：缩小边界
初始边界：up=0,down=matrix.length-1,left=0,right=matrix[0].length-1；
代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> a = new ArrayList<Integer>();
int height = matrix.length;
int weight = matrix[0].length;
int up=0,down=matrix.length-1,left=0,right=matrix[0].length-1;
if(matrix==null)
return a;
while(true){
for(int i=left;i<=right;i++){
a.add(matrix[up][i]);
}
up++;
if(up>down) break;//判断越界
for(int i=up;i<=down;i++){
a.add(matrix[i][right]);
}
right--;
if(left>right) break;//判断越界
for(int i=right;i>=left;i--){
a.add(matrix[down][i]);
}
down--;
if(up>down) break;//判断越界
for(int i=down;i>=up;i--){
a.add(matrix[i][left]);
}
left++;
if(left>right) break;//判断越界
}
return a;
}
} 思路三：层数解题
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> a = new ArrayList<Integer>();
if(matrix==null) return a;
int height = matrix.length;
int weight = matrix[0].length;
int layers = (Math.min(height, weight)+1)/2;
for(int cnt=0;cnt<layers;cnt++){
//四条边
for(int i=cnt;i<weight-cnt;i++) a.add(matrix[cnt][i]);
for(int i=cnt+1;i<height-cnt;i++) a.add(matrix[i][weight-cnt-1]);
for(int i=weight-cnt-2;(i>=cnt)&&(height-cnt-1!=cnt);i--) a.add(matrix[height-cnt-1][i]);
for(int i=height-cnt-2;(i>cnt)&&(weight-cnt-1!=cnt);i--) a.add(matrix[i][cnt]);
}
return a;
}
} ----待更新
