★ FEATURED ARTICLE 科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文基于本仓库 leetcode/biweekly/134/c/README.md 的题解骨架完整讲解力扣第 3207 题「交替组 II」Alternating Groups II的两套单指针滑动窗口写法并结合仓库源码c.go、c_test.go、c.txt、a.go及 weekly/391/c/c.go 中的 3101 题实现做源码级印证。读完本文你将掌握如何在环形数组上用 O(n) 时间、O(1) 空间统计长度为 k 的交替子数组个数理解两种循环边界写法2n 次循环 i n去重以及 nk-1 次循环天然不重复各自的原理与适用场景并能在七种主流语言间自如迁移该模板。一、题目背景从普通数组到环形数组本仓库 leetcode/biweekly/134/README.md 显示本题出自力扣双周赛 134 的第 3 题。题目给出一个环形数组colors长度为 n和一个整数 k要求统计长度为 k 的交替组的个数一组连续的 k 个元素中任意相邻两个元素都不相等。环形数组意味着首尾相接下标 n-1 与下标 0 也是相邻的因此跨过边界的位置同样需要参与交替性判断。这一点是本题与普通数组版本最大的区别也是绝大多数环形类题目的通用难点。题目约束中1 k n这保证了“交替组”不会重复跨越多个环也为写法二把循环次数压缩到 nk-1 提供了前提。前置铺垫3101 交替子数组计数普通数组版文档明确指出本题是环形数组版本建议先完成普通数组版本 —— 3101. 交替子数组计数Count Alternating Subarrays出自周赛 391。该题求的是数组中所有交替子数组的个数核心是一个经典的单指针计数在 leetcode/weekly/391/c/c.go 中可以找到它的 Go 实现// https://space.bilibili.com/206214 func countAlternatingSubarrays(nums []int) (ans int64) { cnt : 0 for i, x : range nums { if i 0 x nums[i-1] { cnt 1 } else { cnt } ans int64(cnt) } return }其核心思想是维护以当前下标i为右端点的最长交替子数组长度cnt。每向后走一步如果当前元素与前一个元素相等说明交替性被打断cnt重置为 1否则交替段延续cnt加 1。而以i为右端点的交替子数组恰好有cnt个长度 1、2、……、cnt累加即可。本题交替组 II正是在这个“维护 cnt”的思想上加上两个新约束只统计长度恰好为 k的交替组数组是环形的边界处也要判断交替性。二、核心思路复制拼接 取模映射处理环形数组时一个自然的想法是把数组复制一份拼接起来形成一个长度为 2n 的新数组这样“环”就被摊平成了一个普通数组跨边界的相邻关系colors[n-1]与colors[0]在新数组中变成了紧邻的colors[n-1]与colors[n]问题得以用普通数组的方式解决。文档同时点出了一个实现上的优化代码里不需要真的复制数组而是用colors[i % n]的方式访问i从 0 遍历到 2n-1 时i % n就等价于在拼接后的数组上顺序扫描。这样空间复杂度保持 O(1)。这一步“用取模替代物理拼接”的技巧在仓库第一题交替组 Ik3 的固定版本中也能看到对照——leetcode/biweekly/134/a/a.go 采用了物理拼接的写法func numberOfAlternatingGroups(a []int) (ans int) { a append(a, a...) c : 0 for i, v : range a { if i 0 v a[i-1] { c 0 } c if i len(a)/2 c 3 { ans } } return }对比可见a.go直接append(a, a...)复制了一份n 较小且答案固定 k3 时可接受而c.go用取模把空间开销降到了 O(1)。这是同一个计数模板的两种工程取舍。三、写法一循环 2n 次 i n去重写法一严格模拟“扫描拼接后的 2n 长数组”遍历i从 0 到 2n-1若colors[i % n] colors[(i 1) % n]说明这两个相邻位置颜色相同交替段被打断cnt归零否则cnt表示以i在拼接视角下为右端点的交替段长度当i n且cnt k时i就是某个长度为 k 的交替子数组的右端点答案加一。为什么必须加i n的判断因为在拼接后的 2n 长数组里前半段i n中的每个交替子数组都对应着环中一个“真实”的起点——但它同时也可能在环中被重复统计。具体来说长度为 k 的交替组在环中共有 n 种起点位置但扫描 2n 长的数组时每个交替组会在两个位置起点、起点 n附近各出现一次。限制只统计i n的右端点就恰好让每个交替组只被计入一次避免重复。文档给出的 Go 实现如下这也是仓库 leetcode/biweekly/134/c/c.go 中的numberOfAlternatingGroups2func numberOfAlternatingGroups2(colors []int, k int) (ans int) { n : len(colors) cnt : 0 for i : range n * 2 { if colors[i%n] colors[(i1)%n] { cnt 0 } cnt if i n cnt k { ans } } return }四、写法二循环 nk-1 次天然不重复写法二换了一个观察角度环上长度为 k 的交替组一共有且仅有 n 个k n 时它们的下标范围依次是第 1 个子数组[0, k-1]第 2 个子数组[1, k]第 3 个子数组[2, k1]……第 n 个子数组[n-1, nk-2]也就是说只需把循环进行到i nk-2即最后一个子数组的右端点为止也就是循环nk-1次。由于这个区间内每个长度为 k 的滑动窗口都对应一个不同的起点起点 0 到 n-1 各出现一次不存在重复统计因此不再需要i n的判断代码更简洁。文档给出的写法二 Go 实现正是仓库 c.go 中的主解numberOfAlternatingGroupsfunc numberOfAlternatingGroups(colors []int, k int) (ans int) { n : len(colors) cnt : 0 for i : range n k - 1 { if colors[i%n] colors[(i1)%n] { cnt 0 } cnt if cnt k { ans } } return }两种写法的时间复杂度均为 O(n)空间复杂度均为 O(1)。写法一的循环次数固定为 2n写法二在 k 接近 n 时循环约 2n 次、在 k 较小时循环约 n 次整体更省而写法一在“不加思考、严格模拟拼接”的思路上更直觉、不易写错边界。文档将其作为两种并列的写法呈现实际解题时可以互相校验例如本题解c.go中两种写法同时保留。五、七语言代码对照完整收录文档为两种写法分别提供了 Python3、Java、C、C、Go、JavaScript、Rust 七种语言的完整实现以下完整继承便于作为跨语言模板直接复用。写法一2n 循环 i n去重Python3class Solution: def numberOfAlternatingGroups(self, colors: List[int], k: int) - int: n len(colors) ans cnt 0 for i in range(n * 2): if colors[i % n] colors[(i 1) % n]: cnt 0 cnt 1 if i n and cnt k: ans 1 return ansJavaclass Solution { public int numberOfAlternatingGroups(int[] colors, int k) { int n colors.length; int ans 0; int cnt 0; for (int i 0; i n * 2; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; if (i n cnt k) { ans; } } return ans; } }Cclass Solution { public: int numberOfAlternatingGroups(vectorint colors, int k) { int n colors.size(); int ans 0, cnt 0; for (int i 0; i n * 2; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; ans i n cnt k; } return ans; } };Cint numberOfAlternatingGroups(int* colors, int n, int k) { int ans 0, cnt 0; for (int i 0; i n * 2; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; if (i n cnt k) { ans; } } return ans; }Gofunc numberOfAlternatingGroups(colors []int, k int) (ans int) { n : len(colors) cnt : 0 for i : range n * 2 { if colors[i%n] colors[(i1)%n] { cnt 0 } cnt if i n cnt k { ans } } return }JavaScriptvar numberOfAlternatingGroups function(colors, k) { const n colors.length; let ans 0, cnt 0; for (let i 0; i n * 2; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; if (i n cnt k) { ans; } } return ans; };Rustimpl Solution { pub fn number_of_alternating_groups(colors: Veci32, k: i32) - i32 { let n colors.len(); let mut ans 0; let mut cnt 0; for i in 0..n * 2 { if colors[i % n] colors[(i 1) % n] { cnt 0; } cnt 1; if i n cnt k { ans 1; } } ans } }写法二nk-1 循环无需去重Python3class Solution: def numberOfAlternatingGroups(self, colors: List[int], k: int) - int: n len(colors) ans cnt 0 for i in range(n k - 1): if colors[i % n] colors[(i 1) % n]: cnt 0 cnt 1 if cnt k: ans 1 return ansJavaclass Solution { public int numberOfAlternatingGroups(int[] colors, int k) { int n colors.length; int ans 0; int cnt 0; for (int i 0; i n k - 1; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; if (cnt k) { ans; } } return ans; } }Cclass Solution { public: int numberOfAlternatingGroups(vectorint colors, int k) { int n colors.size(); int ans 0, cnt 0; for (int i 0; i n k - 1; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; ans cnt k; } return ans; } };Cint numberOfAlternatingGroups(int* colors, int n, int k) { int ans 0, cnt 0; for (int i 0; i n k - 1; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; ans cnt k; } return ans; }Gofunc numberOfAlternatingGroups(colors []int, k int) (ans int) { n : len(colors) cnt : 0 for i : range n k - 1 { if colors[i%n] colors[(i1)%n] { cnt 0 } cnt if cnt k { ans } } return }JavaScriptvar numberOfAlternatingGroups function(colors, k) { const n colors.length; let ans 0, cnt 0; for (let i 0; i n k - 1; i) { if (colors[i % n] colors[(i 1) % n]) { cnt 0; } cnt; if (cnt k) { ans; } } return ans; };Rustimpl Solution { pub fn number_of_alternating_groups(colors: Veci32, k: i32) - i32 { let n colors.len(); let mut ans 0; let mut cnt 0; for i in 0..n k as usize - 1 { if colors[i % n] colors[(i 1) % n] { cnt 0; } cnt 1; if cnt k { ans 1; } } ans } }六、复杂度分析时间复杂度O(n)其中 n 是colors的长度。无论写法一循环 2n 次还是写法二循环 nk-1 次k n循环次数都只是 n 的常数倍每个位置至多被常数次访问。空间复杂度O(1)。只使用了几个基本变量ans、cnt、n并通过i % n代替数组复制不额外分配与 n 相关的空间。七、仓库源码级验证测试用例与运行方式本仓库为本题配置了完整的测试设施可在本地直接运行验证解题源码leetcode/biweekly/134/c/c.go同时收录写法一numberOfAlternatingGroups2与写法二numberOfAlternatingGroups两个版本并保留题目来源注释。测试文件leetcode/biweekly/134/c/c_test.go通过testutil.RunLeetCodeFuncWithFile(t, numberOfAlternatingGroups, c.txt, 0)从外部用例文件驱动测试测试框架位于 leetcode/testutil/leetcode.go。测试数据leetcode/biweekly/134/c/c.txt 中的 3 组用例格式为「数组 / k / 预期答案」例如[0,1,0,1,0] 3 3 [0,1,0,0,1,0,1] 6 2 [1,1,0,1] 4 0第一组[0,1,0,1,0]、k3环上 5 个起点均构成交替三组答案 3注意第一组和最后一组共享元素需借助环处理才能正确计数第二组k6、n7只有两个位置能凑出长度为 6 的交替段答案 2第三组[1,1,0,1]、k4整个环长因存在相邻相同元素1,1无法形成整环交替答案 0。这些用例同时覆盖了普通情况、跨边界统计和 kn 的边界情况。运行方式在仓库根目录执行go test ./leetcode/biweekly/134/c -run Test_c -v即可看到Test_c对用例文件逐条校验的结果。八、相关变体与延伸交替组 Ik3 的固定版本本仓库 leetcode/biweekly/134/a/a.go 收录了同场双周赛的交替组 I要求长度为 3 的交替组。它在c.go的思路上做了两点简化固定cnt 3并用物理拼接append(a, a...)替代取模便于初学者理解“复制拼接”这一环形处理范式。对比两题代码可以发现交替组 II 正是把 I 中写死的 3 参数化为 k因此学习时先理解 a.go 再迁移到 c.go 是顺滑的进阶路径。相似的环形处理场景下一个更大元素 II文档将 503. 下一个更大元素 II 列为相似题目。该题同样是环形数组 单调栈的经典场景其处理方式同样是“循环取模模拟复制”核心套路一致环形问题优先考虑是否可以把数组展开/复制/取模从而复用线性扫描算法。如果你在单调栈中处理环形时感到困难本题的两处写法物理拼接 vs 取模正好给出了两种可迁移的工程范式。九、易错点小结忘记i n去重写法一若缺少该条件拼接数组前半段的右端点会把环上每个交替组多算一次。写法二循环上界写错最后一个子数组右端点是nk-2对应循环i nk-1若写成nk会多扫描导致错误答案虽然 kn 时多出的部分一般不会改变 cnt 的逻辑但会引入越界/多余计算务必按文档边界写。取模访问的越界访问colors[(i1)%n]时 i 最大取到 2n-1 或 nk-2(i1)%n均落在 [0, n-1] 内无需担心越界这是取模写法的自带安全属性。kn 的整环情况此时只有全环交替才能产生答案测试用例[1,1,0,1], k4 - 0提示我们不要忘记验证首尾相接的相邻对。十、延伸学习本题是“单序列 定长窗口 环形数组”三要素的典型组合。文档还给出了系列分类题单与精选题解索引方便按主题继续训练滑动窗口与双指针定长/不定长/单序列/双序列/三指针方向可进一步巩固定长滑动窗口的计数技巧常用数据结构与算法题单可系统补齐前缀和、差分、栈、队列、堆、树状数组、线段树等相邻技能点仓库 leetcode/SOLUTIONS.md 收录了作者按分类整理的精选题解可在掌握本题后继续拓展同类型环形数组与滑动窗口题目。总结来说交替组 II 是一个“旧思路 新包装”的教科书级题目把 3101 的单指针cnt计数迁移到环形数组上再用取模替代复制把空间压到 O(1)。掌握写法一直观、2n 循环、i n去重与写法二精炼、nk-1 循环、天然不重复后环形数组类问题如 503 下一个更大元素 II的通用处理范式也就一并掌握了。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 134 题解交替组计数、贪心取点与 AND 值为 k 的子数组枚举codeforces-go 仓库配套实现力扣双周赛 134 题解交替组计数、贪心取点与 AND 值为 k 的子数组枚举codeforces go 仓库配套实现 本篇文章以 leetcode/bi科学计算LeetCode 125 验证回文串头尾双指针解法全解含 JS/C/Python/Java 多语言实现LeetCode 125 验证回文串头尾双指针解法全解含 JS/C/Python/Java 多语言实现 本篇技术指南以 leetcode 题解仓库中的文档教程知识库LocalSend 跨平台文件传输兼容性自查5 个平台的最低系统要求、唯一要开放的端口与 Win7 的版本选择LocalSend 跨平台文件传输兼容性自查5 个平台的最低系统要求、唯一要开放的端口与 Win7 的版本选择 家里一台 Win7 老机器、公司一台安卓手机、即时通讯网络/通信上一篇Haystack 集成指南使用 AIMLAPIChatGenerator 统一调用多供应商生成式模型下一篇Ente Locker 使用指南端到端加密的家庭重要信息保险库与数字遗产继承方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
