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

《剑指Offer》笔记&题解&思路&技巧&优化_Part_2

😍😍😍 相知
🙌🙌🙌 相识
🍓🍓🍓广度优先搜索BFS
🍓🍓🍓深度优先搜索DFS
😢😢😢 开始刷题
- 1. LCR 129. 字母迷宫——矩阵中的路径
- 2. LCR 130. 衣橱整理——机器人的运动范围
- 3. LCR 131. 砍竹子 I——剪绳子I
- 4. LCR 132. 砍竹子 II——剪绳子II
- 5. LCR 133. 位 1 的个数——二进制中1的个数
- 6. LCR 134. Pow(x, n)——数值的整数次方
- 7. LCR 135. 报数——打印从1到最大的n位数
- 8. LCR 136. 删除链表的节点——删除链表的节点
- 9. LCR 137. 模糊搜索验证——正则表达式匹配

在这里插入图片描述

😍😍😍 相知

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

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

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

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

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

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

🙌🙌🙌 相识

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

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

🍓🍓🍓广度优先搜索BFS

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

在这里插入图片描述

在这里插入图片描述
树——谁出来，放谁的子节点进去！

对于图来说！

在这里插入图片描述
图没有根节点，我们从任意一个节点出发！

在这里插入图片描述

🍓🍓🍓深度优先搜索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的最大乘积为1
        if (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 value
    public 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 value
    public 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 位为 i
            dfs(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]=\left\{ \begin{matrix} f[i-1][j-1] & s[i]=p[j] \\ \text{false } & s[i]\ne p[j] \\ \end{matrix} \right.$

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

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

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

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

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

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

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

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

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

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

$\begin{cases} f[i - 1][j] \text{~or~} f[i][j - 2], & s[i] = p[j - 1] \\ f[i][j - 2], & s[i] \neq p[j - 1] \end{cases}$

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

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

$\begin{cases} \text{if~} (p[j] \neq \text{~`*'}) = \begin{cases} f[i - 1][j - 1], & \textit{matches}(s[i], p[j])\\ \text{false}, & \text{otherwise} \end{cases} \\ \text{otherwise} = \begin{cases} f[i - 1][j] \text{~or~} f[i][j - 2], & \textit{matches}(s[i], p[j-1]) \\ f[i][j - 2], & \text{otherwise} \end{cases} \end{cases}$

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

细节

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

在上面的状态转移方程中，如果字符串 $p$ 中包含一个「字符 + 星号」的组合（例如 $a *$ ），那么在进行状态转移时，会先将 $a$ 进行匹配（当 $p [j]$ 为 $a$ 时），再将 $a *$ 作为整体进行匹配（当 $] p [j]$ 为 $*$ 时）。然而，在题目描述中，我们必须将 $a *$ 看成一个整体，因此将 $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);
    }
}