科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本篇技术指南以 leetcode/biweekly/121/a/README.md 题解文档为核心深入讲解力扣双周赛第 121 场 A 题《最小缺失整数》Smallest Missing Integer Greater Than Sequential Prefix Sum的完整解法先遍历数组求最长连续递增前缀的元素和再用哈希集合从该前缀和出发逐步自增找到第一个不在数组中的整数。读完本文你将掌握这道题的两阶段线性算法、四语言Python/Java/C/Go代码模板、边界用例如1324567以及本仓库如何用a.go、a.txt与a_test.go组成题解 样例数据 自动化测试的完整闭环。一、题目核心顺序前缀和是什么题目要求给定整数数组nums先求出最长的顺序前缀的元素之和s——所谓顺序前缀是指从nums[0]开始、每个元素都比前一个元素恰好大1的连续前缀随后不断将s加1直到s不再出现在nums中此时返回s。为什么是前缀而不是任意子段原文档明确了两点关键约束前缀必须从nums[0]开始也就是只能从数组头部向后延伸前缀内相邻元素严格满足x 1 y连续整数一旦断链例如nums[i] ! nums[i-1]1就立刻停止累加。例如nums [1, 2, 3, 2, 5]最长顺序前缀是[1, 2, 3]其和为s 66不在数组中直接返回6。再如nums [3, 4, 5, 1, 12, 14, 13]最长顺序前缀是[3, 4, 5]s 12但12在数组中于是s依次变为13仍在数组中、14仍在数组中、15不在数组中最终返回15。这两个样例正是仓库中 a.txt 里存储的测试数据一并在下节验证。二、算法思路两阶段线性扫描阶段一求最长顺序前缀的和从nums[0]出发初始化s nums[0]从第二个元素开始向后检查只要nums[i] nums[i-1] 1就继续把nums[i]累加进s否则立即跳出循环。由于前缀要求从nums[0]起连续这里用短路同时判断越界与连续性一旦断链就终止因此前缀不可能从中间某个位置重新开始。阶段二从s出发找最小缺失整数将整个nums装入哈希集合然后反复执行while s 在集合中: s 1每次把s加1都是因为s本身被占用了一旦s不在集合中就得到了答案。这个循环至多执行n次n为数组长度因为当s增长到超过数组中最大值后必然不在集合中——原文档给出的极端例子是nums [1, 3, 2, 4, 5, 6, 7]即1324567此时最长顺序前缀是[1]s 11在数组中之后依次跳过2,3,4,5,6,7七个元素s最终变成8才跳出循环恰好循环了n 7次。复杂度分析原文档结论时间复杂度O(n)其中n是nums的长度。阶段一是单次线性扫描阶段二至多自增n次哈希集合的插入与查询均摊O(1)空间复杂度O(n)用于存储哈希集合。三、四语言代码模板继承自原题解文档原文档给出了 Python3、Java、C、Go 四份等价的实现这里完整保留并补充注释class Solution: def missingInteger(self, nums: List[int]) - int: s nums[0] for x, y in pairwise(nums): if x 1 ! y: break s y st set(nums) while s in st: # 至多循环 n 次例如 1324567 s 1 return sclass Solution { public int missingInteger(int[] nums) { int sum nums[0]; for (int i 1; i nums.length nums[i] nums[i - 1] 1; i) { sum nums[i]; } SetInteger set new HashSet(); for (int num : nums) { set.add(num); } while (set.contains(sum)) { // 至多循环 n 次例如 1324567 sum; } return sum; } }class Solution { public: int missingInteger(vectorint nums) { int sum nums[0]; for (int i 1; i nums.size() nums[i] nums[i - 1] 1; i) { sum nums[i]; } unordered_setint s(nums.begin(), nums.end()); while (s.contains(sum)) { // 至多循环 n 次例如 1324567 sum; } return sum; } };func missingInteger(nums []int) int { sum : nums[0] for i : 1; i len(nums) nums[i] nums[i-1]1; i { sum nums[i] } has : map[int]bool{} for _, x : range nums { has[x] true } for has[sum] { // 至多循环 n 次例如 1324567 sum } return sum }四种实现殊途同归阶段一都用x 1 y或nums[i] nums[i-1] 1作为连续性判据阶段二都用哈希结构set/unordered_set/map[int]bool做 O(1) 判重。注意s从nums[0]开始取值即使第一个元素之后立即断链也至少要返回一个不小于nums[0]的缺失整数。四、仓库实现佐证从a.go到自动化测试闭环4.1 源码实现 a.go仓库中的 Go 解答与题解文档的sol-Go完全一致去掉了文档里has[sum]判断的注释package main // https://space.bilibili.com/206214 func missingInteger(nums []int) int { sum : nums[0] for i : 1; i len(nums) nums[i] nums[i-1]1; i { sum nums[i] } has : map[int]bool{} for _, x : range nums { has[x] true } for has[sum] { // 至多循环 n 次 sum } return sum }注意package main仓库的力扣题解都以main包组织便于直接用go test跑题解自测。4.2 测试数据与测试用例样例数据文件 a.txt 以输入一行、期望输出一行、空行分隔的格式组织正好对应上面推演的两个用例用例 1输入[1,2,3,2,5]→ 输出6用例 2输入[3,4,5,1,12,14,13]→ 输出15。测试文件 a_test.go 由模板生成器自动生成其核心只有一行调用func Test_a(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, missingInteger, a.txt, 0); err ! nil { t.Fatal(err) } }RunLeetCodeFuncWithFile定义于 leetcode/testutil/leetcode.go会读取a.txt按fNumIn fNumOut本题为 1 输入 1 输出 2 行切分组数据通过反射调用missingInteger再把实际输出与期望输出逐例比对。targetCaseNum传0表示跑全部用例传-1表示只跑最后一个用例该参数在_test.go中默认以注释形式给出可用于调试。该测试用例的题目链接记录在 a_test.go 末尾biweekly-contest-121/problems/smallest-missing-integer-greater-than-sequential-prefix-sum/。4.3 测试基础设施如何工作仓库级深度RunLeetCodeFuncWithExamplesleetcode/testutil/leetcode.go做了三件事体现了本仓库题解仓库的工程化设计解析输入parseRawArgleetcode/testutil/leetcode.go按 Go 反射类型把[1,2,3,2,5]解析为[]int把6解析为int执行并做 TLE 检测isTLEleetcode/testutil/leetcode.go在非调试环境下用带超时定时器的 goroutine 包裹被测函数若超时直接报【超时】断言输出toRawString把反射到的结果序列化成[6]或15这类字符串与期望值assert.Equal比对出错时报【答案错误 N】并打印对应输入。也就是说即便你修改了a.go里的实现只要go test ./leetcode/biweekly/121/a/仓库根目录下执行测试框架就会自动用a.txt里的官方样例做回归验证——这套README 题解 x.go实现 x.txt样例 x_test.go自动测试的四件套模式是仓库中每一道力扣题的标准形态可参考同场次 b/README.md 等其他题目目录。五、扩展思考为什么哈希集合是最优判重结构本题第二阶段本质上是在问从s开始第一个不属于nums的整数是谁。若改用数组 排序后二分查找单次判断是O(log n)总复杂度会退化到O(n log n)而哈希集合把是否包含压到均摊O(1)配合至多n次自增的结论让整体保持O(n)。从代码结构看本仓库中大量依赖集合语义的场景如 copypasta/orderedset.go、copypasta/treap 等有序集合实现处理的是需要取前驱/后继的更强操作本题只需存在性查询用map[int]bool或set即可无需引入有序结构——这是按需选择数据结构的典型范例。六、实战检验跑通仓库测试若你想在本地验证上面的完整链路仓库为只读以下均为查看与运行操作在仓库根目录含 go.mod模块名github.com/EndlessCheng/codeforces-goGo 1.23执行go test ./leetcode/biweekly/121/a/若只想调试单个用例把 a_test.go 中的targetCaseNum改为1或2分别对应a.txt中的两个样例或利用RunLeetCodeFuncWithFile的负参数约定传-1跑最后一个用例若本地没有这些文件对应的测试依赖可先go mod download拉取 go.sum 中锁定的依赖再执行测试。题解文档 README.md 末尾还附有科学刷题方法论与滑动窗口、二分、单调栈、网格图、位运算、图论、动态规划等分类题单以及仓库作者维护的题解精选列表 leetcode/SOLUTIONS.md可作为后续系统化练习的索引。总结本题的解题链非常清晰阶段一用一次线性扫描求出从nums[0]开始的最长连续递增前缀的元素和s阶段二用哈希集合从s逐次加1返回第一个不在数组中的值。时间复杂度O(n)、空间复杂度O(n)1324567这类极端样例恰好说明了至多循环n次的边界。配合仓库中 a.go、a.txt 与 a_test.go 组成的测试闭环你可以立即动手复现、修改并验证任何等价实现。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 仓库实战力扣双周赛 104「英雄的力量」贡献法递推题解全解析codeforces go 仓库实战力扣双周赛 104「英雄的力量」贡献法递推题解全解析 导读 本篇技术指南以仓库中 双周赛 104 第四题题解 https:科学计算codeforces-go 仓库实战解析双周赛 107 A 题「字符串成对反转匹配」的 O(n) 哈希解法codeforces go 仓库实战解析双周赛 107 A 题「字符串成对反转匹配」的 O n 哈希解法 本篇文章以算法竞赛模板库 codeforces go科学计算LeetCode 双周赛 101 题 A从两个数字数组生成最小数字——哈希表与位运算双解法及 codeforces-go 仓库源码剖析LeetCode 双周赛 101 题 A从两个数字数组生成最小数字——哈希表与位运算双解法及 codeforces go 仓库源码剖析 本篇技术指南以 cod科学计算上一篇VTube Studio 新手教程30分钟跑通你的第一个Live2D虚拟形象下一篇在家制作雌二醇凝胶的3个关键环节5种原料做出100ml成品创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考