😍😍😍 相知

当你踏入计算机科学的大门，或许会感到一片新奇而陌生的领域，尤其是对于那些非科班出身的学子而言。作为一位非科班研二学生，我深知学习的道路可能会充满挑战，让我们愿意迎接这段充满可能性的旅程。

最近，我开始了学习《剑指Offer》和Java编程的探索之旅。这不仅是一次对计算机科学的深入了解，更是对自己学术生涯的一次扩展。或许，这一切刚刚开始，但我深信，通过努力与坚持，我能够逐渐驾驭这门技艺。

在这个博客中，我将深入剖析《剑指Offer》中的问题，并结合Java编程语言进行解析。

让我们一起踏上这段学习之旅，共同奋斗，共同成长。无论你是已经驾轻就熟的Java高手，还是像我一样初出茅庐的学子，我们都能在这里找到彼此的支持与激励。让我们携手前行，共同迎接知识的挑战，为自己的未来打下坚实的基石。

这是我上一篇博客的，也希望大家多多关注！

1. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_1

🙌🙌🙌 相识

根据题型可将其分为这样几种类型：

1. 结构概念类（数组，链表，栈，堆，队列，树）
2. 搜索遍历类（深度优先搜索，广度优先搜索，二分遍历）
3. 双指针定位类（快慢指针，指针碰撞，滑动窗口）
4. 排序类（快速排序，归并排序）
5. 数学推理类（动态规划，数学）

🍓🍓🍓广度优先搜索BFS

1. 选定一个结点访问
2. 访问完后入队
3. 依次访问已选结点相关联的其他结点并入队
4. 依次访问队中其他结点，访问完所有相关联结点后出队
5. 所有结点访问完成

树——谁出来，放谁的子节点进去！

---

对于图来说！

图没有根节点，我们从任意一个节点出发！

🍓🍓🍓深度优先搜索DFS

利用栈

😢😢😢 开始刷题

1. LCR 129. 字母迷宫——矩阵中的路径

题目跳转：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/description/

class Solution {public boolean wordPuzzle(char[][] grid, String target) {if(grid.length*grid[0].length< target.length())return false;boolean[][] visited = new boolean[grid.length][grid[0].length];for(int i = 0;i<grid.length;i++){for(int j =0;j<grid[i].length;j++){if(dfs(grid,i,j,target,0)) return true;}}return false;}public boolean dfs(char[][] grid,int i,int j,String target,int k){if(i<0||i>=grid.length||j<0||j>=grid[i].length||grid[i][j] != target.charAt(k)){return false;}if(k == target.length()-1)return true;grid[i][j] = '1';boolean res = dfs(grid,i,j+1,target,k+1)||dfs(grid,i+1,j,target,k+1)||dfs(grid,i,j-1,target,k+1)||dfs(grid,i-1,j,target,k+1);grid[i][j] = target.charAt(k);return res;}
}

---

2. LCR 130. 衣橱整理——机器人的运动范围

题目跳转：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/

补充说明如下：

digit(x)，表示数字 x 的个十百千…位数字之和，比如 digit(726) = 7 + 2 + 6 = 15
允许向下或向右移动一格，不允许跨过格子，如果向下向右的格子均不可整理，则不能继续向下向右移动，返回 [0][0] 坐标；
一次移动到尽头后，可以返回 [0][0] 位置，沿着一条新路径开始整理；

• 举例1：
  一个 4 x 7 的矩阵，cnt 为 5，
  则可整理的格子如下，y 表示可整理，n 表示不可整理：

\、	0	1	2	3	4	5	6
0	y	y	y	y	y	y	n
1	y	y	y	y	y	n	n
2	y	y	y	y	n	n	n
3	y	y	y	n	n	n	n

digit(0) + digit(6) = 0 + 6 = 6 > cnt (cnt为5)，所以不可整理，以此类推。
所以可整理格子数量总计为 18 格。

• 举例2：
  一个 4 x 11 的矩阵，cnt 为 2，
  则可整理的格子如下，y 表示可整理，n 表示不可整理：

|	0	1	2	3	4	5	6	7	8	9	10
0	y	y	y	n	n	n	n	n	n	n	n
1	y	y	n	n	n	n	n	n	n	n	n
2	y	n	n	n	n	n	n	n	n	n	n
3	n	n	n	n	n	n	n	n	n	n	n

digit(0) + digit(10) = 0 + 1+0 = 1 < cnt (cnt为2)，虽然满足digit要求，但没有可达的路径，
一次只能向下、向右移动一格，不能跨格子，所以[0][10]也不可整理。
所以可整理格子数量总计为 6 格。

class Solution {public int wardrobeFinishing(int m, int n, int cnt) {boolean[][] visited = new boolean[m][n];return dfs(0, 0, m, n, cnt, visited);}int dfs(int i, int j, int m, int n, int k, boolean visited[][]) {if (i < 0 || i >= m || j < 0 || j >= n || (i/10 + i%10 + j/10 + j%10) > k || visited[i][j]) {return 0;}visited[i][j] = true;return dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + 1;}
}

---

3. LCR 131. 砍竹子 I——剪绳子I

题目跳转：https://leetcode.cn/problems/jian-sheng-zi-lcof/description/

class Solution {public int cuttingBamboo(int bamboo_len) {// n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2, 同理2的最大乘积为1if (bamboo_len==1 ||  bamboo_len== 2)return 1;if (bamboo_len == 3)return 2;int sum = 1;while(bamboo_len>4){sum *=3;bamboo_len -=3;}return sum*bamboo_len;}
}

class Solution {public int cuttingRope(int bamboo_len) {int[] dp = new int[bamboo_len + 1];for (int i = 2; i <= bamboo_len; i++) {int curMax = 0;for (int j = 1; j < i; j++) {curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));}dp[i] = curMax;}return dp[bamboo_len];}
}

---

4. LCR 132. 砍竹子 II——剪绳子II

题目跳转：https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/description/

贪心算法：

class Solution {public int cuttingBamboo(int bamboo_len) {if (bamboo_len==1 ||  bamboo_len== 2)return 1;if (bamboo_len == 3)return 2;long res = 1;while(bamboo_len>4){res *=3;res = res%1000000007;bamboo_len -=3;}return (int)(res*bamboo_len%1000000007);}
}

动态规划+大数：

import java.math.BigInteger;class Solution {public int cuttingRope(int n) {BigInteger dp[] = new BigInteger[n + 1];Arrays.fill(dp, BigInteger.valueOf(1));for (int i = 3; i <= n; i++) {for (int j = 1; j < i; j++) {dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));}}return  dp[n].mod(BigInteger.valueOf(1000000007)).intValue();}
}

---

5. LCR 133. 位 1 的个数——二进制中1的个数

题目跳转：https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/description/

学个小小函数：

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {return Integer.bitCount(n);}
}

public int hammingWeight(int n) {String s = Integer.toBinaryString(n);int count = 0;for (int i = 0; i < s.length(); i++){if (s.charAt(i) == '1')count++;}return count;
}

• 异或运算的性质?
  • 运算规则:相同为0，不同为1
  • N^0= N
  • N^N=0
  • a^b=b^a
  • a^(b^C) = (a^b)^c

把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int count=0;while(n!=0){n=n&(n-1);count++;}return count;}
}

---

6. LCR 134. Pow(x, n)——数值的整数次方

题目跳转：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/description/

首先主打一个叛逆！但是你真这么写 别逼我删你 我们主要是熟悉函数！

class Solution {public double myPow(double x, int n) {return Math.pow(x,n);}
}

class Solution {public double myPow(double x, int n) {if(n==0)return 1;if(n==1)return x;if(n==-1)return 1/x;double half = myPow(x, n / 2);double mod = myPow(x, n % 2);return half * half * mod;}
}

---

7. LCR 135. 报数——打印从1到最大的n位数

题目跳转：https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/description/

class Solution {public int[] countNumbers(int cnt) {int[] temp  = new int[(int)Math.pow(10,cnt)-1];for(int i = 0;i < temp.length;i++){temp[i] = i+1;}return temp;}
}

要是考虑大数！！

class Solution {StringBuilder res;int count = 0, cnt;char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};public String countNumbers(int cnt) {this.cnt = cnt;res = new StringBuilder(); // 数字字符串集num = new char[cnt]; // 定义长度为 cnt 的字符列表dfs(0); // 开启全排列递归res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号return res.toString(); // 转化为字符串并返回}void dfs(int x) {if(x == cnt) { // 终止条件：已固定完所有位res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部，使用逗号隔开return;}for(char i : loop) { // 遍历 ‘0‘ - ’9‘num[x] = i; // 固定第 x 位为 idfs(x + 1); // 开启固定第 x + 1 位}}
}

---

8. LCR 136. 删除链表的节点——删除链表的节点

题目跳转：https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/description/

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode deleteNode(ListNode head, int val) {if(head.val==val) return head.next;ListNode result = head;while(head.next!=null){if(head.next.val == val ){head.next = head.next.next;break;}head = head.next;}return result;}
}

---

9. LCR 137. 模糊搜索验证——正则表达式匹配

题目跳转：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/description/

题目中的模糊搜索验证是指一个「逐步匹配」的过程：我们每次从字符串$p$ 中取出一个字符或者「字符 + 星号」的组合，并在$s$中进行匹配。对于 $p$ 中一个字符而言，它只能在$s$ 中匹配一个字符，匹配的方法具有唯一性；而对于$p$ 中字符 + 星号的组合而言，它可以在 $s$中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。

我们用 $f[i][j]$ 表示 $s$ 的前 $i$ 个字符与 $p$ 中的前 $j$ 个字符是否能够匹配。在进行状态转移时，我们考虑 $p$ 的第 $j$ 个字符的匹配情况：

如果 $p$ 的第 $j$ 个字符是一个小写字母，那么我们必须在 $s$ 中匹配一个相同的小写字母，即

$$f[i][j]=\{\begin{array}{cc}f[i-1][j-1]& s[i]=p[j]\\ \text{false }& s[i]\ne p[j]\end{array}$$

也就是说，如果 $s$ 的第 $i$ 个字符与 $p$ 的第 $j$ 个字符不相同，那么无法进行匹配；否则我们可以匹配两个字符串的最后一个字符，完整的匹配结果取决于两个字符串前面的部分。

如果 $p$ 的第 $j$ 个字符是 $\ast$，那么就表示我们可以对 $p$ 的第 $j-1$ 个字符匹配任意自然数次。在匹配 $0$ 次的情况下，我们有

$$f[i][j]=f[i][j-2]$$

也就是我们「浪费」了一个字符 + 星号的组合，没有匹配任何 $s$ 中的字符。

在匹配 1,2,3,⋯1,2,3, \cdots1,2,3,⋯ 次的情况下，类似地我们有

$$\begin{array}{rlrl}& f[i][j]=f[i-1][j-2],& & \text{if }s[i]=p[j-1]\\ & f[i][j]=f[i-2][j-2],& & \text{if }s[i-1]=s[i]=p[j-1]\\ & f[i][j]=f[i-3][j-2],& & \text{if }s[i-2]=s[i-1]=s[i]=p[j-1]\\ & \cdots \cdots & & \end{array}$$

​

如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了 $s$ 中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：字母 + 星号的组合在匹配的过程中，本质上只会有两种情况：

匹配 $s$ 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；

不匹配字符，将该组合扔掉，不再进行匹配。

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：

$$f[i][j]=\{\begin{array}{ll}f[i-1][j]\text{ or }f[i][j-2],& s[i]=p[j-1]\\ f[i][j-2],& s[i]\ne p[j-1]\end{array}$$

​

在任意情况下，只要 $p[j]$是$.$，那么 $p[j]$ 一定成功匹配$s$中的任意一个小写字母。

最终的状态转移方程如下：

$$f[i][j]=\{\begin{array}{l}\text{if }(p[j]\ne \text{ ‘*’})=\{\begin{array}{ll}f[i-1][j-1],& \text{matches}(s[i],p[j])\\ \text{false},& \text{otherwise}\end{array}\\ \text{otherwise}=\{\begin{array}{ll}f[i-1][j]\text{ or }f[i][j-2],& \text{matches}(s[i],p[j-1])\\ f[i][j-2],& \text{otherwise}\end{array}\end{array}$$

​

其中 $\text{matches}(x,y)$ 判断两个字符是否匹配的辅助函数。只有当 $y$ 是 $.$ 或者 $x$ 和 $y$ 本身相同时，这两个字符才会匹配。

细节

动态规划的边界条件为 $f[0][0]=\text{true}$，即两个空字符串是可以匹配的。最终的答案即为 $f[m][n]$，其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $p$ 的长度。由于大部分语言中，字符串的字符下标是从 $0$ 开始的，因此在实现上面的状态转移方程时，需要注意状态中每一维下标与实际字符下标的对应关系。

在上面的状态转移方程中，如果字符串 $p$ 中包含一个「字符 + 星号」的组合（例如 $a\ast$），那么在进行状态转移时，会先将 $a$ 进行匹配（当$p[j]$ 为 $a$ 时），再将 $a\ast$ 作为整体进行匹配（当 $]p[j]$ 为 $\ast$ 时）。然而，在题目描述中，我们必须将 $a\ast$ 看成一个整体，因此将 $a$ 进行匹配是不符合题目要求的。看来我们进行了额外的状态转移，这样会对最终的答案产生影响吗？这个问题留给读者进行思考。

class Solution {public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();boolean[][] f = new boolean[m + 1][n + 1];f[0][0] = true;for (int i = 0; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p.charAt(j - 1) == '*') {f[i][j] = f[i][j - 2];if (matches(s, p, i, j - 1)) {f[i][j] = f[i][j] || f[i - 1][j];}} else {if (matches(s, p, i, j)) {f[i][j] = f[i - 1][j - 1];}}}}return f[m][n];}public boolean matches(String s, String p, int i, int j) {if (i == 0) {return false;}if (p.charAt(j - 1) == '.') {return true;}return s.charAt(i - 1) == p.charAt(j - 1);}
}

---