算法沉淀——动态规划之子数组、子串系列
- 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 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 * 104
- 0 <= 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 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 <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s 和 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 <= 105
- s 由小写英文字母组成
思路
算法思路：
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(); vectordp(n,1); for(int i=1;i
- "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
- 若 i <= k < j ：
- 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。