前言

该链接的学习计划如下：
剑指 Offer学习计划

上一版本的博文链接如下：
【leetcode】 剑指 Offer学习计划（java版本含注释）（上）

此贴两年前写的，一直在草稿箱里，今天释放出来，后续有时间完善下！（= - =）

第十六天（排序）

剑指 Offer 45. 把数组排成最小的数（中等）

题目：

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: “102”

示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

提示:

0 < nums.length <= 100

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

---

思路：

关于这部分的具体核心逻辑代码
可参考如下链接：

剑指 Offer 45. 把数组排成最小的数（自定义排序，清晰图解）

class Solution {public String minNumber(int[] nums) {//新建一个字符数组String []s=new String[nums.length];//遍历每个数组到字符数组中，具体转类型，通过String.valueOf(nums[i]);for(int i=0;i<nums.length;i++){s[i]=String.valueOf(nums[i]);}//通过快排将其排好顺序，运用大小的转换quicksort(s,0,s.length-1);//通过StringBuilder() 添加数组的，之后输出其toString类型StringBuilder res = new StringBuilder();for(int i=0;i<s.length;i++){res.append(s[i]);}return res.toString();}public void quicksort(String [] s,int l,int r){if(l>=r)return ;int left=l;int right=r;//具体快排的方式，主要是通过该逻辑x+y>y+x  则x大于y。如果x+y<y+x  则x小于y// 330 大于 303 。也就是30要排在3的后面。用此逻辑将其快排while(left<right){while(left<right && (s[right]+s[l]).compareTo(s[l]+s[right]) >=0)right--;while(left<right && (s[left]+s[l]).compareTo(s[l]+s[left]) <=0)left++;swap(s,left,right);}swap(s,left,l);quicksort(s,l,left-1);quicksort(s,left+1,r);}public void swap(String [] s,int left,int right){String temp=s[left];s[left]=s[right];s[right]=temp;}
}

剑指 Offer 61. 扑克牌中的顺子（简单）

题目：

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5

数组的数取值为 [0, 13] .

---

思路：

class Solution {public boolean isStraight(int[] nums) {Arrays.sort(nums);//将其数组进行排序int res=0;//只遍历到最后一个for(int i=0;i<4;i++){if(nums[i]==0){res++;//统计大小王的数量}//如果有重复的提前返回falseelse if(nums[i+1]==nums[i])return false;}//用最后一个值减去 最小值（除了0），如果小于5则是顺子return nums[4]-nums[res]<5;}
}

或者直接比较最大值最小值即可

class Solution {public boolean isStraight(int[] nums) {Set<Integer> repeat=new HashSet<>();int max=Integer.MIN_VALUE;int min=Integer.MAX_VALUE;for(int i=0;i<5;i++) {if(nums[i] == 0) continue; // 跳过大小王max = Math.max(nums[i],max); // 最大牌min = Math.min(nums[i],min); // 最小牌if(repeat.contains(nums[i])) return false; // 若有重复，提前返回 falserepeat.add(nums[i]); // 添加此牌至 Set}return max-min<5;}
}

注意这种写法：

int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;

第十七天（排序）

剑指 Offer 40. 最小的k个数（简单）

题目：

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

---

思路：

可以通过排序，然后在弄，但是复杂度比较高
这道题是简单题
可以使用复杂度比较低一些的
例如
快排

class Solution {public int[] getLeastNumbers(int[] arr, int k) {quicksort(arr,0,arr.length-1);//数组的截取前几个，通过这个函数return Arrays.copyOf(arr,k);}public void quicksort(int [] arr,int l,int r){if(l>=r)return;//记住左右的节点，因为l作为基准，到时候要替换变成有序的元素int left=l;int right=r;while(left<right){while(left<right&&arr[right]>=arr[l])right--;while(left<right&&arr[left]<=arr[l])left++;swap(arr,left,right);}//不要忘记更换基准的元素swap(arr,left,l);//中间节点已经有序，继续排左右两边的子数组就好quicksort(arr,l,left-1);quicksort(arr,left+1,r);}public void swap(int []arr,int left,int right){int temp=arr[left];arr[left]=arr[right];arr[right]=temp;}
}

或者使用大根堆或者小根堆的实现方式
以下使用的是PriorityQueue
大根堆(前 K 小) / 小根堆（前 K 大)

class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// 默认是小根堆，实现大根堆需要重写一下比较器。Queue<Integer> pq = new PriorityQueue<>((o1,o2)->(o2-o1));for (int num: arr) {if (pq.size() < k) {pq.offer(num);}else if(num<pq.peek()){pq.poll();pq.offer(num);}}// 返回堆中的元素int[] res = new int[pq.size()];int idx = 0;for(int num: pq) {res[idx++] = num;}return res;}
}

第十八天（搜索与回溯算法）

剑指 Offer 55 - I. 二叉树的深度（简单）

题目：略

---

思路：

递归：

class Solution {public int maxDepth(TreeNode root) {//从下往上递归，通过递归左右子树，然后将其判断哪个子树大，最后加1。往上遍历即可if(root==null)return 0;int left=maxDepth(root.left);int right=maxDepth(root.right);return Math.max(left,right)+1;}
}

层次遍历，在每一层加1计数即可

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);//为了方便计数每一层size，也就是最大的深度int ans = 0;while (!queue.isEmpty()) {int n = queue.size();for(int i=0;i<n;i++) {TreeNode node = queue.poll();if (node.left != null)queue.offer(node.left);               if (node.right != null)  queue.offer(node.right);}ans++;}return ans;}
}

剑指 Offer 55 - II. 平衡二叉树（简单）*

题目：略

---

思路：

class Solution {public boolean isBalanced(TreeNode root) {//返回的高度一定是非负整数，如果abs一直大于1，则会有负数的return heigh(root)>=0;}//重新定义一个int类型的函数，主要是为了返回左右子树的最大深度，在中间加一些判断条件public int heigh(TreeNode root){//终止条件判断，如果叶子节点为null，则直接返回0if(root==null)return 0;//从上往下递归遍历，一开始在最下面的一层次遍历int left=heigh(root.left);int right=heigh(root.right);//如果左子树或者右子树为-1.则往上层递归直接变为-1。还有一个abs直接大于1//不要忽略左右子树，某个数为-1的情况，主要是为了方便传递if(left==-1||right==-1||Math.abs(left-right)>1)return -1;//往上返回的左右子树最大的一个，直接加1。递归条件return Math.max(left,right)+1;}
}

第十九天（搜索与回溯算法）

剑指 Offer 64. 求1+2+…+n（中等）

题目：

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

1 <= n <= 10000

---

思路：

除法不能使用（数学中的求和不可使用）
for不能使用

class Solution {public int sumNums(int n) {int sum=0;for(int i=1;i<=n;i++){sum+=i;}return sum;}
}

那就通过异或或者递归的方式
该题解主要通过k神
具体解释如下：
面试题64. 求 1 + 2 + … + n（逻辑符短路，清晰图解）

class Solution {//定义一个临界值，放于外面，主要是不影响递归的调用int sum=0;public int sumNums(int n) {//x=n>1不可写成n>1因为boolean变量要修饰。//主要大于1，是因为1的时候是终止条件。具体的递归通过sumNums(n-1)boolean x=n>1&&sumNums(n-1)>1;sum+=n;return sum;}
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先（简单）

题目：略

---

思路：

总体通过root不为null，一个个值比较，如果有两者相等或者不统一，直接返回root节点即可

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(root!=null){if(root.val>p.val&&root.val>q.val){root=root.left;}else if(root.val<p.val&&root.val<q.val){root=root.right;}else {return root;}}return null;}
}

剑指 Offer 68 - II. 二叉树的最近公共祖先（简单）*

题目：
略

---

思路：

关于该题解，可看k神比较全面的题解：
k神题解

初始条件以及递归条件以及边界值的返回条件是什么
搞清楚逻辑传递即可

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null; // 如果树为空，直接返回nullif(root == p || root == q) return root; // 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁TreeNode right = lowestCommonAncestor(root.right, p, q); // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁if(left == null) return right; // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）else if(right == null) return left; // 否则，如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）else return root; //否则，当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root}
}

第二十天（分治算法）

剑指 Offer 07. 重建二叉树（中等）*

题目：

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

---

思路：

第二十一天（位运算）

剑指 Offer 15. 二进制中1的个数（简单）

题目：leetcode：剑指 Offer 15. 二进制中1的个数

---

思路：

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int x=1;int sum=0;while(n!=0){//此处记得括号if((n&x)==1){sum++;}//可以将上面一步到位//  sum += n & 1;//本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作//无符号的移动为>>>n=n>>>1;}return sum;}
}

剑指 Offer 65. 不用加减乘除做加法（简单）*

题目：leetcode：剑指 Offer 65. 不用加减乘除做加法

---

思路：
这道题的题解主要参考k神题解

class Solution {public int add(int a, int b) {while(b != 0) { // 当进位为 0 时跳出int c = (a & b) << 1;  // c = 进位a ^= b; // a = 非进位和b = c; // b = 进位}return a;}
}

第二十三天（数学）

剑指 Offer 39. 数组中出现次数超过一半的数字（简单）

题目：leetcode：剑指 Offer 39. 数组中出现次数超过一半的数字

---

思路：
可以用哈希统计 计算

class Solution {public int majorityElement(int[] nums) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num,map.getOrDefault(num,0)+1);        }//--//定义最大值int max=Integer.MIN_VALUE;//为了保留getKey的值int x=0;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() > max) {max = entry.getValue();x=entry.getKey();}}return x;//---或者使用如下进行Map.Entry<Integer, Integer> majorityEntry = null;for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {majorityEntry = entry;}}return majorityEntry.getKey();}
}

以及另外一种做法：
题解如下：k神题解

class Solution {public int majorityElement(int[] nums) {//相同票数则加1，不同票数减1，如果为0的票数，设置众数为当前int vote=0;int x=0;for(int num:nums){if(vote==0)x=num;vote+= x==num?1:-1;}return x;}
}

剑指 Offer 66. 构建乘积数组（中等）*

题目：leetcode：剑指 Offer 66. 构建乘积数组

大致意思如下：

---

思路：

class Solution {public int[] constructArr(int[] a) {if(a.length==0)return new int [0];int []b=new int[a.length];//设置第一个初值为1b[0]=1;//遍历后边的初值条件int temp=1;//计算从前往后的值，维护b【i】这个数组for(int i=1;i<b.length;i++){b[i]=b[i-1]*a[i-1];}for(int i=b.length-2;i>=0;i--){//从后往前的遍历，计算另外一边的值temp *= a[i + 1];b[i] *= temp;}return b;}
}

第二十五天

剑指 Offer 29. 顺时针打印矩阵（简单）

题目：leetcode：剑指 Offer 29. 顺时针打印矩阵

---

思路：

螺旋 模拟矩阵

class Solution {public int[] spiralOrder(int[][] matrix) {//可能是空数组，所以要多一个判断条件if(matrix.length == 0) return new int[0];int m=matrix.length;int n=matrix[0].length;//个数用来存放其res的总值int []res=new int[m*n];int left=0,right=n-1,top=0,bottom=m-1;//为了更好的定义，配合数组下标，所以统一减个1int num=0,sum=m*n-1;while(num<=sum){for(int i=left;i<=right && num<=sum;i++){res[num++]=matrix[top][i];}top++;for(int i=top;i<=bottom && num<=sum;i++){res[num++]=matrix[i][right];}right--;for(int i=right;i>=left && num<=sum;i--){res[num++]=matrix[bottom][i];}bottom--;for(int i=bottom;i>=top && num<=sum;i--){res[num++]=matrix[i][left];}left++;}return res;}
}