LeetCode-Go 667 Beautiful Arrangement II构造“恰好 k 种相邻差值”排列的前序 对半穿插法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中 667 题解题文档完整讲解 LeetCode 667Beautiful Arrangement II的构造性算法如何把1..n排成一个数组使其相邻绝对差恰好包含 k 个不同的整数。读完你可以掌握“先探两个极端值、再分段构造”的通用构造思路并对照仓库中的 Go 实现与测试文件逐行验证该构造的边界行为尤其是 k 的奇偶性处理。题目定义与约束原题LeetCode 667. Beautiful Arrangement II仓库文档保留了英文原文Given two integersnandk, you need to construct a list which containsndifferent positive integers ranging from1tonand obeys the following requirement: Suppose this list is[a1, a2, a3, ... , an], then the list[|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]has exactlykdistinct integers.If there are multiple answers, print any of them.题目大意给定两个整数 n 和 k实现一个数组这个数组包含从 1 到 n 的 n 个不同整数同时满足如果这个数组是[a1, a2, a3, ... , an]那么数组[|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]中应该有且仅有 k 个不同整数如果存在多种答案只需返回其中任意一种。两个官方示例Example 1Input: n 3, k 1 Output: [1, 2, 3] Explanation: [1, 2, 3] 包含 1 到 3 的三个不同正整数且 [1, 1] 恰好有 1 个不同整数1。Example 2Input: n 3, k 2 Output: [1, 3, 2] Explanation: [1, 3, 2] 的差值数组 [2, 1] 恰好有 2 个不同整数1 和 2。约束条件1 k n 10^4。即 n 最小为 2k 至少为 1且 k 严格小于 n。构造框架先观察 k 的两个极端仓库文档的解题思路采用了典型的“从极端情形反推一般规律”方法k 取最大值 n-1 的情形把末尾的较大值依次插入到前面的较小值中形成[1, n, 2, n-1, 3, n-2, ……]这种“两端对半穿插”的排列。相邻差值依次为 n-1、n-2、……、1恰好覆盖 k n-1 个不同差值k 取最小值 1 的情形顺序排列[1, 2, 3, 4, ……, n]所有相邻差值都是 1k 1。那么 k 在[1, n-1]之间取值时怎么构造文档给出的答案是把数组拆成两段前半段顺序排列[1, 2, 3, 4, ……, n-k-1]共n-k-1个数只贡献一种差值1剩下k1个数n-k, n-k1, …, n用第 1 点里“k 最大”的穿插方式排列贡献 k 种差值。关键在于第 2 点k1个数要形成 k 个相邻差值且各不相同这与“n 个数形成 n-1 个不同差值”是同一个子问题可以直接复用最大 k 情形的构造。一般情形前序段 对半穿插段以n5, k3为例走一遍手工构造前序段n-k-1 1个数即[1]穿插段剩余 4 个数2, 3, 4, 5做两端穿插得到[2, 5, 3, 4]拼接结果[1, 2, 5, 3, 4]。验证差值|1-2|1, |2-5|3, |5-3|2, |3-4|1不同差值集合为{1, 2, 3}恰好 3 种满足 k3。对偶数 k如n5, k4穿插到“对半处”会剩一个中间数n-k(k1)/2必须最后单独追加穿插段[1, 5, 2, 4]剩余中间数3追加到末尾结果[1, 5, 2, 4, 3]差值4, 3, 2, 1恰好 4 种。为什么差值种类恰好是 k 而不是 k1这是文档中特别强调、也是该构造最容易误解的一点前序段构造了 1 种差值1穿插段构造了 k 种差值加起来不是k1种吗文档给出的解释是不是。穿插段的最后两个数字是n-k(k1)/2-1和n-k(k1)/2两者差值为 1而前序段的最后两个数字差值同样是 1。也就是说两段在交界处“共用”了差值 1。因此总的不同差值种类是1 k - 1 k种。换句话说穿插段的差值集合本身就是{1, 2, …, k}两端交替使差值在 k、k-1、k-2……之间递减直至 1它天然包含差值 1与前序段的差值 1 重叠最终并集大小恰为 k。Go 完整实现与逐行解读仓库中的解法见 667. Beautiful Arrangement II.go与文档中的代码完全一致package leetcode func constructArray(n int, k int) []int { res : []int{} // 第一段顺序排列 1 .. n-k-1只贡献差值 1 for i : 0; i n-k-1; i { res append(res, i1) } // 第二段i 与其配对值 2*n-k-i 交替放入形成 k, k-1, ..., 1 的差值 for i : n - k; i n-k(k1)/2; i { res append(res, i) res append(res, 2*n-k-i) } // k 为偶数时“对半处”的中间数单独追加 if k%2 0 { res append(res, n-k(k1)/2) } return res }逐行解读第一个 for 循环i从 0 到n-k-2依次追加i1生成1, 2, …, n-k-1。注意当k n-1时n-k-1 0该循环不执行整个排列全部由穿插段构成正好退化为最大 k 的情形第二个 for 循环i从n-k遍历到 n-k(k1)/2共执行(k1)/2次Go 整数除法向下取整。每轮把i与其配对值2*n-k-i成对追加。当i n-k时配对值恰为n随着i递增、配对值递减相邻差值依次出现k, k-1, k-2, …直至降到 1偶数 k 的补丁(k1)/2次循环只覆盖了k1个数中的前k个k 为偶数时k1为奇数必有 1 个中位数落单因此单独把中间数n-k(k1)/2追加到末尾。由于它与上一对配对值中较大者的差为 1不会引入新的差值种类。复杂度只做了 O(n) 次 append无额外空间除结果数组外满足n 10^4的约束。在 LeetCode-Go 仓库中查看与运行验证该题在仓库中的完整目录结构为 leetcode/0667.Beautiful-Arrangement-II/包含三个文件题解文档、解法文件与测试文件 667. Beautiful Arrangement II_test.go。测试文件用question667结构体内嵌参数结构体para667{ n, k }与答案结构体ans667{ one []int }组织了两组用例与文档中的官方示例一一对应{ para667{3, 1}, ans667{[]int{1, 2, 3}}, }, { para667{3, 2}, ans667{[]int{1, 3, 2}}, },Test_Problem667会遍历用例并打印输入与constructArray(p.n, p.k)的实际输出方便人工核对3,1应输出[1 2 3]3,2应输出[1 3 2]均与构造结论吻合。仓库整体是module github.com/halfrost/LeetCode-Go、Go 1.19 的单模块项目见 go.mod题解目录按“题号.题名”组织。查看本地运行方式单独运行本题测试go test -run Test_Problem667 ./leetcode/0667.Beautiful-Arrangement-II/仓库提供的覆盖率脚本 gotest.sh 执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部leetcode/...包一次性生成合法覆盖率文件667 题的解法与测试也包含其中。要点总结环节排列片段元素个数贡献的不同差值前序段1, 2, …, n-k-1n-k-1{1}穿插段偶数配对i与2n-k-i交替最多k个{k, k-1, …, 2}及边界 1偶数 k 的中间数n-k(k1)/21差值为 1与两段重叠本解法的核心技巧是复用极值构造k 最大情形的两端穿插天然产生n-1种差值把该技巧限制在数组尾部k1个数上即可精确产生 k 种差值前序段与穿插段的差值 1 发生重叠使总种类从表面的k1降为恰好 k这是证明构造正确性的关键一步实现上唯一需要特判的是k 的奇偶性偶数 k 时“对半穿插”会剩下中间数n-k(k1)/2须单独追加见 解法文件 的k%2 0分支。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
