codeforces-go 题解：最长相邻不等分组子序列 I —— 连续相同段贪心取一个的 O(n) 解法

科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文讲解 LeetCode 第 115 场双周赛 B 题 Longest Unequal Adjacent Groups Subsequence I 的完整解法并结合作者灵茶山艾府的开源算法竞赛模板库 codeforces-go 中的 Go 实现 与 测试用例 进行源码级印证。读完本文你将掌握「分组循环」这一高频贪心技巧的核心判别条件——只在连续相同段的末尾取元素并以 O(n) 时间、O(1) 空间完成最优解构造。题意重述给定两个等长数组words和groupsgroups[i]取值仅为0或1要求选出words的一个子序列使得该子序列中相邻两个字符串对应的groups值互不相同并且该子序列要尽可能长最后返回这个最长子序列。示例 words [e,a,b] groups [0,0,1] 最长子序列 [e,b] groups 为 0→1相邻不等核心思路把 groups 看作 01 串按连续相同段分组1. 连续相同段的划分为了直观理解可以把groups看作一个01字符串。例如groups 0001100可以分成三个连续的相同段000 | 11 | 00每一段内的groups值全部相同相邻段之间的值必然不同。2. 鸽巢原理确定上界题目的约束是「相邻字符串对应的groups[i]不同」即选出的相邻元素必须落在不同段中。因此每一段内最多只能选一个元素否则同段相邻违反约束一共有k段那么答案子序列的长度至多为k。如果试图选出超过k个字符串根据鸽巢原理必然至少有两个字符串落在同一段内且它们在该段内的选取必然导致相邻位置值相同违反题意。因此k就是答案长度的上界。3. 构造每个连续相同段恰好取末尾一个上界k是否可达可以。由于相邻段的值必然不同我们只要每个段任意选一个元素得到的子序列相邻元素都满足「值不同」。因此最长子序列长度为段数k且构造方式为遍历每个连续相同段取其中任意一个words[i]。一个实现上的小技巧是只在段尾取元素——当i n-1或groups[i] ! groups[i1]时说明i是当前连续相同段的末尾此时把words[i]加入答案即可。这样无需记录段头一趟遍历即可完成。多语言实现该题解在文档中给出了 7 种语言的实现核心逻辑完全一致区别仅在语法。Go对应仓库中的实际提交仓库 Go 实现package main // https://space.bilibili.com/206214 func getWordsInLongestSubsequence(words []string, groups []int) (ans []string) { n : len(groups) for i, x : range groups { if i n-1 || x ! groups[i1] { ans append(ans, words[i]) } } return }Python普通写法与 groupby 写法class Solution: def getLongestSubsequence(self, words: List[str], groups: List[int]) - List[str]: n len(groups) ans [] for i, g in enumerate(groups): if i n - 1 or g ! groups[i 1]: # i 是连续相同段的末尾 ans.append(words[i]) return ansPython 还提供了一行式写法用itertools.groupby把相邻的相同值聚合成组每组取第一个元素class Solution: def getLongestSubsequence(self, words: List[str], groups: List[int]) - List[str]: return [next(g)[0] for _, g in groupby(zip(words, groups), keylambda z: z[1])]Java / C / C / JavaScript / RustJava 版本class Solution { public ListString getLongestSubsequence(String[] words, int[] groups) { ListString ans new ArrayList(); int n groups.length; for (int i 0; i n; i) { if (i n - 1 || groups[i] ! groups[i 1]) { // i 是连续相同段的末尾 ans.add(words[i]); } } return ans; } }C 版本class Solution { public: vectorstring getLongestSubsequence(vectorstring words, vectorint groups) { vectorstring ans; int n groups.size(); for (int i 0; i n; i) { if (i n - 1 || groups[i] ! groups[i 1]) { // i 是连续相同段的末尾 ans.push_back(words[i]); } } return ans; } };C 版本注意需要手动管理返回数组和*returnSizechar** getLongestSubsequence(char** words, int wordsSize, int* groups, int groupsSize, int* returnSize) { char** ans malloc(sizeof(char*) * groupsSize); int idx 0; for (int i 0; i groupsSize; i) { if (i groupsSize - 1 || groups[i] ! groups[i 1]) { // i 是连续相同段的末尾 ans[idx] words[i]; } } *returnSize idx; return ans; }JavaScript 版本var getLongestSubsequence function(words, groups) { const n groups.length; const ans []; for (let i 0; i n; i) { if (i n - 1 || groups[i] ! groups[i 1]) { // i 是连续相同段的末尾 ans.push(words[i]); } } return ans; };Rust 版本impl Solution { pub fn get_longest_subsequence(words: VecString, groups: Veci32) - VecString { let n groups.len(); let mut ans vec![]; for (i, word) in words.into_iter().enumerate() { if i n - 1 || groups[i] ! groups[i 1] { // i 是连续相同段的末尾 ans.push(word); } } ans } }复杂度分析时间复杂度O(n)其中 n 是words与groups的长度。只需一趟线性扫描每次比较相邻元素即可判定段尾。空间复杂度O(1)。除返回答案数组外不使用额外存储返回值不计入空间开销。该复杂度已达到理论下界——每个元素至少要访问一次才能确定其归属段因此无法做得更快。仓库源码级印证从实现到测试1. 函数签名与文档一致仓库中的 b.go 与题解文档的 Go 版本完全对应函数名为getWordsInLongestSubsequence使用命名返回值ans []string使代码更加简洁。该文件位于leetcode/biweekly/115/b/目录下与题目的周赛场次biweekly contest 115和题号B 题一一对应。2. 本地测试框架如何驱动该目录下的 b_test.go 展示了这类题解在仓库中的标准测试方式func Test_b(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, getWordsInLongestSubsequence, b.txt, targetCaseNum); err ! nil { t.Fatal(err) } }它调用 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile从 b.txt 读取用例数据。该测试框架的机制可以概括为逐行解析b.txt每 3 行为一组用例输入参数1、输入参数2、期望输出通过反射reflect将字符串输入转换为函数实参并调用被测试函数RunLeetCodeFuncWithExamples 中的parseRawArg与fValue.Call(ins)将实际输出与期望输出比对并内置 TLE超时检测超时的用例会被单独标注leetcode.gotargetCaseNum支持选择单个用例0表示测试全部用例-1表示最后一个用例正数表示指定用例单个用例通过后还会自动补测全部用例。3. 测试数据覆盖b.txt 中的两组用例[e,a,b] words [0,0,1] groups [e,b] 期望输出 [a,b,c,d] words [1,0,1,1] groups [a,b,c] 期望输出第二组用例groups [1,0,1,1]被划分为三段1 | 0 | 1(1)最后两个1属于同一段段内只取末尾的c输出[a,b,c]恰好覆盖了「段内多个相同值只取一个」的关键边界情况。易错点与思维拓展子序列 vs 子数组本题允许跳过元素因此同一段内取任意一个即可若题目改为子数组约束则完全不同。段尾判定的边界i n-1必须放在||前面否则最后一个元素访问groups[i1]会越界各语言版本都正确处理了这一边界。为什么不能每段取多个同段内相邻元素的groups值必然相同一旦在段内取两个及以上元素就会直接违反「相邻字符串对应的groups[i]不同」。变式延伸若把groups的取值从二值推广为多值思路依然成立——只需保证相邻元素值不同仍是对值序列做连续相同段划分后每段取一个仓库作者将该题归类于「贪心与思维」「分组循环」一类题单这类按连续段分组、段内一次决策的模板在滑动窗口、双指针、区间覆盖等题目中同样适用。小结本题是典型的想通即秒杀的贪心构造题把groups视为 01 串并按连续相同段分组用鸽巢原理证明答案上界为段数 k再用「段尾取元素」的一趟扫描构造出最优解整体 O(n) 时间、O(1) 空间。该题在 codeforces-go 仓库中具备完整的 实现、测试文件 与 用例数据可作为学习「分组循环」模板及仓库测试框架的入门样例。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode「删除相邻近似相等字符」贪心解法codeforces-go 仓库的 Go 实现与自动化测试实践LeetCode「删除相邻近似相等字符」贪心解法codeforces go 仓库的 Go 实现与自动化测试实践 本文基于 codeforces go 仓库中科学计算LeetCode 1526 形成目标数组的子数组最少增加次数从 O(n²) 贪心到 O(n) 相邻差分统计的完整推导LeetCode 1526 形成目标数组的子数组最少增加次数从 O n² 贪心到 O n 相邻差分统计的完整推导 本文是 leetcode 题解仓库 REA文档教程知识库LeetCode-Go 题解1200. Minimum Absolute Difference最小绝对差——排序后相邻扫描的 O(n log n) 解法LeetCode Go 题解1200. Minimum Absolute Difference最小绝对差——排序后相邻扫描的 O n log n 解法 导示例工程上一篇碧蓝航线Alas自动化脚本架构解析与智能调度系统深度剖析下一篇DLSS Swapper完全指南如何轻松管理DLSS、FSR和XeSS版本提升游戏性能创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考