《LeetCode 467 环绕字符串中唯一的子字符串 || LeetCode 300 最长递增子序列》

一、题目二、做题思路2.1 状态表示核心基础本题要求统计s中所有不同非空子串且这些子串需出现在无限环绕字符串base中。由于base是循环的有效子串必须是连续递增字母序相邻的序列允许z到a的循环。我们定义dp[i]表示以s[i]结尾的最长连续有效子串的长度。2.2 状态转移方程关键难点要判断能否将s[i]接在以s[i-1]结尾的有效子串后面只需检查两者在环绕字符串中是否相邻即s[i-1] 1 s[i]或s[i-1] z s[i] a。若满足相邻条件则dp[i] dp[i-1] 1将当前字符附加到之前的连续子串后。否则无法延续只能以当前字符单独作为有效子串dp[i] 1。2.3 初始化边界防护第一个字符下标 0没有前驱其最长连续有效子串长度为 1因此dp[0] 1。2.4 填表顺序递推方向dp[i]仅依赖dp[i-1]因此必须从左到右即i从 1 到n-1依次填充dp表确保每个状态计算时其前置状态已就绪。2.5 返回值目标映射题目要求返回不同非空子串的总数。直接累加所有dp[i]会重复计数例如zab中ab被zab包含因此需要去重对于每个字母c只需保留以c结尾的最大dp值因为以c结尾的所有有效子串长度 1 到最大值都包含在最长的那一个里且这些子串各不相同。具体做法用数组hash[26]记录每个字母结尾的最大长度遍历dp更新hash最后sum(hash)即为答案。该去重策略巧妙地避免了重复统计。三、代码class Solution { public: int findSubstringInWraproundString(string s) { int n s.size(); // 边界处理空字符串无子串 if (n 0) return 0; // 1. 创建dp表 // dp[i] 表示以 s[i] 结尾的最长连续子串的长度这里的“连续”指在无限环绕字符串 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz... 中连续 // 例如s zabdp[0]1zdp[1]2zadp[2]3zab vectorint dp(n, 0); // 2. 初始化第一个字符结尾的最长连续子串长度为1 dp[0] 1; // 3. 填表顺序从左到右i从1到n-1因为dp[i]依赖dp[i-1] for (int i 1; i n; i) { // 4. 状态转移方程 // 若当前字符与前一个字符在环绕字符串中相邻即前一个字符1 当前字符或前一个为z且当前为a // 则可以将当前字符附加到以s[i-1]结尾的所有连续子串后面形成新的更长连续子串 // 所以 dp[i] dp[i-1] 1 if (s[i - 1] 1 s[i] || (s[i - 1] z s[i] a)) { dp[i] dp[i - 1] 1; // 原代码使用 但dp[i]初始为0等效 } else { // 否则无法与前一个字符连续只能以当前字符单独作为一个连续子串长度为1 dp[i] 1; } } // 5. 去重统计因为以同一个字母结尾的不同起始位置会产生重叠的子串 // 例如 zab 中以 b 结尾的连续子串有 ab长度2和 zab长度3但 ab 已经是 zab 的后缀 // 所有以 b 结尾的连续子串实际上都包含在最长的那一个zab中所以只需保留最大长度。 // 用 hash[26] 记录每个字母结尾的最大连续子串长度 int hash[26] {0}; for (int i 0; i n; i) { int index s[i] - a; hash[index] max(hash[index], dp[i]); } // 6. 返回值所有以不同字母结尾的连续子串数量之和 // 因为对于某个字母结尾长度为 L 的最长连续子串可以产生 L 个不同的子串长度从1到L // 且这些子串分别以该字母结尾且互不相同直接累加 L 即可。 int sum 0; for (int i 0; i 26; i) { sum hash[i]; } return sum; } };四、流程图五、题目六、做题思路6.1 状态表示核心基础本题要求计算数组中最长严格递增子序列的长度。我们定义dp[i]表示以nums[i]结尾的最长递增子序列的长度。6.2 状态转移方程关键难点要构造以nums[i]结尾的递增子序列前一个元素可以是任意nums[j]其中j i且必须满足nums[j] nums[i]。若满足则可以将nums[i]接在nums[j]结尾的递增子序列后面形成长度为dp[j] 1的新子序列。为了获得最长长度我们在所有满足条件的j中取最大值dp[i] max(dp[i], dp[j] 1)其中j从 0 到i-1遍历且nums[j] nums[i]。若不满足任何j则dp[i]保持为 1仅包含自身。6.3 初始化边界防护每个元素自身至少可以构成长度为 1 的递增子序列因此dp数组全部初始化为 1。6.4 填表顺序递推方向dp[i]依赖所有dp[j]j i即更小的下标。因此必须从左到右即i从 1 到n-1依次填充dp表且对于每个i内层遍历所有j i确保每个状态计算时其所有前置状态均已就绪。6.5 返回值目标映射题目要求返回整个数组的最长递增子序列长度即所有dp[i]中的最大值。我们在计算完成后遍历dp数组取最大值最终返回ret。七、代码class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; // 边界处理 // 1. 创建dp表 // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度 vectorint dp(n, 1); // 初始化每个元素自身构成一个长度为1的子序列 // 2. 填表顺序从左到右i从1到n-1因为dp[i]依赖之前的所有dp[j]j i for (int i 1; i n; i) { // 内层循环遍历所有j i寻找可以与nums[i]构成递增关系的dp[j] for (int j 0; j i; j) { // 3. 状态转移方程 // 若 nums[j] nums[i]则可以将 nums[i] 接在以 nums[j] 结尾的最长递增子序列后面 // 形成以 nums[i] 结尾、长度为 dp[j] 1 的递增子序列 if (nums[i] nums[j]) { dp[i] max(dp[i], dp[j] 1); } } } // 4. 返回值所有 dp[i] 中的最大值即为整个数组的最长递增子序列长度 int ret 0; for (int i 0; i n; i) { ret max(ret, dp[i]); } return ret; } };八、流程图