算法沉淀——动态规划之子数组、子串系列（下）（leetcode真题剖析）

算法沉淀——动态规划之子数组、子串系列

01.等差数列划分02.最长湍流子数组03.单词拆分04.环绕字符串中唯一的子字符串

01.等差数列划分

题目链接：https://leetcode.cn/problems/arithmetic-slices/

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[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

思路

1. 状态表达： 定义动态规划数组 dp，其中 dp[i] 表示必须以 i 位置的元素为结尾的等差数列有多少种。

2. 状态转移方程： 对于 dp[i] 位置的元素 nums[i]，分两种情况讨论：

如果 nums[i - 2] + nums[i] != 2 * nums[i - 1]，表示 nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列。此时，以 nums[i] 为结尾的等差数列不存在，令 dp[i] = 0。如果 nums[i - 2] + nums[i] == 2 * nums[i - 1]，表示 nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列。此时，以 nums[i - 1] 为结尾的所有等差数列后面填上一个 nums[i] 也是一个等差数列，令 dp[i] = 1 + dp[i - 1]。

3. 初始化： 由于需要用到前两个位置的元素，但前两个位置的元素又无法构成等差数列，因此初始化 dp[0] = dp[1] = 0。

4. 填表顺序： 从左往右遍历数组。

5. 返回值： 返回整个 dp 数组中的元素之和，即为所有等差数列的个数。

代码

class Solution {

public:

int numberOfArithmeticSlices(vector& nums) {

int n=nums.size();

vector dp(n);

int sum=0;

for(int i=2;i

dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;

sum+=dp[i];

}

return sum;

}

};

02.最长湍流子数组

题目链接：https://leetcode.cn/problems/longest-turbulent-subarray/

给定一个整数数组 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 * 1040 <= arr[i] <= 109

思路

1. 状态表达： 定义两个动态规划数组 f 和 g，其中 f[i] 表示以 i 位置元素为结尾的所有子数组中，最后呈现「上升状态」下的最长湍流数组的长度，而 g[i] 表示以 i 位置元素为结尾的所有子数组中，最后呈现「下降状态」下的最长湍流数组的长度。

2. 状态转移方程： 对于 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]，不构成湍流数组。

3. 初始化： 所有的元素「单独」都能构成一个湍流数组，因此可以将 f 和 g 数组内所有元素初始化为 1。由于用到前面的状态，因此循环的时候从第二个位置开始即可。

4. 填表顺序： 从左往右遍历数组，同时填充 f 和 g 两个数组。

5. 返回值： 返回两个数组中的最大值，即为湍流数组的最大长度。

代码

class Solution {

public:

int maxTurbulenceSize(vector& arr) {

int n=arr.size();

vector f(n,1);

vector g(n,1);

int ret=1;

for(int i=1;i

if(arr[i-1]

if(arr[i-1]>arr[i]) g[i]=f[i-1]+1;

ret=max(ret,max(g[i],f[i]));

}

return ret;

}

};

03.单词拆分

题目链接：https://leetcode.cn/problems/word-break/

给你一个字符串 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 中的所有字符串 互不相同

思路

1. 状态表达： 定义动态规划数组 dp，其中 dp[i] 表示 [0, i] 区间内的字符串，能否被字典中的单词拼接而成。

2. 状态转移方程： 对于 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。

3. 初始化： 在最前面加上一个「辅助结点」，帮助初始化。可以将字符串前面加上一个占位符 s = ' ' + s，这样就没有下标的映射关系的问题了，同时还能处理「空串」的情况。设置 dp[0] = true，表示空串能够拼接而成。

4. 填表顺序： 从左往右遍历字符串。

5. 返回值： 返回 dp[n] 位置的布尔值，表示整个字符串能否被字典中的单词拼接而成。

代码

class Solution {

public:

bool wordBreak(string s, vector& wordDict) {

unordered_set hash;

for(string& s:wordDict) hash.insert(s);

int n=s.size();

vector 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];

}

};

04.环绕字符串中唯一的子字符串

题目链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

定义字符串 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 <= 105s 由小写英文字母组成

思路

算法思路：

1. 状态表达： 定义动态规划数组 dp，其中 dp[i] 表示以 i 位置的元素为结尾的所有子串中，有多少个在 base 中出现过。

2. 状态转移方程： 对于 dp[i]，可以根据子串的「长度」划分为两类：子串的长度等于 1：此时这一个字符会出现在 base 中；子串的长度大于 1：如果 i 位置的字符和 i - 1 位置上的字符组合后，出现在 base 中的话，那么 dp[i - 1] 里面的所有子串后面填上一个 s[i] 依旧在 base 中出现。因此，dp[i] = dp[i - 1]。

综上， dp[i] = 1 + dp[i - 1]，其中 dp[i - 1] 是否加上需要先做一下判断。

3. 初始化： 可以根据「实际情况」，将表里面的值都初始化为 1。

4. 填表顺序： 从左往右遍历字符串。

5. 返回值： 不能直接返回 dp 表里面的和，因为会有重复的结果。在返回之前，需要先「去重」：相同字符结尾的 dp 值，仅需保留「最大」的即可，其余 dp 值对应的子串都可以在最大的里面找到；可以创建一个大小为 26 的数组，统计所有字符结尾的最大 dp 值。

代码

class Solution {

public:

int findSubstringInWraproundString(string s) {

int n=s.size();

vector dp(n,1);

for(int i=1;i

if(s[i]-1==s[i-1]||(s[i-1]=='z'&&s[i]=='a'))

dp[i]=dp[i-1]+1;

int hash[26]={0};

for(int i=0;i

hash[s[i]-'a']=max(hash[s[i]-'a'],dp[i]);

int sum=0;

for(int& x:hash) sum+=x;

return sum;

}

};

相关阅读

 您阅读本篇文章共花了：