LeetCode刷题笔记

参考链接：图解算法数据结构
- 动态规划
- 搜索与回溯算法
  - 剑指Offer 12 – 矩阵中的路径
  - 剑指Offer 13 – 机器人的运动范围

参考链接：图解算法数据结构

代码和思路主要来源：

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/
来源：力扣（LeetCode）

动态规划

剑指Offer 58 – Ⅱ.左旋转字符串

四种解题思路

字符串切片(简单效率高)

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        return s.substr(n, s.size()) + s.substr(0, n);
    }
};

列表、字符串遍历拼接
原理类似：通过新建list或者string变量res，先向res添加“第n + 1位至末位的字符”，再向 res 添加 “首位至第n位的字符” ，最后将res转化为字符串并返回。
三次翻转(C++)
由于C++中的字符串是可变类型，因此可在原字符串上直接操作实现字符串旋转，实现O(1)的空间复杂度。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        //使用双向迭代器的重排算法，reverse(beg, end)
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

剑指Offer 67 – 把字符串转换成整数

主站第8题

先贴代码

class Solution {
public:
    int strToInt(string str) {
        int res = 0, bndry = INT_MAX / 10;	// 变量初始化
        int i = 0, sign = 1, length = str.size();	// 默认sign为正
        if(length == 0) return 0;	// 若为空字符串，直接返回0
        while(str[i] == ' ')	// 先判断字符串开头是否为空格，若为true则进入if语句
            if(++i == length) return 0;	// i+1后是否已经到达字符串尾部，若为true,返回0
        if(str[i] == '-') sign = -1;	// 开始判断正负号，已经默认为正了，所以仅作负号判断即可
        if(str[i] == '-' || str[i] == '+') i++;	// 符号位判断结束，i+1开始遍历
        for(int j = i; j < length; j++) {	// 临时变量j，遍历字符串
            if(str[j] < '0' || str[j] > '9') break;	// 每次循环先判断当前字符是否不是数字，若为true，直接跳出循环
            if(res > bndry || res == bndry && str[j] > '7')	// 拼接前，判断是否会越界，若为true，返回
                return sign == 1 ? INT_MAX : INT_MIN;
            res = res * 10 + (str[j] - '0'); // 拼接，10进制
        }
        return sign * res;	// 结束符号位，返回数值
    }
};

考虑四种字符：

首部空格：直接删除；
符号位，利用一个int变量sign保存符号位，默认为正，取值为1，若为负，取值为-1，在返回前做正负判断，即在代码最后乘上sign；
非数字字符：碰到首个非数字的字符时，立即返回；
数字字符：
1. 字符转数字：此数字的ASCII码与0的ASCII码相减即可，(str[j] - '0');
  2. 数字拼接：从左向右遍历数字，res = res * 10 + (str[j] - '0');

数字越界处理：

在每轮数字拼接前，判断res在此轮拼接后是否超过2147483647，若超过则加上符号位直接返回。

设数字拼接编辑 bndry = 2147483647 // 10 = 214748364，则有以下两种情况越界：

res > bndry 情况一：执行拼接10×res≥2147483650越界
res = bndry, x > 7 情况二：拼接后是2147483648或2147483649越界

if(res > bndry || res == bndry && str[j] > '7')

剑指Offer 10-Ⅰ. 斐波那契数列

递归解决，因为当n很大的时候可能会出现数字溢出，所以我们需要用结果对1000000007求余。如果直接对最后的结果求余会有一个问题，即可能还没执行到最后一步就已经溢出了，所以需要对每一步的计算都求余。但由于这样递归的时候会造成大量的重复计算，所以运行起来会超时。

class Solution{
public:
    int fib(int n){
        if(n < 2) return n;
        int first = fib(n - 1) % 1000000007;
        int second = fib(n - 2) % 1000000007; 
        return (first + second) % 1000000007;
    }
}

为了避免重复计算，可以使用一个关联容器map把计算过的值保存，每次计算的时候先从map中查找有没有。

int constant = 1000000007;

public int fib(int n) {
    return fib(n, new HashMap());
}

public int fib(int n, Map<Integer, Integer> map) {
    if (n < 2)
        return n;
    if (map.containsKey(n))
        return map.get(n);
    int first = fib(n - 1, map) % constant;
    map.put(n - 1, first);
    int second = fib(n - 2, map) % constant;
    map.put(n - 2, second);
    int res = (first + second) % constant;
    map.put(n, res);
    return res;
}
作者：sdwwld
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/di-gui-he-fei-di-gui-liang-chong-fang-shi-du-ji-ba/

推荐做法：非递归做法，动态规划
- 状态定义：设dp为一维数组，其中dp[i]的值代表斐波那契数列的第i个数字
- 转移方程：dp[i + 1] = dp[i] + dp[i - 1]，即对应数列定义f(n + 1) = f(n) + f(n - 1);
- 初始状态： dp[0] = 0，dp[1] = 1，即初始化前两个数字;
- 返回值：dp[n]，即斐波那契数列的第n个数字。

public int fib(int n) {
    int constant = 1000000007;
    int a = 0;
    int b = 1;
    for(int i = 0;i < n; i++) {
        int sum = (a + b) % constant;	//先求和,求余法则(x+y)⊙p=(x⊙p+y⊙p)⊙p 
        a = b;	
        b = sum;
    }
    return a;  //为什么要返回a呢？可以自己手写下，当n等于4的时候，返回a的值是5，但sum是8，所以返回a的值才是对的。
}

剑指Offer 10- Ⅱ.青蛙跳台阶问题

动态规划：

若f(x)表示爬到第x级台阶的方案数，由于最后一步可能跨了一级台阶，也可能跨了两级台阶，所以转移方程为：

\[f(x) = f(x – 1) + f(x – 2)
\]

边界条件：爬第0级可以看作只有一种方案，即f(0) = 1；从0级到第1级也只有一种方案，即爬一级，f(1) = 1。

优化：由于f(x) 只和 f(x – 1)与 f(x – 2)有关，所以可以用「滚动数组思想」把空间复杂度优化成 O(1)。

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

剑指Offer 42 – 连续子数组的最大和

标准动态规划解题流程：

状态定义：设动态规划列表dp，dp[i]代表以元素nums[i]为结尾的连续子数组最大和。

为何定义最大和dp[i]中必须包含元素nums[i]：保证dp[i]递推到dp[i+1]的正确性；如果不包含nums[i]，递推时则不满足题目的连续子数组要求。
转移方程：若dp[i - 1] ≤ 0，说明dp[i - 1]对dp[i]产生负贡献，即dp[i- 1]+nums[i]还不如nums[i]本身大。

\[dp[i] = \left\{
\begin{aligned}
dp[i−1]+nums[i],dp[i−1]>0\\
nums[i],dp[i−1]≤0
\end{aligned}
\right.
\]
初始状态: dp[0] = nums[0]，即以nums[0]结尾的连续子数组最大和为nums[0]。
返回值：返回dp列表中的最大值。

由于 dp[i]只与 dp[i-1]和 nums[i]有关系，因此可以将原数组 nums 用作 dp列表，即直接在 nums上修改即可。降低至空间复杂度O(1)。

class Solution{
public:
    int maxSubArray(vector<int>& nums){
        int res = nums[0];
        for(auto i = 1; i < nums.size(); i++){
            if(nums[i - 1] > 0) nums[i] += nums[i - 1];
            if(nums[i] > res) res = nums[i];
        }
        return res;
    }
}

剑指Offer 46 – 把数字翻译成字符串

转移方程：

动态规划解析：

记数字$num$第$i$位数字为$ x_i $,数字$num$的位数为$n$；

例如：$num = 12258$的$n = 5, x1 = 1$

状态定义： 设动态规划列表$ dp，dp[i]$代表以$x_i$为结尾的数字的翻译方案数量。
转移方程：若$x_i$和$x_i – 1$组成的两位数字可被整体翻译，则$dp[i] = dp[i – 1] + dp[i – 2]$，否则$dp[i]=dp[i – 1]$。

\[dp[i] = \left\{
\begin{aligned}
dp[i – 1] + dp[i – 2], (10x_{i-1} + x_i)\in [10,25]\\
dp[i – 1]， (10x_{i-1} + x_i)\in [0,10)\bigcup (25,99]
\end{aligned}
\right.
\]

可被整体翻译的两位数区间分析：当 $x_{i-1} = 0$ 时，组成的两位数无法被整体翻译（例如 00, 01, 02,⋯ ），大于 25的两位数也无法被整体翻译（例如 26, 27,⋯ ），因此区间为$ [10, 25] $。
初始状态：$dp[0] = dp[1] = 1$，即“无数字”和“第1位数字”的翻译方法数量均为1；
返回值：$dp[n]$，即此数字的翻译方案数量;

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num); //将数字转化为字符串，方便获取数字的各位x_i，通过遍历s实现动态规划
        int a = 1, b = 1, len = s.size();
        for(int i = 2; i <= len; i++) {
            string tmp = s.substr(i - 2, 2);
            int c = tmp.compare("10") >= 0 && tmp.compare("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
};

剑指Offer 47 – 礼物的最大价值

解题思路：

根据题目说明，得到某单元格只可能从上边单元格或左边单元格到达。

设$ f(i, j) $ 为从棋盘左上角走至单元格$ (i, j) $的礼物最大累计价值，易得到以下递推关系：$ f(i, j)$ 等于$ f(i, j – 1) $ 和 $ f(i – 1, j) $ 中的较大值加上当前单元格礼物价值$ grid(i, j) $。

\[f(i, j) = max[f(i, j – 1), f(i – 1, j)] + grid(i, j)
\]

因此，可用动态规划解决此问题，以上公式编为转移方程。

状态定义：设动态规划矩阵$ dp$，$dp(i,j)$代表从棋盘的左上角开始，到达单元格$ (i,j)$时能拿到礼物的最大累计价值。

转移方程：

当 i = 0 且 j = 0 时，为起始元素；
当 i = 0 且 j ≠ 0 时，为矩阵第一行元素，只可从左边到达;
当 i ≠ 0 且 j ≠ 0 时，为矩阵第一列元素，只可从上边到达；
当 i ≠ 0 且 j ≠ 0 时，可从左边或上边到达；

\[dp(i,j) =\left\{
\begin{aligned}
grid(i, j),i = 0, j = 0\\
grid(i, j) + dp(i, j – 1) ,i = 0, j \not= 0\\
grid(i, j) + dp(i – 1, j) ,i \not= 0, j = 0\\
grid(i, j) + max[dp(i – 1,j), dp(i, j – 1)] ,i \not= 0, j\not= 0
\end{aligned}
\right.
\]

初始状态：$dp[0][0] = grid[0][0]$，即到达单元格(0, 0)时能拿到礼物的最大累计价值为$grid[0][0]$；

返回值：$dp[m – 1][n – 1]$，m, n分别为矩阵的行高和列宽，即返回$dp$矩阵右下角元素。

空间复杂度降低：

由于$ dp[i][j]$只与$dp[i – 1][j], dp[i][j – 1], grid[i][j]$有关系，因此可以将原矩阵grid用作dp矩阵，即直接再grid上修改即可。
应用此方法可省去$dp$矩阵使用的额外空间，因此空间复杂度从O(MN)降至O(1)。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0) continue;
                if(i == 0 && j != 0) {
                    grid[i][j] += grid[0][j - 1];
                    continue;
                }
                if(i != 0 && j == 0){
                    grid[i][j] += grid[i - 1][0];
                    continue;
                }
                grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m - 1][n - 1];
    }
};

剑指Offer 48 – 最长不含重复字符子串

请注意理解题目：是找无重复字符！

长度为N的字符串公有$ \frac{(1+N)(N)}{2} $个子字符串（复杂度为$O(N^{2)$），判断长度为N的字符串是否有重复字符的复杂度为$O(N)$，因此本题使用暴力法解决的复杂度为$O(N}3)$。考虑使用动态规划降低时间复杂度。

动态规划解析：

状态定义：设动态规划列表$dp$，$dp[j]$代表以字符$s[j]$为结尾的”最长不重复子字符串”的长度。
转移方程：固定右边界$j$，设字符$s[j]$左边距离最近的相同字符为$s[i]$，即$s[i] = s[j]$。
1. 当$i < 0$，即$s[j]$左边无相同字符，则$dp[j] = dp[j – 1] + 1$;
2. 当$dp[j – 1] < j – i$，说明字符$s[i]$在子字符串$dp[j – 1]$区间之外，则$dp[j] = dp[j – 1] + 1$;
3. 当$dp[j – 1] ≥ j – i$，说明字符$s[i]$在子字符串$dp[j – 1]$区间之中，则$dp[j]$的左边界由$s[i]$决定，即$dp[j] = j – i$；

当$i < 0$时，由于$dp[j – 1] ≤ j $恒成立，因而$dp[j – 1] < j – i$恒成立，因此分支1.和2.可被合并。

\[dp[j]=\left\{
\begin{aligned}
dp[j – 1] + 1,dp[j-1]<j-i\\
j-i,dp[j-1] \geq j-i
\end{aligned}
\right.
\]

返回值：$max(dp)$，即全局的”最长不重复子字符串“的长度。

空间复杂度降低：

由于返回值是取$dp$列表最大值，因此可借助变量$tmp$存储$dp[j]$，变量$res$每轮更新最大值即可。
此优化可节省$dp$列表使用的$O(N)$大小的额外空间。

待解决问题：每轮遍历字符$s[j]$时，如何计算索引$i$？

方法一：动态规划 + 哈希表

哈希表统计：遍历字符串$s$时，使用哈希表（记为$dic$）统计各字符最后一次出现的索引位置。
左边界i获取方式：遍历到$s[j]$时，可通过访问哈希表$dic[s[j]]$获取最近的相同字符的索引$i$。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> dic;
        int res = 0, tmp = 0, len = s.size(), i = -1;
        for(int j = 0; j < len; j++){
            if(dic.find(s[j]) == dic.end()) i = -1;
            else i = dic.find(s[j])->second; // 获取索引i
            dic[s[j]] = j;	// 更新哈希表
            tmp = tmp < j - i? tmp + 1: j - i;
            res = max(res, tmp);
        }
        return res;
    }
};

方法二：动态规划 + 线性遍历

左边界$i$获取方式：遍历到$s[j]$时，初始化索引$i= j – 1$，向左遍历搜索第一个满足$s[i] = s[j]$的字符即可。

class Solution{
public:
	int lengthOfLongestSubstring(string s){
        int res = 0, tmp = 0, len = s.size();
        for(int j = 0; j < len; j++){
            int i = j - 1;
            while(i >= 0 && s[i] != s[j]) i--;	//线性查找
            tmp = tmp < j - i ? tmp + 1: j - i;	//dp[j - 1]->dp[j]
            res = max(res, tmp);	//max(dp[j-1], dp[j])
        }
        return res;
    }
}

方法三：双指针 + 哈希表

哈希表$dic$统计：指针$j$遍历字符$s$，哈希表统计字符$s[j]$最后一次出现的索引。
更新左指针i：根据上轮左指针$i$和$dic[s[j]]$，每轮更新左边界$i$，保证区间$[i + 1, j]$内无重复字符且最大。

\[i = max(dic[s[j]], i)
\]
更新结果$res$：取上轮$res$和本轮双指针区间$[i + 1， j]$的宽度（即$j – i$）中的最大值。

\[res = max(res, j – i)
\]

class Solution{
public:
	int lengthOfLongestSubstring(string s){
		unordered_map<char, int> dic;
        int i = -1, res = 0, len = s.size();
        for(int j = 0; j < len; j++){
            if(dic.find(s[j]) != dic.end())
                i = max(i, dic.find(s[j])->second);	// 更新左指针
            dic[s[j]] = j;	// 更新哈希表记录
            res = max(res, j - i);	// 更新结果
        }
        return res;
    }
}

剑指Offer 49 – 丑数

参考：

作者：LZH_Yves
链接：https://leetcode-cn.com/problems/ugly-number-ii/solution/bao-li-you-xian-dui-lie-xiao-ding-dui-dong-tai-gui/

题目描述：只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

解题思路：

抽数的递推性质：丑数只包含因子2，3，5，因此有”丑数=某较小丑数 x 某因子“（例如：10 = 5 x 2）。

设已知长度为$n$的丑数序列$x_{1},x_{2},…,x_{n}$，求第n+1个丑数$x_{n+1}$。根据递推性质，丑数$x_{n+1}$只可能是以下三种情况其中之一（索引a,b,c为未知数）：

\[x_{n+1} = \left\{
\begin{aligned}
x_{a} \times 2, a \in [1,n]\\
x_{b} \times 3, b \in [1,n]\\
x_{c} \times 5, c \in [1,n]
\end{aligned}
\right.
\]

方法一：暴力法(brute force)

为啥我脑子里得暴力法是拿一个个数去除，人家想的就不一样，菜的扣脚！

class Solution{
public:
    int nthUglyNumber(int n){
        vector<int> v;
        for(long long a = 1; a <= INT_MAX; a = a * 2)
            for(long long b = a; b <= INT_MAX; b = b * 3)
                for(long long c = b; c <= INT_MAX; c = c * 5)
                    v.push_back(c);
        sort(v.begin(), v.end());
        return v.at(n - 1);
    }
};

方法二：动态规划

丑数递推公式：若索引a,b,c满足以上条件，则下个丑数$x_{n+1}$为以下三种情况中的最小值：

\[x_{n+1}=min(x_{a} \times 2, x_{b} \times 3, x_{c} \times 5)
\]

由于$x_{n+1}$是最接近$x_{n}$的丑数，因此索引a,b,c需满足以下条件：

\[\left\{
\begin{aligned}
x_{a} \times 2 > x_{n} \geq x_{a-1} \times 2, 即x_{a}为首个乘以2后大于x_{n}的丑数\\
x_{b} \times 3 > x_{n} \geq x_{b-1} \times 3, 即x_{b}为首个乘以3后大于x_{n}的丑数\\
x_{c} \times 5 > x_{n} \geq x_{c-1} \times 5, 即x_{c}为首个乘以5后大于x_{n}的丑数
\end{aligned}
\right.
\]

设置指针a，b，c指向首个丑数（即1），循环根据递推公式得到下个丑数，并每轮将对应指针执行+1即可。

状态定义：设动态规划列表$dp$，$dp[i]$代表第$i+1$个丑数；
转移方程：
1. 当索引$a,b,c$满足以下条件时，$dp[i]$为三种情况的最小值；
2. 每轮计算$dp[i]$后，需要更新索引$a,b,c$的值，使其始终满足方程条件。实现方法：分别独立判断$dp[i]$和$dp[a] \times 2$，
  
  $dp[b] \times 3$，$dp[c] \times 5$ 的大小关系，若相等则将对应索引a，b，c加1；
  
  \[\left\{
  \begin{aligned}
  dp[a] \times 2 > dp[i-1] \geq dp[a-1] \times 2\\
  dp[b] \times 3 > dp[i-1] \geq dp[b-1] \times 3\\
  dp[c] \times 3 > dp[i-1] \geq dp[c-1] \times 3
  \end{aligned}
  \right.
  \]
初始状态：$dp[0]=1$，即第一个丑数为1；
返回值：$dp[n-1]$，即返回第n个丑数。

class Solution{
public:
    int nthUglyNumber(int n){
        int a = 0, b = 0, c = 0;
        int dp[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
};

方法三：优先队列(小顶堆)

利用优先队列有自动排序的功能
每次取出队头元素，存入队头元素*2、队头元素*3、队头元素*5
但注意，像 12 这个元素，可由 4 乘 3 得到，也可由 6 乘 2 得到，所以要注意去重

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue <double,vector<double>,greater<double> > q; // 一定要有空格，不然成了右移运算符
        double answer=1;
        for (int i=1;i<n;++i)
        {
            q.push(answer*2);
            q.push(answer*3);
            q.push(answer*5);
            answer=q.top();
            q.pop();
            while (!q.empty() && answer==q.top())
                q.pop();
        }
        return answer;
    }
};

进一步采用set来识别有无重复
class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue <double,vector<double>,greater<double> > q;
        set<int> s;
        s.insert(1);
        vector<int> mask({2,3,5});
        double answer=1;
        for (int i=1;i<n;++i)
        {
            for (int &j:mask)
                if (s.count(answer*j)==0)
                {
                    q.push(answer*j);
                    s.insert(answer*j);
                }
            answer=q.top();
            q.pop();
        }
        return answer;
    }
};

剑指Offer 63 – 股票的最大利润

动态规划解析：

状态定义：设动态规划列表$dp$，$dp[i]$代表以$prices[i]$为结尾的子数组的最大利润（以下简称为前$i$日的最大利润）。
转移方程：由于题目限定“买卖该股票一次”，因此前i日最大利润$dp[i]$等于前$i – 1$日最大利润$dp[i- 1]$和第$i$日卖出的最大利润中的最大值。

\[dp[i] = max(dp[i-1],prices[i]-min(prices[0:i]))
\]
初始状态：$dp[0] = 0$，即首日利润为0；
返回值：$dp[n – 1]$，其中$n$为$dp$列表长度。

时间复杂度降低：

前i日的最低价格$min(prices[0:i])$时间复杂度为$O(i)$。而在遍历$prices$时，可以借助一个变量（记为成本$cost$）每日更新最低价格。优化后的转移方程为：

\[dp[i]=max(dp[i-1],prices[i]-min(cost,prices[i]))
\]

空间复杂度降低：

由于$dp[i]$只与$dp[i-1], prices[i], cost$相关，因此可使用一个变量（记为利润$profit$）代替$dp$列表。优化后的转移方程为：

\[profit = max(profit, prices[i] – min(cost, prices[i]))
\]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cost = INT_MAX, profit = 0;
        for(int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }
};

搜索与回溯算法

剑指Offer 12 – 矩阵中的路径

典型的矩阵搜索问题，可使用深度优先搜索(DFS)+剪枝。

深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性。DFS通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。

DFS解析：

递归参数：当前元素在矩阵board中的行列索引i和j，当前目标字符在word中的索引k。
终止条件：
1. 返回false：（1）行或列索引越界；or（2）当前矩阵元素与目标字符不同；or（3）当前矩阵元素已访问过（（3）可合并至（2））。
2. 返回true：k = len(word) - 1，即字符串word已全部匹配。
递推工作：
1. 标记当前矩阵元素：将board[i][j]修改为空字符“，代表此元素已访问过，防止之后搜索时重复访问。
2. 搜索下一单元格：朝当前元素的上、下、左、右四个方向开启下层递归，使用或连接（代表只需找到一条可行路径就直接返回，不再做后续DFS），并记录结果至res。
3. 还原当前矩阵元素：将board[i][j]元素还原至初始值，即word[k]。
返回值：返回布尔量res，代表是否搜索到目标字符串。

使用空字符（Python: ” , Java/C++: ‘\0’ ）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。

复杂度分析：

M,N 分别为矩阵行列大小， KK 为字符串 word 长度。

时间复杂度$O(3^{K}MN)$：最差情况下，需要遍历矩阵中长度为K字符串的所有方案，时间复杂度为$O(3^{K})$;矩阵中共有MN个起点，时间复杂度为$O(MN)$。
- 方案数计算：设字符串长度为K，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下3种选择，因此方案数的复杂度为$O(3^{K})$。
空间复杂度$O(K)$：搜索过程中的递归深度不超过K，因此系统因函数调用累计使用的栈空间占用$O(K)$（因为函数返回后，系统调用的栈空间会释放）。最坏情况下K = MN，递归深度为MN，此时系统栈使用O(MN)的额外空间。

//C++:
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
private:
    int rows, cols;
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.size() - 1) return true;
        board[i][j] = '\0';
        bool 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];
        return res;
    }
};

#python:
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

剑指Offer 13 – 机器人的运动范围

解题思路：

本题与矩阵中的路径类似，时典型的搜索&回溯问题。在介绍回溯算法前，为提升计算效率，需要先了解两项前置工作：数位之和计算、可达解分析。——自行百度

方法一：深度优先遍历DFS

深度优先搜索：可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为可行性剪枝。

算法解析：

递归参数：当前元素在矩阵中的行列索引$i$和$j$，两者的数位和$si$，$sj$。
终止条件：当(1)行列索引越界 or (2)数位和超过目标值k or (3)当前元素已访问过时，返回0，代表不计入可达解。
递推工作：
1. 标记当前单元格：将索引(i, j)存入Set visited中，代表此单元格已被访问过。
2. 搜索下一单元格：计算当前元素的下、右两个方向元素的数位和，并开启下层递归。
回溯返回值：返回1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

复杂度分析：

设矩阵行列数分别为M, N。

时间复杂度O(MN)：最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为O(MN)。

空间复杂度O(MN)：最差情况下，Set visited内存储矩阵所有单元格的索引，使用O(MN)的额外空间。

//C++
class Solution{
public:
    int movingCount(int m, int n, int k){
        vector<vector<bool>> visited(m, vector<bool>(n, 0)); // MN矩阵初始化，每个元素默认为0
        return dfs(0, 0, 0, 0, visited, m, n, k);
    }
private:
    int dfs(int i, int j, int si, int sj, vector<vector<bool>>& visited, int m, int n, int k){
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj, visited, m, n, k) +
                   dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8, visited, m, n, k);
    }
};

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i, j, si, sj):
            if i >= m or j >= n or k < si + sj or (i, j) in visited: return 0
            visited.add((i,j))
            return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)

        visited = set()
        return dfs(0, 0, 0, 0)

方法二：广度优先遍历BFS

BFS/DFS ： 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现： 通常利用队列实现广度优先遍历。

算法解析：

初始化： 将机器人初始点 (0, 0)加入队列 queue ；
迭代终止条件： queue 为空。代表已遍历完所有可达解；
迭代工作：
1. 单元格出队： 将队首单元格的索引、数位和弹出，作为当前搜索单元格。
2. 判断是否跳过： 若 ① 行列索引越界或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，执行 continue 。
3. 标记当前单元格 ：将单元格索引 (i, j) 存入 Set visited 中，代表此单元格 已被访问过 。
4. 单元格入队： 将当前元素的 下方、右方 单元格的 索引、数位和 加入 queue 。
返回值： Set visited 的长度 len(visited) ，即可达解的数量。

复杂度分析：与方法一一致。

// C++
class Solution{
public:
    int movingCount(int m, int n, int k){
        vector<vector<bool>> visited(m, vector<bool>(n, 0));
        int res = 0;	// 统计可达解数量
        queue<vector<int>> que;
        que.push({ 0, 0, 0, 0}); // 初始点(0, 0)的索引和数位和
        while(que.size() > 0){
            vector<int> x = que.front();
            que.pop();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res++;
            que.push({ i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj});
            que.push({i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8});
        }
        return res;
    }
};

#python
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        queue, visited, = [(0, 0, 0, 0)], set()
        while queue:
            i, j, si, sj = queue.pop(0)
            if i >= m or j >= n or k < si + sj or (i, j) in visited: continue
            visited.add((i,j))
            queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))
            queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))
        return len(visited)

本文链接：https://www.cnblogs.com/monsterLiu/p/14239427.html

LeetCode刷题笔记

参考链接：图解算法数据结构

动态规划

剑指Offer 58 – Ⅱ.左旋转字符串

剑指Offer 67 – 把字符串转换成整数

剑指Offer 10-Ⅰ. 斐波那契数列

剑指Offer 10- Ⅱ.青蛙跳台阶问题

剑指Offer 42 – 连续子数组的最大和

剑指Offer 46 – 把数字翻译成字符串

剑指Offer 47 – 礼物的最大价值

剑指Offer 48 – 最长不含重复字符子串

剑指Offer 49 – 丑数

剑指Offer 63 – 股票的最大利润

搜索与回溯算法

剑指Offer 12 – 矩阵中的路径

剑指Offer 13 – 机器人的运动范围

LeetCode刷题笔记的更多相关文章

随机推荐

热门专题

目录导航