《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彩色日志实践

更多资讯

三处改动把MoE接进DiT：构建完整专家混合扩散模型

UPS选型与NUT联动关机：PVE/TrueNAS实战

全栈模板3分钟跑通：React+Vite+NestJS+Electron实战

第031篇腾讯性能专项面经：帧率与卡顿定位到底怎么答？

第030篇腾讯跨端通信开发面经：面试官问数据同步与一致性想听什么？

CANN Runtime CMO 缓存操作接口解析：aclrtCmoAsync 系列 API 使用与实现原理

今日更新

校园网认证计费模式详解：AAA与代拨架构、原理及排障

Spring Boot+Vue垃圾分类毕设：分层、权限与排错实战

把 Cline 的 Base URL 改到 TaoToken 之后，DeepSeek 仍能修调试配置

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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