科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以 leetcode/biweekly/111/c/README.md 的官方题解为骨架完整讲解「将三个组排序Sorting Three Groups」这道经典值域 DP 题的三类解法二分优化的最长非递减子序列、以值域为维度的多维 DP 及其空间优化、以及竞赛中常用的「合法子序列 DP」套路。同时结合 codeforces-go 仓库中 c.go 的四个真实实现、c_test.go 的自动化测试与 copypasta/dp.go 的 LIS 模板从原理到代码到验证给出完整闭环读完你不仅能秒掉本题还能把「非递减子序列」「值域维度 DP」「合法子序列 DP」三个技能点迁移到同类题目中。题目背景与分析思路正难则反给定一个只含 $1、2、3$ 三种值的数组 $\textit{nums}$每次操作可以把任意一个元素改成任意值只能是 $1、2、3$ 之一问最少操作多少次能把数组变成非递减的即形如 $1,\dots,1,2,\dots,2,3,\dots,3$ 的模式。直接计算「最少改多少个」并不直观官方题解给出关键思维定式正难则反计算最多保留多少个。保留下来的数必须是非递减的且它们原本就是有序的其余数全部改掉即可。于是答案 $n - \text{最长非递减子序列长度}$其中 $n$ 为 $\textit{nums}$ 长度。原数组只有三种取值值域极小$U3$这既支持 $\mathcal{O}(n\log n)$ 的通用 LNDS 解法也催生了两种把值域当 DP 维度的 $\mathcal{O}(nU)$ 解法——这正是本文要展开的三条主线。方法一最长非递减子序列LNDS$\mathcal{O}(n\log n)$前置知识是 300. 最长递增子序列 的贪心 二分做法维护一个递增数组 $g$对每个 $x$用二分找到第一个 $\ge x$严格递增 LIS的位置并替换本题要求非递减即允许相等因此把查找目标从 $x$ 改为 $x1$等价于找第一个 $x$ 的位置。$g$ 的长度就是最长非递减子序列长度。class Solution: def minimumOperations(self, nums: List[int]) - int: g [] for x in nums: j bisect_right(g, x) if j len(g): g.append(x) else: g[j] x return len(nums) - len(g)class Solution { public int minimumOperations(ListInteger nums) { ListInteger g new ArrayList(); for (int x : nums) { int j upperBound(g, x); if (j g.size()) { g.add(x); } else { g.set(j, x); } } return nums.size() - g.size(); } // 开区间写法 private int upperBound(ListInteger g, int target) { int left -1, right g.size(); // 开区间 (left, right) while (left 1 right) { // 区间不为空 // 循环不变量 // nums[left] target // nums[right] target int mid (left right) 1; if (g.get(mid) target) { right mid; // 范围缩小到 (left, mid) } else { left mid; // 范围缩小到 (mid, right) } } return right; } }class Solution { public: int minimumOperations(vectorint nums) { vectorint g; for (int x : nums) { auto it ranges::upper_bound(g, x); if (it g.end()) { g.push_back(x); } else { *it x; } } return nums.size() - g.size(); } };func minimumOperations(nums []int) int { g : []int{} for _, x : range nums { p : sort.SearchInts(g, x1) if p len(g) { g[p] x } else { g append(g, x) } } return len(nums) - len(g) }复杂度分析时间复杂度$\mathcal{O}(n\log n)$其中 $n$ 为 $\textit{nums}$ 的长度。空间复杂度$\mathcal{O}(n)$。仓库佐证LIS 模板与本题实现的对应这套写法在本仓库里并非孤例。在 copypasta/dp.go 的算法模板库中就内置了完全一致的 LIS 贪心二分实现注释明确写道lis : func(a []int) int { f : []int{} for _, v : range a { j : sort.SearchInts(f, v) // v 是严格递增改成 v1 是非严格递增 if j len(f) { f[j] v } else { f append(f, v) } } return len(f) }sort.SearchInts(f, v)找的是第一个 $\ge v$ 的下标严格递增场景把参数改成v1即找第一个 $v$ 的下标等价于bisect_right/upper_bound从而把「最长递增子序列」平滑升级为「最长非递减子序列」。对照 c.go 中的minimumOperations1正是这一模板的逐字应用func minimumOperations1(nums []int) int { g : []int{} for _, x : range nums { p : sort.SearchInts(g, x1) // x1非递减 if p len(g) { g[p] x } else { g append(g, x) } } return len(nums) - len(g) }这个模板可以继续推广到任意值域无论元素取值多大只要目标是「非递减」把二分查找参数1即可因而方法一是三种解法中唯一不受值域限制、可无缝迁移到一般整数数组的方案。方法二多维 DP以值域为维度$\mathcal{O}(nU)$由于值域很小只有 $1、2、3$把值域当作 DP 的一个维度可以得到另一种思路。状态定义与转移定义 $f[i1][j]$ 表示 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 的最长非递减子序列的长度其中子序列最后一个数 $\le j$。设 $x\textit{nums}[i]$分类讨论不选 $x$问题变成 $\textit{nums}[0]$ 到 $\textit{nums}[i-1]$ 的最长非递减子序列的长度其中子序列最后一个数 $\le j$即 $f[i1][j] f[i][j]$。选 $x$把 $x$ 当作子序列最后一个数需满足 $x\le j$。问题变成 $\textit{nums}[0]$ 到 $\textit{nums}[i-1]$ 的最长非递减子序列的长度其中子序列最后一个数 $\le x$即 $f[i1][j] f[i][x] 1$。两种情况取最大值$$ f[i1][j] \begin{cases} f[i][j], j x \ \max(f[i][j], f[i][x] 1), j\ge x \ \end{cases} $$初始值 $f[0][j] 0$答案为 $n - f[n][3]$。优化前二维数组版本class Solution: def minimumOperations(self, nums: List[int]) - int: n len(nums) f [[0] * 4 for _ in range(n 1)] for i, x in enumerate(nums): for j in range(1, 4): if j x: f[i 1][j] f[i][j] else: f[i 1][j] max(f[i][j], f[i][x] 1) return n - f[n][3]class Solution { public int minimumOperations(ListInteger nums) { int n nums.size(); int[][] f new int[n 1][4]; for (int i 0; i n; i) { int x nums.get(i); for (int j 1; j 3; j) { if (j x) { f[i 1][j] f[i][j]; } else { f[i 1][j] Math.max(f[i][j], f[i][x] 1); } } } return n - f[n][3]; } }class Solution { public: int minimumOperations(vectorint nums) { int n nums.size(); vectorarrayint, 4 f(n 1); for (int i 0; i n; i) { int x nums[i]; for (int j 1; j 3; j) { if (j x) { f[i 1][j] f[i][j]; } else { f[i 1][j] max(f[i][j], f[i][x] 1); } } } return n - f[n][3]; } };func minimumOperations(nums []int) int { n : len(nums) f : make([][4]int, n1) for i, x : range nums { for j : 1; j 3; j { if j x { f[i1][j] f[i][j] } else { f[i1][j] max(f[i][j], f[i][x]1) } } } return n - f[n][3] }仓库中对应实现是 c.go 的minimumOperations2与上面的 Go 版本逐行一致。空间优化去掉第一个维度去掉第一个维度转移简化为$$ f[j] \begin{cases} f[j], j x \ \max(f[j], f[x] 1), j\ge x \ \end{cases} $$把 $\texttt{for}$ 循环展开就得到一个极为优雅的常数级更新序列先把 $f[x]$ 加一然后更新 $f[2] \max(f[2], f[1])$若 $x1$则 $f[2]$ 不变然后更新 $f[3] \max(f[3], f[2])$若 $x2$则 $f[3]$ 不变。class Solution: def minimumOperations(self, nums: List[int]) - int: f [0] * 4 for x in nums: f[x] 1 f[2] max(f[2], f[1]) f[3] max(f[3], f[2]) return len(nums) - f[3]class Solution { public int minimumOperations(ListInteger nums) { int[] f new int[4]; for (int x : nums) { f[x]; f[2] Math.max(f[2], f[1]); f[3] Math.max(f[3], f[2]); } return nums.size() - f[3]; } }class Solution { public: int minimumOperations(vectorint nums) { int f[4]{}; for (int x: nums) { f[x]; f[2] max(f[2], f[1]); f[3] max(f[3], f[2]); } return nums.size() - f[3]; } };func minimumOperations(nums []int) int { f : [4]int{} for _, x : range nums { f[x] f[2] max(f[2], f[1]) f[3] max(f[3], f[2]) } return len(nums) - f[3] }仓库中 c.go 的minimumOperations3就是这个空间优化版本。复杂度分析时间复杂度$\mathcal{O}(nU)$其中 $n$ 为 $\textit{nums}$ 的长度$U\max(\textit{nums})3$。空间复杂度$\mathcal{O}(U)$。从代码量看空间优化版每轮只做「一次加一、两次取 max」是四份实现中最短也最不易写错的一个。方法三合法子序列 DP$\mathcal{O}(nU)$官方题解指出这是一个固定套路见动态规划题单中的「§7.2 合法子序列 DP」。套路模板一般定义 $f[x]$ 表示以元素 $x$ 结尾的合法子序列的最长长度 / 个数 / 元素和从子序列的倒数第二个数转移过来。本题倒数第二个数记作 $j$那么必须满足 $j\le x$。转移方程为$$ f[x] \max_{j1}^{x} f[j] 1 $$其中 $1$ 表示在以 $j$ 结尾的子序列末尾添加一个 $x$得到以 $x$ 结尾的子序列。初始值 $f[x] 0$答案为 $n - \max(f)$。class Solution: def minimumOperations(self, nums: List[int]) - int: f [0] * 4 for x in nums: f[x] max(f[1: x 1]) 1 return len(nums) - max(f)class Solution { public int minimumOperations(ListInteger nums) { int[] f new int[4]; for (int x : nums) { int mx 0; for (int j 1; j x; j) { mx Math.max(mx, f[j]); } f[x] mx 1; } return nums.size() - Arrays.stream(f).max().getAsInt(); } }class Solution { public: int minimumOperations(vectorint nums) { int f[4]{}; for (int x : nums) { f[x] *max_element(f 1, f x 1) 1; } return nums.size() - ranges::max(f); } };func minimumOperations(nums []int) int { f : [4]int{} for _, x : range nums { f[x] slices.Max(f[1:x1]) 1 } return len(nums) - slices.Max(f[:]) }仓库中 c.go 的minimumOperations即被测试的主函数正是这一写法使用 Go 1.21 标准库的slices.Max完成前缀最大值// https://space.bilibili.com/206214 func minimumOperations(nums []int) int { f : [4]int{} for _, x : range nums { f[x] slices.Max(f[1:x1]) 1 } return len(nums) - slices.Max(f[:]) }复杂度分析时间复杂度$\mathcal{O}(nU)$其中 $n$ 为 $\textit{nums}$ 的长度$U\max(\textit{nums})3$。空间复杂度$\mathcal{O}(U)$。三种方法的本质联系把三种做法放在一起看它们的共性清晰可见方法视角复杂度核心操作方法一 LNDS 二分通用子序列不限值域$\mathcal{O}(n\log n)$ / $\mathcal{O}(n)$upper_bound(g, x)替换方法二 多维 DP值域当维度选/不选当前元素$\mathcal{O}(nU)$ / $\mathcal{O}(U)$$f[x]1$ 后做两次前缀 max方法三 合法子序列 DP以「倒数第二个数」转移$\mathcal{O}(nU)$ / $\mathcal{O}(U)$$f[x]\max_{j\le x}f[j]1$方法二的空间优化版本与方法三在形式上已经高度接近区别仅在于方法二先f[x]再逐级做前缀 max保证 $f[x]$ 自己也能参与后续转移方法三直接对前缀取最大值再加一。两条推导路径殊途同归都受益于值域 $U3$ 极小这一前提。仓库实现与自动化测试佐证四个实现与三种解法一一对应leetcode/biweekly/111/c 目录下官方题解的三种解法被完整落地为四个 Go 函数命名按版本编号minimumOperations1c.go方法一二分 LNDS$\mathcal{O}(n\log n)$minimumOperations2c.go方法二优化前二维 DPminimumOperations3c.go方法二空间优化一维 DPminimumOperationsc.go方法三合法子序列 DP即本题的主解法也是测试入口。测试用例与测试框架仓库为本题配备了数据驱动测试。用例文件 c.txt 中存放了三组「输入 / 期望输出」[2,1,3,2,1] 3 [1,3,2,1,3,3] 2 [2,2,2,2,3,3] 0输入[2,1,3,2,1]保留 $2,3$或 $1,3$等非递减子序列最多保留 $2$ 个故需改 $5-23$ 个输入[1,3,2,1,3,3]最长非递减子序列长度为 $4$如 $1,2,3,3$故需改 $6-42$ 个输入[2,2,2,2,3,3]$本身已非递减答案 $0$。测试驱动由 c_test.go 完成它通过反射调用被测函数func Test_c(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, minimumOperations, c.txt, targetCaseNum); err ! nil { t.Fatal(err) } }RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go其工作流程为读取c.txt→ 按「函数入参个数 出参个数」切分每行数据为一组用例 → 用reflect反射调用被测函数 → 逐组比对期望输出。因此仓库中的测试相当于对官方题解的三种解法做了一次完整的交叉验证任何一份实现与c.txt中的三组答案不一致go test都会立刻失败。如果你在自己的 Go 工程里复现本题可以直接复用这套模式把minimumOperations放进main包、在包内放置c.txt用例文件再复制c_test.go的驱动代码运行go test即可获得与仓库一致的数据驱动验证体验当然直接去 LeetCode 提交对应的sol-Go代码同样可行。总结与迁移指南回顾本题最有价值的收获有三点正难则反求「最少修改次数」时先想「最多能保留多少」答案通常等于 $n - \text{保留数}$。这个技巧在「使数组有序」「使数组相等」「分组排序」类题目中反复出现。LIS 二分模板的 1 技巧upper_bound/bisect_right/SearchInts(g, x1)三者的等价关系见 copypasta/dp.go 的模板注释把严格递增直接改成非递减一条注释即可应对一类题。合法子序列 DP 套路当元素取值域很小时本题 $U3$把「以 $x$ 结尾的合法子序列最优值」作为状态从倒数第二个数转移配合前缀 max 优化往往能得到代码极短的 $\mathcal{O}(nU)$ 解法——这正是动态规划题单中「§7.2 合法子序列 DP」一节的通用模板可复用于计数、最长、最值等多种子序列问题。无论选择 $\mathcal{O}(n\log n)$ 的通用 LNDS还是 $\mathcal{O}(nU)$ 的两种值域 DP最终都收敛于同一个结论答案 数组长度 − 最长非递减子序列长度。理解这三条路径背后的等价性比背下某一版代码更有价值。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐第 124 场力扣双周赛 T4 题解排序 子序列 DP 求解「修改后数组的最大连续元素个数」第 124 场力扣双周赛 T4 题解排序 子序列 DP 求解「修改后数组的最大连续元素个数」 本篇题解以 leetcode/biweekly/124/d/科学计算子序列 DP 的「枚举选哪个」与「值域 DP」力扣 115 场双周赛 T3「最长不等相邻组子序列 II」详解codeforces-go 实战子序列 DP 的「枚举选哪个」与「值域 DP」力扣 115 场双周赛 T3「最长不等相邻组子序列 II」详解codeforces go 实战 本篇以力扣第科学计算容斥原理与正难则反LeetCode 双周赛 117 第三题 stringCount 的 O(log n) 计数解法容斥原理与正难则反LeetCode 双周赛 117 第三题 stringCount 的 O log n 计数解法 导读 本题是 LeetCode 第 117科学计算上一篇Summarize模型自动选择原理从API密钥到本地CLI的智能 fallback 策略下一篇Nuclide折叠状态共享团队代码浏览体验一致化创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考