-
动态规划：路径和子数组问题（C++）
路径问题
1.不同路径（中等）
链接：不同路径
-
题目描述
-
做题步骤
-
状态表示
尝试定义状态表示为到达[m, n]位置的路径数。
-
状态转移方程
通过上述分析，可知状态转移方程为：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。 -
填表顺序
保证填当前状态时，所需状态已经计算过，从起点出发，填表顺序为从上往下，每一行从左往右。 -
返回值
根据状态表示，返回的应该是dp[m][n]，即到达终点的路径数。
- 代码实现
class Solution { public: int uniquePaths(int m, int n) { //dp[i][j]表示到达该位置的路径 vector<vector<int>> dp(m+1, vector<int>(n+1,0)); dp[0][1] = 1; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n;j++) { dp[i][j] = dp[i][j - 1] + dp[i - 1][j]; } } return dp[m][n]; //时间复杂度：O(N) //空间复杂度：O(N^M) } }; //滚动数组优化 // class Solution { // public: // int uniquePaths(int m, int n) // { // vectordp(n + 1); // dp[1] = 1; // for(int i = 1; i <= m; i++) // { // for(int j = 1; j <= n;j++) // { // dp[j] += dp[j-1]; // } // } // return dp[n]; // } // };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
2.不同路径II（中等）
链接：不同路径II
-
题目描述
-
做题步骤
-
状态表示
这个题和第一题唯一不同就是加入了障碍物（1），我们只需要进行判断，如果该位置是障碍物就填0，否则依据转移方程填表。 -
状态转移方程
通过上述分析，可知状态转移方程为：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。 -
初始化
和第一题一样，多开一圈，dp[0][1]或dp[1][0]初始为1。 -
填表顺序
和第一题一样，填表顺序为从上往下，每一行从左往右。 -
返回值
根据状态表示，返回的应该是dp[m][n]，即到达终点的路径数。
- 代码实现
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); //dp[i][j]：到达该位置的路径数 vector<vector<int>> dp(m + 1,vector<int>(n + 1)); dp[0][1] = 1; //dp[1][0] = 1; for(int i = 1; i < m + 1; i++) { for(int j = 1; j < n + 1; j++) { //多开了一圈，注意下标映射 if(obstacleGrid[i - 1][j - 1] == 0) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } //vector默认初始0，障碍物对应位置无需处理 } } return dp[m][n]; //时间复杂度：O(N) //空间复杂度：O(N^2) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
3.下降路径最⼩和（中等）
链接：下降路径最⼩和
-
题目描述
-
做题步骤
-
状态表示
-
状态转移方程
由前面的分析可知，状态转移方程为：
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]}) + matrix[i - 1][j - 1](本身的值） -
初始化
先全部初始化为极大值，然后第一行初始化为0。 -
填表顺序
从上往下，每一行从左往右。 -
返回值
依据状态表示和题目要求，返回最后一行的最小值即可。
- 代码实现
class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { //dp[i][j]表示到这个位置最小路径和 int n = matrix.size(); vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX)); //初始化第一行 for(int j = 0; j < n + 2; j++) { dp[0][j] = 0; } for(int i = 1; i < n + 1; i++) { for(int j = 1; j < n + 1; j++) { dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]}) + matrix[i - 1][j - 1]; } } //再遍历一次找最小 int ret = dp[n][0]; for(auto e : dp[n]) { ret = min(ret, e); } return ret; //时间复杂度：O(N) //空间复杂度：O(N^2) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
4.地下城游戏（困难）
链接：地下城游戏
- 题目描述
- 做题步骤
- 状态表示
-
状态转移方程
由前面的分析可知，状态转移方程为：
dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j](自身出去的消耗） -
初始化
先将所有值初始化为极大值，dp[m][n - 1] = dp[m - 1][n] = 1。 -
填表顺序
从下往上，每一行从右向左。 -
返回值
由状态表示可知，返回值为dp[0][0]（即[0,0]位置到终点需要的最小生命）
- 代码实现
// 看点位的状态表示 //从左上到右下：点位表示到这里需要的最小健康点数，点位并不是只受到左边和上面的影响，也要受后面点位的影响（后面点位可能使自己死亡），这种状态表示肯定不能 //从右下到左上：点位表示从这里开始到终点所需要的最小健康点数。 class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { //dp[i][j]表示以这个位置为起点到终点所需要的最小健康点数 int m = dungeon.size(); int n = dungeon[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); //初始化 dp[m][n - 1] = dp[m - 1][n] = 1; for(int i = m - 1; i >= 0; i--) { for(int j = n - 1; j >=0; j--) { dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]; //如果dp[i][j]为负数，说明这个位置是奶 //直接奶满了，从这里到终点所要的点数1就足够（小于1就死了） dp[i][j] = max(dp[i][j], 1); } } return dp[0][0]; //时间复杂度：O(N) //空间复杂度：O(N^2) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
子数组问题
1.最大子数组和（中等）
链接：最大子数组和
- 题目描述
- 做题步骤
-
状态表示
这个题目我们可以定义状态表示为以i位置为结尾的子数组的最大和。
因为子数组必须是连续的，所以i位置有两种选择：
(1)接在以i - 1位置为结尾的子数组后面，即dp[i] = dp[i - 1] + 自身点数
(2)不接在别人后面(可能dp[i - 1]是负值)，就自己一个，即dp[i] = 自身点数
从两种选择中选择最大的一种，即dp[i] = max(dp[i -1] + 自身点数, 自身点数) -
状态转移方程
由前面的分析可知，状态转移方程为：
dp[i] = max(dp[i -1] + 自身点数, 自身点数) -
初始化
无需初始化。 -
填表顺序
从左往右。 -
返回值
无法直接确定最大子数组的结尾位置，可以定义变量ret，一边dp一边更新最大值。
- 代码实现
class Solution { public: int maxSubArray(vector<int>& nums) { //在原数组上面dp就行 //dp[i]：以i位置为结尾的最大子数组和 int ret = nums[0]; for(int i = 1; i < nums.size(); i++) { nums[i] = max(nums[i - 1] + nums[i], nums[i]); //遍历的过程顺便找最大 ret = max(ret, nums[i]); } return ret; //时间复杂度：O(N) //空间复杂度：O(1) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
2.环形子数组的最大和（中等）
链接：环形子数组的最大和
-
题目描述
-
做题步骤
-
状态表示
这个题目和前一题类似，我们依然可以定义状态表示为以i位置为结尾的最大子数组和。
对于环形问题，最常见的做法就是分情况讨论，分解问题：
(1)最大子数组不成环，比如[-1,2,3,-1]，这个情况做法和前一道题一样。
(2)最大子数组成环，比如[2,1,-3,-2,1]，最大子数组成环情况，数组中剩余的连续部分一定是最小子数组。
子数组是连续的，环形可以理解为左右扩张，所有有利于自己的连续部分一定会被吞并，剩下的一定是最小子数组和。
但数组的总和是不变的，我们只需要用总和减去最小子数组和即可得到成环情况的最大和。 -
状态转移方程
不成环最大子数组和用f表来记录，最小子数组和用g表来记录
状态转移方程为：
f[i] = max(nums[i], f[i - 1] + nums[i])
g[i] = min(nums[i], g[i - 1] + nums[i]) -
初始化
为避免填表越界，处理第一个位置，f[0] = g[0] = nums[0] -
填表顺序
都是从左往右。 -
返回值
无法直接确定最大(小)子数组的结尾，所以一边dp一边记录最大(小)值。
(1)f表最大值->fmax
(2)g表最小值->gmin
(3)总和->sum
还有一种特殊情况就是环形数组长度为0(数组中全是负数)，这个时候最大值为fmax而不是0，所以返回值为sum == gmin ? fmax : max(fmax, sum - gmin)。
- 代码实现
class Solution { public: int maxSubarraySumCircular(vector<int>& nums) { int n = nums.size(); //一种情况是不需要环形，区间就在数组中 //第二种情况是需要环形，数组总大小恒定 //非目标区间是连续并且在数组中的，所以最大 = 总 - 非目标区间 //比如 5 -3 5，第一种得到5，第二种为 7(总) - (-3) = 10 int sum = nums[0]; //f[i]：以i位置为结尾的不成环最大子数组和 vector<int> f(n); //g[i]：以i位置为结尾的最小子数组和 auto g = f; f[0] = g[0] = nums[0]; int fmax = nums[0]; int gmin = nums[0]; for(int i = 1; i < n; i++) { f[i] = max(nums[i], f[i - 1] + nums[i]); g[i] = min(nums[i], g[i - 1] + nums[i]); fmax = max(fmax, f[i]); gmin = min(gmin, g[i]); sum += nums[i]; } //sum和gmin相同说明里面全是负数，这个时候fmax才是最大，不能为0 return sum == gmin ? fmax : max(fmax, sum - gmin); //时间复杂度：O(N) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
3.乘积最大子数组（中等）
链接：乘积最大子数组
-
题目描述
-
做题步骤
这个题目子数组长度最小可以为1，其实所有子数组默认乘了一个1。
-
状态表示
依据前面最大子数组和的经验，我们可以定义状态为以i位置为结尾的最大乘积。
但只有这一个状态表示是不够的，负数的加入对乘积影响是巨大的，比如[1,2,3,-1,-2,1]，前面按最大和的做法来还没问题，但遇到多个负数就会出问题，这里[1,2,3,-1,-2]可以得到最大乘积12，如果按照最大和的做法只能得到6。
出现上面情况的原因在于负数的出现使得原来的最大乘积变成了最小乘积，但如果保存最小乘积，当遇到负数时最小乘积就可以变成最大乘积。
综上所述，我们需要同时记录最大和最小乘积，其中最大用f表记录，最小用g表记录。
(1)x = nums[i]（当前位置的值）
(2)y = f[i - 1]（前一个位置的最大乘积）
(3)z = g[i - 1]（前一个位置的最小乘积） -
状态转移方程
一共就三种情况：
(1)x：不接在别人后面，子数组长度为1。
(2)x * y：接在前一个位置最大乘积子数组后面，有可能得到最大(小)乘积。
(3)y * z：接在前一个位置最小乘积子数组后面，有可能得到最大(小)乘积。
由此可知状态转移方程为：
f[i] = max( {x, x * y, x * z} )
g[i] = min( {x, x * y, x * z} ) -
初始化
当前位置的f、g更新需要前一个位置，第一个位置的最大(小)乘积就是值本身，为了避免第一个位置越界，可以在前面多开一个空间并初始化为1，即f[0] = g[0] = 1，这样不会影响第一个位置。 -
填表顺序
从左往右。 -
返回值
无法直接确定最大子数组的结尾位置，一边dp一边更新最大值。
- 代码实现
class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(); //dp[i]：以i为结尾的最大乘积 //f[i]表示最大乘积，g[i]表示最小乘积 vector<int> f(n + 1); auto g = f; f[0] = g[0] = 1; //ret变量记录最大乘积 int ret = INT_MIN; for(int i = 1; i <= n; i++) { int x = nums[i - 1];//现在 int y = f[i - 1]; //上个位置的最大乘积 int z = g[i - 1]; //上个位置的最小乘积 //如果遇到负数的情况，原本最大乘积可能会变成最小，原本最小可能会变成最大 f[i] = max({x, x * y, x * z}); g[i] = min({x, x * y, x * z}); ret = max(ret, f[i]); } return ret; //时间复杂度：O(N) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
4.乘积为正数的最长子数组（中等）
链接：乘积为正数的最长子数组
-
题目描述
-
做题步骤
-
状态表示
这个题目和上一道类似，要考虑负数的加入，因此只有一个状态表示是不够的。
(1)f表：以i位置为结尾，乘积为正数的最长子数组长度。
(2)g表：以i位置为结尾，乘积为负数的最长子数组长度。 -
状态转移方程
设当前位置的值为x
(1)x为负数时，接在前一个位置的后面，原本乘积正数的子数组会变成负数，乘积负数的子数组会变成正数。
即f[i] = g[i - 1] + 1 和 g[i] = f[i - 1] + 1,但前一个位置结尾的子数组乘积可能无法出现负数（前面都是正数），即g[i - 1] == 0，这个时候f[i]应该也为0。
故状态转移方程为：
f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1
g[i] = f[i - 1] + 1
(2)当x为正数时，接在前一个位置的后面，原本乘积正数的子数组还是正数，乘积负数的子数组还是负数。
（也要考虑前一个位置乘积负数不存在的情况）
故状态转移方程为：
f[i] = f[i - 1] + 1
g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1 -
初始化
当前位置的f、g更新需要前一个位置，第一个位置为负数，g[i]为1，f[i]为0，值为正数则相反。为了避免第一个位置越界，可以在前面多开一个空间并初始化为0，即f[0] = g[0] = 0，这样不会影响第一个位置。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序很明显是从左往右 -
返回值
无法直接确定乘积为正数的最长子数组结尾位置，定义变量ret，一边dp一边更新最大值。
- 代码实现
class Solution { public: int getMaxLen(vector<int>& nums) { //dp[i] 表示这个位置乘积为负数/正数时的最大长度 int n = nums.size(); vector<int> f(n + 1); // 正数 auto g = f;//负数 int ret = -1; for(int i = 1; i < n + 1; i++) { //这个数是正数 if(nums[i - 1] > 0) { f[i] = f[i - 1] + 1; //要考虑前一个位置乘积负数不存在的情况 g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; } else if(nums[i - 1] < 0) //负数 { f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; g[i] = f[i - 1] + 1; } //这个数为0，两个状态都不存在，不用处理（本来就是0） ret = max(ret, f[i]); } return ret; //时间复杂度：O(N) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
5.等差数列划分（中等）
链接：等差数列划分
- 题目描述
- 做题步骤
-
状态表示
依据前面的经验，我们可以定义状态表示为以i位置为结尾的等差数组个数。 -
状态转移方程
以[1,2,3,4]为例子进行分析：
(1)像1、2这样的位置为结尾数组长度不足3，是一定不能构成等差数组的，即dp[i] = 0。
(2)像4这样的位置，先看能不能和前面两个元素构成等差数组（满足nums[i] + nums[i - 2] == 2* nums[i - 1]），如果可以的话那4也一定可以接在以3为结尾的等差数组后面，即dp[i] = dp[i - 1] + 1。
综上所述，状态转移方程为：
可以和前两个数构成等差数组：dp[i] = dp[i - 1] + 1
不能和前两个数构造等差数组：dp[i] = 0 -
初始化
无需初始化。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序很明显是从左往右 -
返回值
题目要求返回所有等差子数组，定义变量sum，一边dp一边累加。
- 代码实现
class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { // 1 2 3 4 5 //3位置1种 4位置除了拼在3位置可能的后面，还可以抢2 3 来组成 //4位置2种 5位置除了拼在4位置可能的后面，还可以抢3 4 来组成 //………………对更长的序列也是如此 int n = nums.size(); //dp[i]：以i位置为结尾的等差数组个数 vector<int> dp(n); int sum = 0; for(int i = 2; i < n; i++) { //等差数列的性质：num[i] + nums[i - 2] == 2 * num[i - 1] if(nums[i] + nums[i - 2] == 2* nums[i - 1]) { dp[i] = dp[i - 1] + 1; } //不满足等差数组为0，vector默认给0，不用处理 sum += dp[i]; } return sum; //时间复杂度：O(N) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
6.最长湍流子数组（中等）
链接：最长湍流子数组
-
题目描述
-
做题步骤
-
状态表示
依据前面的经验，我们定义状态表示为以i位置为结尾的最长湍流子数组长度。
但只知道i-1位置的最大长度是无法推导出i位置的最大长度的，因为不知道前一个最长湍流子数组结束是处于上升状态(最后的比较符号为’<‘)还是下降状态(最后的比较符号为’>')
因此可以对状态进行细分：
（1）f[i]表示以i位置为结尾并处于上升状态(最后的比较符号为’<')的最长湍流子数组长度
（2）g[i]表示以i位置为结尾并处于下降状态(最后的比较符号为’>')的最长湍流子数组长度 -
状态转移方程
因为湍流子数组比较符号必须在每个相邻元素之间翻转，所以状态转移方程与当前的比较符号相关。
（1）arr[i-1] < arr[i]，现在处于上升状态，需要前置状态处于下降状态的最长湍流子数组长度，即f[i] = g[i - 1] + 1。
（2）arr[i-1] > arr[i]，现在处于下降状态，需要前置状态处于上升状态的最长湍流子数组长度，即g[i] = f[i - 1] + 1。
（3）arr[i-1] = arr[i]，不能和前面组合，只能自己重新开始，即f[i] = g[i] = 1。 -
初始化
推导当前状态需要前一个状态，像第一个位置不能跟在别人后面，两个状态的长度都为1，f[0] = g[0] = 1。因为arr[i-1] = arr[i]时f[i] = g[i] = 1，所以干脆一开始全都初始化为1，就不用单独处理arr[i-1] = arr[i]的情况。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序很明显是从左往右 -
返回值
无法直接确定最长湍流数组的结尾位置以及结尾是处于上升还是下降状态，所以定义变量ret，一边dp一边更新最大值。
- 代码实现
class Solution { public: int maxTurbulenceSize(vector<int>& arr) { int n = arr.size(); //dp[i]表示以i位置为结尾并且处于上升(下降)状态的最长湍流子数组的长度 vector<int> f(n, 1); //f表示处于上升(<)状态 //初始化为1，可以把'=='的情况直接处理了 auto g = f; //g表示处于下降(>)状态 int ret = 1; for(int i = 1; i < n; i++) { if(arr[i-1] < arr[i]) f[i] = g[i - 1] + 1; else if(arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1; ret = max( {ret, f[i], g[i]} ); } return ret; //时间复杂度：O(N) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
7.单词拆分（中等）
链接：单词拆分
- 题目描述
- 做题步骤
-
状态表示
依据前面的经验，我们可以定义状态表示为以i位置为结尾的字符串能否由字典中的单词拼出。 -
状态转移方程
以s = “leetcode”, wordDict = [“leet”, “code”]为例进行分析：
（1）先看字符’t’位置（下标3位置），以这个位置为结尾的字符串如果能由字典中的单词拼出，一共有下面几种可能：
①"lee"可以由字典中的单词拼出(即dp[2] = true)，"t"也可以由字典中的单词拼出。
②"le"可以由字典中的单词拼出(即dp[1] = true)，"et"也可以由字典中的单词拼出。
③"l"可以由单词中的单词拼出(即dp[0] = true)，"eet"也可以由字典中的单词拼出。
④再往前就没有了，"leet"可以由字典中的单词拼出。
其它位置的分析也和上述一致，将当前字符串分成[0, j - 1]区间和[j, i]区间，从 0 ~ i 枚举 j ，只要 dp[j - 1] = true并且后面部分的子串 s.substr(j, i - j + 1) 能够在字典中找到，那么 dp[i] = true 。 -
初始化
处理④这样的情况，可以多加一个虚拟节点并初始化true(dp[0] = true)，可以理解为空串能在字典中找到。同时为了方便处理下标的映射关系，我们可以在字符串s前面加一个占位符(s = ’ ’ + s)，这样就不用考虑下标的映射了。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序很明显是从左往右 -
返回值
根据状态表示，假设字符串长度为n，返回的应该是dp[n] -
优化
为了方便查询字符串是否在字典中，可以把字典的单词存储到哈希表中。
- 代码实现
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { // 将字典⾥⾯的单词存在哈希表⾥⾯ unordered_set<string> hash; for(auto& s : wordDict) hash.insert(s); int n = s.size(); vector<bool> dp(n + 1); dp[0] = true; // 保证后续填表是正确的 s = ' ' + s; // 使原始字符串的下标统⼀ for(int i = 1; i <= n; i++) { for(int j = i; j >= 1; j--) //最后⼀个单词的起始位置 { if(dp[j - 1] && hash.count(s.substr(j, i - j + 1))) { dp[i] = true; break; //已经确定为真就可以跳出这一层循环了 } } } return dp[n]; //时间复杂度：O(N^2) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
8.环绕字符串中唯⼀的子字符串（中等）
- 题目描述
- 做题步骤
-
状态表示
依据前面的经验，我们定义状态表示为以i位置为结尾并且在base中出现的子字符串个数。 -
状态转移方程
这个题目中的base数组是按照abcd……zabcd这样的顺序来的，要注意base成环。
以i位置为结尾并在base中出现的子字符串有下面三种可能：
(1)不拼在别人后面，就单独自己一个，该字符串一定会在base中出现。
(2)拼在别人后面，并且满足s[i] = s[i - 1] + 1(即满足abcd递增)
(3)拼在别人后面，并且满足s[i] == ‘a’ && s[i - 1] == ‘z’(刚好成环)
综上所述，状态转移方程为：
①满足(2)(3)中任意一个，dp[i] = dp[i - 1] + 1（这个1是自己,dp[i - 1]是拼在别人后面)
②不满足(2)(3)，dp[i] = 1 -
初始化
每个位置最少也有自己单独一个的情况，所以全都初始化为1。 -
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序很明显是从左往右 -
返回值
这个题目最需要注意的就是对dp表数据的处理，因为dp表中可能有大量重复的数据，比如"abcdcd"中’d’字符出现了两次，"cd"和"d"这两个字符串在dp表中是多次记录了的，我们需要对dp表数据进行去重。
每个字符都对应了固定的ASCLL码，因此可以可以创建⼀个大小为 26 的数组，遍历dp表，对于出现多次的字符，只需保留以该字符为结尾的最大dp值。
去重完成后再进行累加就可以得到结果。
- 代码实现
class Solution { public: int findSubstringInWraproundString(string s) { //base是abcd……连续的 //s[i]表示现在位置 //所以字串要存在要么s[i] == s[i - 1] + 1 //要么(s[i - 1] == 'z' && a[i]=='a') int n = s.size(); //dp[i]：以i位置为结尾并且在base中出现的子字符串数 vector<int> dp(n, 1); for(int i = 1; i < n; i++) { if(s[i] == s[i-1] + 1 || (s[i-1] == 'z' && s[i] == 'a')) { dp[i] = dp[i - 1] + 1; // 这个1是自己 } } int hash[26] = {0}; //遍历一次，统计对应字符最大的出现次数 //"abcdd"这样的后面那个d的1是无效的，要去掉 for(int i = 0; i < n; i++) { int index = s[i] - 'a'; hash[index] = max(hash[index], dp[i]); } //最后累加 int sum = 0; for(auto e : hash) { sum += e; } return sum; //时间复杂度：O(N) //空间复杂度：O(N) } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
-
-
相关阅读:
JavaMetaweblogClient,Metaweblog的java实现-从此上传博客实现全平台
结构体和共用体
oracle数据库插入数据时提示ORA-32795: 无法插入到“始终生成”身份列
MySQL如何快速获取binlog的开始时间和结束时间
CAN通信----基本原理
在springBoot中同时使用mysql和MongoDB
css实现滚动视差效果
Postman 工具发送请求的技巧与实践
Pinia基础知识
【Linux】应用层协议序列化和反序列化
- 原文地址：https://blog.csdn.net/2301_76269963/article/details/132651497
