【动态规划】子数组系列（二）

📝前言说明：

本专栏主要记录本人的动态规划算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接	开始学习
斐波那契数列模型	路径问题
简单多状态（一）	简单多状态（二）
子数组系列（一）	子数组系列（二）
子序列问题（一）	子序列问题（二）
回文串问题	两个数组dp问题（一）
两个数组的dp问题（二）	01背包问题
完全背包	二维的背包问题
其他

题目

413. 等差数列划分
- 个人解
978. 最长湍流子数组
- 个人解
- 优质解
139. 单词拆分
- 优质解
467. 环绕字符串中唯一的子字符串
- 个人解
- 优质解

413. 等差数列划分

题目链接：https://leetcode.cn/problems/arithmetic-slices/description/
在这里插入图片描述

个人解

思路：

不解释了，比较简单
要注意的是：对于一个以i结尾的子数组，如果以起始位置没变，改成以i + 1结尾，则这时候子数组总数 + 1

用时：12:00
屎山代码：

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 0);for(int i = 2; i < n; i++){if(dp[i - 1] > 0 && nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])dp[i] = dp[i - 1] + 1; // else if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])dp[i] = 1;}int ans = 0;for(auto x: dp)ans += x;return ans;}
};

时间复杂度：O(n)
空间复杂度：O(n)

978. 最长湍流子数组

题目链接：https://leetcode.cn/problems/longest-turbulent-subarray/description/
在这里插入图片描述

个人解

思路：

麻烦点在于，要处理==的情况

用时：25:00
屎山代码（写的太丑陋了）：

class Solution {
public:int maxTurbulenceSize(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);if(n == 1) return 1;if(n == 2 && nums[1]!= nums[0]) return n;if(n == 2 && nums[1] == nums[0]) return 1;// 初始化bool flag1 = nums[1] - nums[0] > 0? true : false;bool flag2 = nums[2] - nums[1] > 0? true : false;if(nums[2] == nums[1])dp[2] = 1;else if(nums[1] == nums[0])dp[2] = 2;else dp[2] = flag1 != flag2? 3: 2;int ans = dp[2];for(int i = 3; i < n ; i++){if(nums[i] == nums[i - 1])continue;dp[i] = 2;if(nums[i - 1] == nums[i - 2])continue;flag1 = nums[i] - nums[i - 1] > 0? true : false;flag2 = nums[i - 1] - nums[i - 2] > 0? true : false;if(flag1 == flag2)continue;if(dp[i - 1] > 2)dp[i] = dp[i - 1] + 1;elsedp[i] = 3;}for(auto x: dp)ans = max(ans, x);return ans;}
};

时间复杂度：O(n)
空间复杂度：O(n)

优质解

一个湍流子数组，以i位置为结尾可以分成两种状态> / <
利用多状态的状态转移来填dp

代码（力扣官方题解）：

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();vector<vector<int>> dp(n, vector<int>(2, 1));dp[0][0] = dp[0][1] = 1;for (int i = 1; i < n; i++) {if (arr[i - 1] > arr[i]) {dp[i][0] = dp[i - 1][1] + 1;} else if (arr[i - 1] < arr[i]) {dp[i][1] = dp[i - 1][0] + 1;}}int ret = 1;for (int i = 0; i < n; i++) {ret = max(ret, dp[i][0]);ret = max(ret, dp[i][1]);}return ret;}
};

139. 单词拆分

题目链接：https://leetcode.cn/problems/word-break/description/
在这里插入图片描述

优质解

思路：

dp[i]：s[0 , i]这部分子串，能否被字典中的单词拼接而成
- 我们怎么利用dp[i - 1]呢（前面的信息记录的是前面的字符串能否被字典中的单词拼接而成）
- 也就是说：我们可以把[0, i]分成两份，[j, i]记录最后一个单词（完整的）
- 如果[j, i]的单词在字典中，且[0, j - 1]这部分能被字典拼接而成，则i位置就行。巧妙用到的dp[j]
状态转移方程：j遍历[0, i]（即得到i结尾的最后一个单词）
- 如果，dp[j - 1] == true && s[j, i] in wordDict：true
- 否则，false
初始化：j会越界，添加一个哨兵节点。那此时字符串的下标和数组不对应了，所以我们可以在字符串前面也加多一个字符串。且dp[0] = true
填表顺序：从左往右
返回值：dp[n]

代码：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordDictset; // 转换成哈希表，后续使用find方便for(auto word:wordDict){wordDictset.insert(word);}s = '0' + s;int n = s.size();vector<bool> dp(n + 1, false);dp[0] = true;for(int i = 1; i <= n; i++){for(int j = i; j >= 1; j--) // 选择从后往前{if(dp[j - 1] && wordDictset.find(s.substr(j, i - j + 1)) != wordDictset.end()){dp[i] = true;break;}}}return dp[n];}
};

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

题目链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/
在这里插入图片描述

个人解

思路：

dp[i]：以 i 结尾的子串是否在 base 中出现
状态转移：如果dp[i - 1] > 1 && (s[i] == s[i - 1] + 1 || s[i] == s[i - 1] - 25) // 回绕到 z
- 则 dp[i] = dp[i - 1] + 1
重复子串怎么处理呢？？？

优质解

思路：

对于这种子串问题，我们可以以最后一个位置为结尾，把子串的状态专业给区分出来，如：单独最后一个位置 / 前 i - 1的子串 + 最后一个位置
返回值是重难点
对于重复的子串，长的子串一定包含短的子串的所有子串
所以，我们可以遍历dp表，对于相同的字符的dp值，只添加大的

代码：

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size();int dp_max[26] = {0}; // 记录每个字符出现的子串的最大值vector<int> dp(n, 1); // 单个字符，dp[i] == 1dp_max[s[0] - 'a'] = 1;for(int i = 1; i < n; i++){if(s[i] == s[i - 1] + 1 || s[i] == s[i - 1] - 25)dp[i] += dp[i - 1];dp_max[s[i] - 'a'] = max(dp_max[s[i] - 'a'], dp[i]); // 更新字符对应的子串最大值}int ans = 0;for(auto x: dp_max)ans += x;return ans;}
};