目录
①力扣53. 最大子数组和
难度 中等
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
}
};解析代码
以某个位置为结尾，结合题目，定义一个状态表示： dp[i] 表示：以 i 位置元素为结尾的所有子数组中和的最大和。dp[i] 的所有可能可以分为以下两种：
- 子数组的长度为 1 ：此时 dp[i] = nums[i] ;
- 子数组的长度大于 1 ：此时 dp[i] 应该等于 以 i - 1 做结尾的所有子数组中和的最大值再加上 nums[i] ，也就是 dp[i - 1] + nums[i] ;
由于我们要的是最大值，因此应该是两种情况下的最大值，因此可得转移方程： dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
int ret = dp[0] = nums[0];
for(int i = 1; i < n; ++i)
{
dp[i] = max(nums[i], dp[i-1] + nums[i]);
ret = max(ret, dp[i]);
}
return ret;
// int ret = nums[0]; // 直接在原数组操作的dp
// for (int i = 1; i < nums.size(); i++)
// {
// nums[i] += max(nums[i - 1], 0);
// ret = max(ret, nums[i]);
// }
// return ret;
}
};②力扣918. 环形子数组的最大和
难度 中等
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
输入：nums = [1,-2,3,-2] 输出：3 解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5] 输出：10 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：nums = [3,-2,2,-3] 输出：3 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示：
n == nums.length1 <= n <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
}
};解析代码
类似打家劫舍中把环形问题转换成线性问题的思路：
本题与最大大数组和的区别在于，考虑问题的时候不仅要分析数组内的连续区域，还要考虑数组首尾相连的一部分。结果的可能情况分为以下两种：
- 结果在数组的内部，包括整个数组。
- 结果在数组首尾相连的一部分上。
其中，对于第一种情况，我们仅需按照最大子数组和的求法就可以得到结果，记为 fmax 。
对于第⼆种情况，可以分析⼀下：
如果数组首尾相连的一部分是最大的数组和，那么数组中间就会空出来⼀部分，因为数组的总和 sum 是不变的，那么中间连续的一部分的和一定是最小的。因此，就可以得出⼀个结论，对于第⼆种情况的最大和，应该等于 sum - gmin ，其中gmin 表示数组内的最小子数组和。
两种情况下的最大值，就是我们要的结果。
但是，由于数组内有可能全部都是负数，第⼀种情况下的结果是数组内的最大值（是个负数），第⼆种情况下的 gmin == sum ，求的得结果就会是 0 。若直接求两者的最大值，就会是 0。但是实际的结果应该是数组内的最大值。对于这种情况，需要特殊判断⼀下。
由于最大子数组和的方法已经讲过，最小子数组和的求解过程，与其求法是一致的。这里用 f 数组表示最大和， g 数组表示最小和。
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);;
int fmax = f[0] = g[0] = nums[0], sum = nums[0], gmin = nums[0];
for(int i = 1; i < n; ++i)
{
sum += nums[i];
f[i] = max(nums[i], f[i-1] + nums[i]);
fmax = max(fmax, f[i]);
g[i] = min(nums[i], g[i-1] + nums[i]);
gmin = min(gmin, g[i]);
}
return sum == gmin ? fmax : max(fmax, sum - gmin);
}
};
③力扣152. 乘积最大子数组
难度 中等
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 10^4-10 <= nums[i] <= 10nums的任何前缀或后缀的乘积都 保证 是一个 32位 整数
class Solution {
public:
int maxProduct(vector<int>& nums) {
}
};解析代码
这道题与最大子数组和非常相似，可以效仿着定义⼀下状态表示以及状态转移：
- dp[i] 表⽰以 i 为结尾的所有子数组的最大乘积，
- dp[i] = max(nums[i], dp[i - 1] * nums[i]) ；
由于正负号的存在，很容易就可以得到，这样求 dp[i] 的值是不正确的。因为 dp[i -1] 的信息并不能让我们得到 dp[i] 的正确值。比如数组 [-2, 5, -2] ，用上述状态转移得到的 dp数组为 [-2, 5, -2] ，最大乘积为 5 。但是实际上的最大乘积应该是所有数相乘，结果为 20 。
究其原因，就是因为我们在求 dp[2] 的时候，因为 nums[2] 是⼀个负数，因此我们需要的是i - 1 位置结尾的最小的乘积 （-10） ，这样⼀个负数乘以最小值，才会得到真实的最大值。
因此不仅需要一个乘积最大值的 dp 表，还需一个乘积最小值的 dp 表。这里用f和g数组表示：
- f[i] 表示：以 i 结尾的所有子数组的最大乘积。
- g[i] 表示：以 i 结尾的所有子数组的最小乘积。
状态转移方程：
遍历每一个位置的时候，要同步更新两个 dp 数组的值。对于 f[i] ，也就是以 i 为结尾的所有字数组的最大乘积，对于所有子数组，可以分为下面三种形式：
- 子数组的长度为 1 ，也就是 nums[i] ；
- 子数组的长度大于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有子数组的最大乘积 f[i - 1]，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；
- 子数组的长度大于 1 ，但 nums[i] < 0 ，此时需要的是 i - 1 为结尾的所有子数组的最小乘积 g[i - 1]，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；
（如果 nums[i] = 0 ，所有子数组的乘积均为 0 ，三种情况其实都包含了）
对于num[i] 可以分类讨论，也可以直接取最大值，这里直接取最大值：
综上所述， f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i -1]) );
同理可得，g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1]));
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n); // 以i结尾的所有子数组的最大/小乘积
int ret = f[0] = g[0] = nums[0];
for(int i = 1; i < n; ++i)
{
f[i] = max(nums[i], max(nums[i] * f[i-1], nums[i] * g[i-1]));
g[i] = min(nums[i], min(nums[i] * f[i-1], nums[i] * g[i-1]));
ret = max(ret, f[i]);
}
return ret;
}
};
④力扣1567. 乘积为正数的最长子数组长度
难度 中等
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1：
输入：nums = [1,-2,-3,4] 输出：4 解释：数组本身乘积就是正数，值为 24 。
示例 2：
输入：nums = [0,1,-2,-3,-4] 输出：3 解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。 注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例 3：
输入：nums = [-1,-2,-3,0,1] 输出：2 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
提示：
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
class Solution {
public:
int getMaxLen(vector<int>& nums) {
}
};解析代码
状态表示： dp[i] 表示 所有以 i 结尾的子数组，乘积为正数的最长子数组的长度。
思考状态转移：对于 i 位置上的 nums[i] ，可以分三种情况讨论：
- 如果 nums[i] = 0 ，那么所有以 i 为结尾的子数组的乘积都不可能是正数，此时dp[i] = 0 ;
- 如果 nums[i] > 0 ，那么直接找到 dp[i - 1] 的值（这里再读⼀遍 dp[i -1] 代表的意义，并且考虑如果 dp[i - 1] 的值是 0 的话，影不影响结果），然后加一即可，此时 dp[i] = dp[i - 1] + 1 ;
- 如果 nums[i] < 0 ，这时候就麻烦了，因为在现有的条件下，你根本没办法得到此时的最长长度。因为乘法是存在负负得正的，单单靠一个 dp[i - 1] ，无法推导出 dp[i] 的值。
但是，如果知道以 i - 1 为结尾的所有子数组，乘积为负数的最长子数组的长度，g[i - 1]，那么此时的 dp[i] 是不是就等于 g[i - 1] + 1 ？ 通过分析可以得出，需要两个 dp 表，才能推导出最终的结果。不仅需要一个乘积为正数的最长子数组」，还需要一个乘积为负数的最长子数组。所以：
- f[i] 表示：以 i 结尾的所有子数组中，乘积为正数的最长子数组的长度。
- g[i] 表示：以 i 结尾的所有子数组中，乘积为负数的最长子数组的长度。
状态转移方程：
遍历每一个位置的时候，要同步更新两个 dp 数组的值。
所以对于 f[i] ，nums[i] < 0 时，此时要看 g[i - 1] 的值（这里再读⼀遍 g[i - 1] 代表的意义。因为负负得正，如果知道以 i - 1 为结尾的乘积为负数的最长子数组的长度，加上 1 即可），根据 g[i - 1] 的值，又要分两种情况：
- g[i - 1] = 0 ，说明以 i - 1 为结尾的乘积为负数的最长子数组是不存在的，又因为 nums[i] < 0，所以以 i 结尾的乘积为正数的最长子数组也是不存在的，此时 f[i] = 0 ；
- g[i - 1] != 0 ，说明以 i - 1 为结尾的乘积为负数的最长子数组是存在的，又因为 nums[i] < 0 ，所以以 i 结尾的乘积为正数的最长子数组就等于 g[i -1] + 1 ;
综上所述， nums[i] < 0 时， f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
对于 g[i] ，以 i 结尾的所有子数组中，乘积为负数的最长子数组的长度。也可以分为三种情况：
- nums[i] = 0 时，所有以 i 为结尾的⼦数组的乘积都不可能是负数，此时 g[i] =0 ;
- nums[i] < 0 时，那么直接找到 f[i - 1] 的值（这里再读⼀遍 f[i - 1] 代表的意义，并且考虑如果 f[i - 1] 的结值是 0 的话，影不影响结果），然后加⼀即可（因为正数 * 负数 = 负数），此时 g[i] = f[i - 1] + 1 ;
- nums[i] > 0 时，此时我们要看 g[i - 1] 的值（这里再读⼀遍 g[i - 1] 代表的意义。因为正数 * 负数 = 负数），根据 g[i - 1] 的值，又要分两种情况：
g[i - 1] = 0 ，说明以 i - 1 为结尾的乘积为负数的最长子数组是不存在的，又因为 nums[i] > 0 ，所以以 i 结尾的乘积为负数的最长子数组也是不存在的，此时 f[i] = 0 ;
g[i - 1] != 0 ，说明以 i - 1 为结尾的乘积为负数的最长子数组是存在的，又因为 nums[i] > 0 ，所以以 i 结尾的乘积为正数的最长子数组就等于 g[i -1] + 1 ;
综上所述， nums[i] > 0 时， g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
据此，从左往右，两个表⼀起填，最后返回 f 表的最大值。
- nums[i] = 0 ，f[i] = 0 ; g[i] = 0 ; // 不用处理，初始化就是0
- nums[i] < 0 时，f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; g[i] = f[i - 1] + 1 ;
- nums[i] > 0 时，f[i] = f[i - 1] + 1 ; g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);
// 以i结尾的所有子数组中，乘积为正/负数的最长子数组的长度。
int ret = INT_MIN;
if(nums[0] < 0)
g[0] = 1, ret = 0;
else if(nums[0] > 0)
f[0] = 1, ret = 1;
for(int i = 1; i < n; ++i)
{
if(nums[i] < 0)
{
g[i] = f[i-1] + 1;
f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
}
else if(nums[i] > 0)
{
f[i] = f[i-1] + 1;
g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
}
ret = max(ret, f[i]);
}
return ret;
}
};⑤力扣413. 等差数列划分
难度 中等
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
- 例如，
[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4] 输出：3 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1] 输出：0
提示：
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
}
};解析代码
首先等差数列至少是三个数，由于研究对象是一段连续的区间，如果我们状态表示定义成 [0, i] 区间内一共有多少等差数列，那么在分析 dp[i] 的状态转移时，会无从下手，因为我们不清楚前面那么多的等差数列都在什么位置。所以说，定义的状态表示必须让等差数列有迹可循，让状态转移的时候能找到大部队。因此，可以固定死等差数列的结尾，定义下面的状态表示：
dp[i] 表示必须以 i 位置的元素为结尾 的等差数列有多少种。
在做题之前需要了解⼀下等差数列的性质：如果 a b c 三个数成等差数列，这时候来了一个d，其中 b c d 也能构成⼀个等差数列，那么 a b c d 四个数也能够成等差序列。因为他们之间相邻两个元素之间的差值都是⼀样的。
有了这个理解，我们就可以转而分析我们 的状态转移方程了。 对于 dp[i] 位置的元素 nums[i]，会与前面的两个元素有下面两种情况：
- nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列：那么以 nums[i] 为结尾的等差数列就不存在，此时 dp[i] = 0 ;
- nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列：那么以 nums[i - 1] 为结尾的所有等差数列后面填上一个 nums[i] 也是一个等差数列，此时 dp[i] = dp[i - 1] 。但是，因为 nums[i - 2], nums[i - 1], nums[i] 三 者又能构成一个新的等差数列，因此要在之前的基础上再添上一个等差数列，于是 dp[i] = dp[i - 1] + 1 。
综上所述：状态转移方程为：
- 当： nums[i - 2] + nums[i] != 2 * nums[i - 1] 时， dp[i] = 0;
- 当： nums[i - 2] + nums[i] == 2 * nums[i - 1] 时， dp[i] = 1 + dp[i - 1];
也可以为 dp[i] = nums[i]-nums[i-1] == nums[i-1]-nums[i-2] ? dp[i-1]+1 : 0;
初始化就是dp[0] = dp[1] = 0; 从左往右填表，最后返回dp表的所有值。
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
// dp[i] 表示必须以 i 位置的元素为结尾 的等差数列有多少种
int n = nums.size();
vector<int> dp(n);
int ret = 0;
for(int i = 2; i < n; ++i)
{ // 前两个默认为0
dp[i] = nums[i]-nums[i-1] == nums[i-1]-nums[i-2] ? dp[i-1]+1 : 0;
ret += dp[i];
}
return ret;
}
};
⑥力扣978. 最长湍流子数组
难度 中等
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
- 若
i <= k < j：- 当
k为奇数时，A[k] > A[k+1]，且 - 当
k为偶数时，A[k] < A[k+1]；
- 当
- 或 若
i <= k < j：- 当
k为偶数时，A[k] > A[k+1]，且 - 当
k为奇数时，A[k] < A[k+1]。
- 当
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9] 输出：5 解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16] 输出：2
示例 3：
输入：arr = [100] 输出：1
提示：
1 <= arr.length <= 4 * 10^40 <= arr[i] <= 10^9
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
}
};解析代码
题意的湍流数组就是一上一下的意思，只有一个元素时长度为1。
先尝试定义状态表示为：dp[i] 表示以 i 位置为结尾的最长湍流数组的长度。
但是，问题来了，如果状态表示这样定义的话，以 i 位置为结尾的最长湍流数组的长度我们没法从之前的状态推导出来。因为我们不知道前一个最长湍流数组的结尾处是递增的，还是递减的。因此，我们需要状态表示能表示多一点的信息：要能让我们知道这一个最长湍流数组的结尾是递增的还是递减的。
因此需要两个 dp 表：
- f[i] 表示：以i位置元素为结尾的所有子数组中，最后呈现上升状态下的最⻓湍流数组的⻓度。
- g[i] 表示：以i位置元素为结尾的所有子数组中，最后呈现下降状态下的最⻓湍流数组的⻓度。
状态转移方程： 对于 i 位置的元素 arr[i] ，有下面两种情况：
- arr[i] > arr[i - 1] ：如果 i 位置的元素比 i - 1 位置的元素大，说明接下来 应该去找 i -1 位置结尾，并且 i - 1 位置元素比前⼀个元素小的序列，那就是 g[i - 1] 。更新 f[i] 位置的值： f[i] = g[i - 1] + 1 ;
- arr[i] < arr[i - 1] ：如果 i 位置的元素比 i - 1 位置的元素小，说明接下来 应该去找 i - 1 位置结尾，并且 i - 1 位置元素比前⼀个元素大的序列，那就是 f[i - 1] 。更新 g[i] 位置的值： g[i] = f[i - 1] + 1;
- arr[i] == arr[i - 1] ：不构成湍流数组。
初始化： 所有的元素单独都能构成一个湍流数组，因此可以将 dp 表内所有元素初始化为 1。 由于用到前面的状态，因此循环的时候从第二个位置开始。
从左往右，两个表一起填，最后返回两个dp表中的最大值即可。
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size(), ret = 1;
vector<int> f(n, 1), g(n, 1);
// 以i位置元素为结尾的所有子数组中，呈现上升/下降状态下的最⻓湍流数组的⻓度
for(int i = 1; i < n; ++i)
{
if(arr[i-1] > arr[i]) // 下降的
{
g[i] = f[i-1] + 1;
}
else if(arr[i-1] < arr[i]) // 上升的
{
f[i] = g[i-1] + 1;
}
ret = max(ret, max(f[i], g[i]));
}
return ret;
}
};⑦力扣139. 单词拆分
难度 中等
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
}
};解析代码
以某个位置为结尾，结合题目要求，定义一个状态表示：
dp[i] 表示： [0, i] 区间内的字符串，能否被字典中的单词拼接而成。
对于 dp[i] ，为了确定当前的字符串能否由字典里面的单词构成，根据最后一个单词的起始位 置 j ，我们可以将其分解为前后两部分：
- 前面一部分 [0, j - 1] 区间的字符串。
- 后面一部分 [j, i] 区间的字符串。
其中前面部分可以在 dp[j - 1] 中找到答案，后面部分的子串可以在字典里面找到。 因此得出一个结论：当从 0 ~ i 枚举 j 的时候，只要 dp[j - 1] = true 并且后面的子串 s.substr(j, i - j + 1) 能够在字典中找到，那么 dp[i] = true 。
初始化可以在最前面加上一个辅助结点，帮助我们初始化。使用辅助结点要注意两个点：
辅助结点里面的值要保证后续填表是正确的
下标的映射关系。 在本题中，最前面加上一个格子，并且让 dp[0] = true ，可以理解为空串能够拼接而成。 其中为了方便处理下标的映射关系，我们可以将字符串前面加上一个占位符 s = ' ' + s ，这样s的首字母下标就是1，就没有下标的映射关系的问题了，同时还能处理空串的情况。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> hash; // 优化1
for(auto& e :wordDict)
{
hash.insert(e);
}
int n = s.size();
vector<bool> dp(n+1, false);
dp[0] = true; // 辅助结点保证后序填表正确
// dp[i] 表示： [0, i] 区间内的字符串，能否被字典中的单词拼接而成
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; // 优化2
}
}
}
return dp[n];
}
};⑧力扣467. 环绕字符串中唯一的子字符串
难度 中等
定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
示例 1：
输入：s = "a" 输出：1 解释：字符串 s 的子字符串 "a" 在 base 中出现。
示例 2：
输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
示例 3：
输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
提示：
1 <= s.length <= 10^5- s 由小写英文字母组成
class Solution {
public:
int findSubstringInWraproundString(string s) {
}
};解析代码
状态表示和状态转移方程：
以某个位置为结尾，结合题目要求，定义一个状态表示： dp[i] 表示：以 i 位置的元素为结尾的所有子串里面，有多少个在 base 中出现过。
对于 dp[i] ，我们可以根据子串的长度划分为两类：
- 子串的长度等于 1 ：因为只有小写字母，所以此时这个字符一定会出现在 base 中，dp[i] = 1;
- 子串的长度大于 1 ：如果 i 位置的字符和 i - 1 位置上的字符组合后，出现在 base 中的话，那么 dp[i - 1] 里面的所有子串后面填上一个 s[i] 依旧在 base 中出现。因此 dp[i] = dp[i - 1] ;
上面两种情况加起来， dp[i] = 1 + dp[i - 1] ，1是长度等于1的，其中 dp[i - 1] 是否加上需要先做一下判断。
初始化、填表顺序、返回值：
依题意，将表里面的值都初始化为 1 。 从左往右填表，这里不能直接返回 dp 表里面的和，因为会有重复的结果。在返回之前，我们需要先去重。
相同字符结尾的 dp 值，我们仅需保留最大的即可，其余 dp 值对应的子串都可以在最大的里面找到，那么可以创建一个大小为 26 的数组，统计所有字符结尾的最大 dp 值。 最后返回数组中所有元素的和即可。
class Solution {
public:
int findSubstringInWraproundString(string s) {
// dp[i] 表示以i位置的元素为结尾的所有子串里面，有多少个在 base 中出现过
int n = s.size();
vector<int> dp(n, 1);
vector<int> hash(26, 0);
for(int i = 1; i < n; ++i)
{
if(s[i] - 1 == s[i-1] || (s[i - 1] == 'z' && s[i] == 'a'))
dp[i] = dp[i-1] + 1;
}
// 计算每一个字符结尾的最⻓连续⼦数组的⻓度
for(int i = 0; i < n; ++i)
hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
int sum = 0;
for(auto& e : hash)
sum += e;
return sum;
}
};本篇完。
下一篇是栈的相关OJ。
下下篇动态规划类型的是子序列dp系列的OJ。
