| 03-19 | |
| 20-39 |
《剑指offer第2版》Java题解总结（中）_科技小猎豹的博客-CSDN博客 |
| 40-68 |
03-19
03. 数组中重复的数字
数组元素交换。时间On，空间O1.
04.二维数组中的查找
本题与力扣 240 题同
法二：从左下角或右上角搜索。时间复杂度 O(m+n)，空间复杂度 O(1)。为矩阵的行数、列数。
leetcode/lcof/面试题04. 二维数组中的查找 at main · doocs/leetcode · GitHub
05.替换空格
自己遍历比replace（）更快
06.从尾到头打印链表
头插法、栈、递归多种方法。
07. 重建二叉树
本题与主站 105 题重复
测试用例
普通二叉树（完全二叉树；不完全二叉树）
特殊二叉树（所有节点都没有右子节点的二叉树；所有节点都没有左子节点的二叉树；只有一个节点的二叉树）
特殊输入测试（二叉树的根节点为空；输入的前序序列和中序序列不匹配）
力扣
只适用于无重复节点二叉树。分治
08.二叉树的下一个节点
中序遍历
09.用两个栈实现队列
leetcode/lcof/面试题09. 用两个栈实现队列 at main · doocs/leetcode · GitHub
10-I.斐波那契数列问题
动态规划
力扣
10- II. 青蛙跳台阶问题
11. 旋转数组的最小数字
与主站 154 题相同
12. 矩阵中的路径
（ DFS + 剪枝
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
// 遍历图
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
// 如果找到了，就返回true。否则继续找
if(dfs(board, words, i, j, 0)) return true;
}
}
// 遍历结束没找到false
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
// 判断传入参数的可行性 i 与图行数row比较，j与图列数col比较
// i，j初始都是0，都在图左上角
// k是传入字符串当前索引，一开始是0，如果当前字符串索引和图当前索引对应的值不相等，表示第一个数就不相等
// 所以继续找第一个相等的数。题目说第一个数位置不固定，即路径起点不固定（不一定是左上角为第一个数）
// 如果board[i][j] == word[k]，则表明当前找到了对应的数，就继续执行（标记找过，继续dfs 下上右左）
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
// 表示找完了，每个字符都找到了
// 一开始k=0，而word.length肯定不是0，所以没找到，就执行dfs继续找。
if(k == word.length - 1) return true;
// 访问过的标记空字符串，“ ”是空格 '\0'是空字符串，不一样的！
// 比如当前为A，没有标记找过，且A是word中对应元素，则此时应该找A下一个元素，假设是B，在dfs（B）的时候还是-
// ->要搜索B左边的元素（假设A在B左边），所以就是ABA（凭空多出一个A，A用了2次，不可以），如果标记为空字符串->
// 就不会有这样的问题，因为他们值不相等AB != ABA。
board[i][j] = '\0';
// 顺序是 下 上 右 左；上面找到了对应索引的值所以k+1
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
// 还原找过的元素，因为之后可能还会访问到（不同路径）
board[i][j] = word[k];
// 返回结果，如果false，则if(dfs(board, words, i, j, 0)) return true;不会执行，就会继续找
return res;
}
}
13.机器人的运动范围
数位和增量公式：
力扣
以下代码为增量公式的三元表达式写法，将整合入最终代码中。(x + 1) % 10 != 0 ? s_x + 1 : s_x – 8;
14- I. 剪绳子
与主站 343 题相同
动规、数学等等
力扣
关于为什么切分为3的优先级最高 可以利用均值不等式求出乘积最大值 L(m)=(n/m)^m 对此式求导（可利用对数法），可以证明当 m=n/e 时，乘积取最大，此时每段绳子的长度为 n/(n/e)=e，自然对数e的值为2.718，显然接近3，所以总体来讲3最好
class Solution {
public int cuttingRope(int n) {
if(n <= 3) return n - 1;
int a = n / 3, b = n % 3;
if(b == 0) return (int)Math.pow(3, a);
if(b == 1) return (int)Math.pow(3, a - 1) * 4;
return (int)Math.pow(3, a) * 2;
}
}
14- II. 剪绳子 II 大数越界情况下的求余问题
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
int a = n / 3;
int b = n % 3;
// ans * 3 可能在求余之前超出int32的值，所以用long类型
long ans = 1;
switch(b) {
case 0 :
for(int i = 0; i < a; i++) {
ans = ans * 3 % 1000000007 ;
}
break;
case 1 :
for(int i = 0; i < a - 1; i++) {
ans = ans * 3 % 1000000007 ;
}
ans = ans * 4 % 1000000007;
break;
case 2 :
for(int i = 0; i < a; i++) {
ans = ans * 3 % 1000000007 ;
}
ans = ans * 2 % 1000000007;
break;
}
return (int)ans;
}
}
15. 二进制中1的个数
public int hammingWeight(int n) {
int res = 0;
while(n != 0) {
res += n & 1;
n >>>= 1;
}
return res;
}
16. 数值的整数次方
与主站 50 题相同：
力扣
快速幂（数论），在普通计算机内，数是用补码表示滴，而这里b = -b 和 b = -n就隐藏着这个坑。int由于补码无法表示+2147483648。b不能用-n赋值，必须用-b 因为b是long的 可以表示+2147483648
力扣
K佬题解
17. 打印从1到最大的n位数
String表示大数，全排列dfs。
Integer.parseInt这个接口,会自动把整数前面的0去掉。（此法速度慢）
class Solution {
char[] num;
int[] ans;
int count = 0,n;
public int[] printNumbers(int n) {
this.n = n;
num = new char[n];
ans = new int[(int) (Math.pow(10, n) - 1)];
dfs(0);
return ans;
}
private void dfs(int n) {
if (n == this.n) {
String tmp = String.valueOf(num);
int curNum = Integer.parseInt(tmp);
if (curNum!=0) ans[count++] = curNum;
return;
}
for (char i = '0'; i <= '9'; i++) {
num[n] = i;
dfs(n + 1);
}
}
}
18. 删除链表的节点
注意各种特殊情况、限制条件。
public ListNode deleteNode(ListNode head, int val) {
if(head.val == val) return head.next;
ListNode pre = head, cur = head.next;
while(cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if(cur != null) pre.next = cur.next;
return head;
}
19. 正则表达式匹配
hard，动规or递归
class Solution {
public boolean isMatch(String A, String B) {
int n = A.length();
int m = B.length();
boolean[][] f = new boolean[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
//分成空正则和非空正则两种
if (j == 0) {
f[i][j] = i == 0;
} else {
//非空正则分为两种情况 * 和 非*
if (B.charAt(j - 1) != '*') {
if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {
f[i][j] = f[i - 1][j - 1];
}
} else {
//碰到 * 了，分为看和不看两种情况
//不看
if (j >= 2) {
f[i][j] |= f[i][j - 2];
}
//看
if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {
f[i][j] |= f[i - 1][j];
}
}
}
}
}
return f[n][m];
}
}