《LeetCode 978 最长湍流子数组 || LeetCode 413 等差数列划分》-北京尧图网络

一、题目二、做题思路2.1 状态表示核心基础本题要求计算最长湍流子数组的长度。湍流要求相邻比较符号交替翻转因此需要区分最后一段比较方向。我们定义两个状态f[i]表示以arr[i]结尾且最后一段比较为“下降”即arr[i-1] arr[i]的湍流子数组的最大长度。g[i]表示以arr[i]结尾且最后一段比较为“上升”即arr[i-1] arr[i]的湍流子数组的最大长度。2.2 状态转移方程关键难点要延长湍流子数组当前比较必须与前一个比较方向相反若arr[i-1] arr[i]当前为下降则它应接在上一个上升状态之后因此f[i] g[i-1] 1。若arr[i-1] arr[i]当前为上升则它应接在上一个下降状态之后因此g[i] f[i-1] 1。若arr[i-1] arr[i]无法形成湍流两个状态均保持为1重新开始。该方程完整体现了比较符号交替翻转的要求。2.3 初始化边界防护每个元素至少可以单独构成一个长度为 1 的湍流子数组因此f[i]和g[i]均初始化为 1包括i0。2.4 填表顺序递推方向每个i状态仅依赖i-1的状态因此必须从左到右即i从 1 到n-1依次填充两个数组确保每个状态计算时其所有前置状态均已就绪。2.5 返回值目标映射题目要求返回最长湍流子数组的长度即所有f[i]和g[i]中的最大值。我们在递推过程中同步维护ret最终返回ret。三、代码class Solution { public: int maxTurbulenceSize(vectorint arr) { int n arr.size(); if (n 0) return 0; // 1. 创建dp表两个一维数组 // f[i] : 以 arr[i] 结尾且最后一段比较关系为“下降”arr[i-1] arr[i]的湍流子数组的最大长度 // g[i] : 以 arr[i] 结尾且最后一段比较关系为“上升”arr[i-1] arr[i]的湍流子数组的最大长度 vectorint f(n, 1); // 初始化每个元素至少自身长度为1 vectorint g(n, 1); int ret 1; // 全局最大湍流长度至少为1 // 2. 初始化dp[0] 已经为1表示单个元素构成湍流子数组 // 3. 填表顺序从左到右i 从 1 到 n-1因为 f[i]/g[i] 依赖 f[i-1]/g[i-1] for (int i 1; i n; i) { // 4. 状态转移方程 // 若当前比较为“下降”前一个元素大于当前 // 则可以从上一个“上升”状态g[i-1]延长长度加1 if (arr[i - 1] arr[i]) { f[i] g[i - 1] 1; } // 若当前比较为“上升”前一个元素小于当前 // 则可以从上一个“下降”状态f[i-1]延长长度加1 else if (arr[i - 1] arr[i]) { g[i] f[i - 1] 1; } // 若相等则不满足湍流条件f[i]和g[i]保持为1重新开始 // 更新全局最大值 ret max(ret, max(f[i], g[i])); } // 5. 返回值整个数组中的最长湍流子数组长度 return ret; } };四、流程图五、题目六、做题思路6.1 状态表示核心基础本题要求判断字符串s能否被字典中的单词拼接而成。我们定义dp[i]表示字符串s的前i个字符即s[0..i-1]能否被拆分成字典中的单词。6.2 状态转移方程关键难点考虑最后一个单词的起始位置j1 ≤ j ≤ i那么前缀s[0..i-1]可拆分当且仅当前缀s[0..j-2]可拆分即dp[j-1] true并且子串s[j-1..i-1]即第j到第i个字符在字典中。因此状态转移方程为dp[i] true当且仅当存在j ∈ [1, i]使得dp[j-1] true且s.substr(j-1, i-j1)在字典中。实际编码中我们从i向前枚举j一旦找到满足条件的j立即置dp[i] true并跳出以提升效率。6.3 初始化边界防护空串可以被拆分因此dp[0] true。其余dp[i]初始化为false。为方便处理子串在s前添加一个占位字符如空格使得s[j]对应原始字符串的第j-1个字符这样取子串时s.substr(j, i-j1)表示原始s[j-1..i-1]。6.4 填表顺序递推方向dp[i]依赖dp[j-1]其中j-1 i即更小的前缀长度。因此必须从左到右即i从 1 到n依次填充dp表确保每个状态计算时其所有前置状态已就绪。6.5 返回值目标映射题目要求返回整个字符串s能否被拆分即长度为n的前缀的可拆分性对应dp[n]。因此直接返回dp[n]。七、代码class Solution { public: bool wordBreak(string s, vectorstring wordDict) { // 1. 使用哈希集合存储单词便于 O(1) 查询 unordered_setstring hash; for (const string word : wordDict) { hash.insert(word); } int n s.size(); // 2. 创建dp表 // dp[i] 表示字符串 s 的前 i 个字符即 s[0..i-1]能否被拆分成字典中的单词 // 为了方便处理边界我们在 s 前面加一个空格使索引从 1 开始对应原始字符 vectorbool dp(n 1, false); // 3. 初始化空串可以被拆分 dp[0] true; // 为了方便取子串在 s 前面添加一个占位符空格这样 s[j] 对应原始第 j-1 个字符 // 注意substr(j, len) 中的 j 是 1-based 索引因为前面加了空格 s s; // 4. 填表顺序从左到右i 从 1 到 n因为 dp[i] 依赖于更小的索引 dp[j-1] for (int i 1; i n; i) { // 内层循环从 i 向前遍历尝试找最后一个单词的起始位置 j // 从后向前可以尽早找到匹配并跳出优化 for (int j i; j 1; j--) { // 5. 状态转移方程 // 如果前 j-1 个字符可以拆分dp[j-1] true // 并且子串 s[j..i] 在字典中则 dp[i] true if (dp[j - 1] hash.count(s.substr(j, i - j 1))) { dp[i] true; break; // 一旦成立无需继续尝试其他 j } } } // 6. 返回值dp[n] 表示整个字符串是否能被拆分 return dp[n]; } };八、流程图

《LeetCode 978 最长湍流子数组 || LeetCode 413 等差数列划分》

相关推荐

ENVI 5.6 与 ArcGIS Pro 3.2 协同：Landsat 8 荒漠化监测全流程实战

AI安全技术博文创作的合规性与内容可行性标准

C程序ANSI彩色日志实践

更多资讯

桂林水电工证有效期多久？学历不高怕报不上名？良心建议来了

电工证出证渠道怎么选？官方回应来了，实操考试心里没底怕挂科

绵阳在哪里办理电工证良心建议：电工证缺口大，考前必看干货

外省电工证能转过来吗官方回应来了考电工证刷学时的软件怎么选

高压电工证多久审一次怎么查网上查询最靠谱

住建厅特种工报名时间你搞错了？官方报名入口早知道

今日更新

特种工指挥考试题库怎么刷才不会白交培训费？官方报名入口在这！

电工证考试多少分合格在哪考别再交冤枉钱了

福清应急管理局电工证真实经历：工地太忙根本没时间复习考试怎么办

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？