科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载力扣第 174 场双周赛的第二题Q2考察的是一个典型的脑筋急转弯型结论每次操作可以把数组中所有等于某个值x的元素一次性改写成各自的目标值求最少操作次数。本文以仓库内 leetcode/biweekly/174/b/README.md 的官方题解笔记为核心完整还原从理论下界推导到可达到性证明的思维链条给出 Python / Java / C / Go 四种语言的实现与复杂度分析并结合 b.go、b_test.go、b.txt 等仓库源码说明该题的样例数据与自动化测试是如何落地的。读完本文你不仅能秒杀这道题还能掌握一类批量替换 集合计数思维的识别与证明方法。题目背景与题意拆解本题目录位于 leetcode/biweekly/174/属于力扣第 174 场双周赛Biweekly Contest 174的 Q2题面名称为Minimum Operations to Reach Target Array。整场比赛的四道题a/b/c/d都有对应的 Go 实现与测试文件本场总览见 leetcode/biweekly/174/README.md。规则描述给定两个等长数组nums和target每次操作选择一个值x把nums中所有等于x的数都改成对应的target[i]。注意nums中不等于x的数保持不变一次操作是批量的——所有等于x的位置被同时改写且改写的目标值是按位置对应的target[i]而不是统一值。官方题解给出一个直观示例设nums [1,2,1,2]target [3,4,5,6]。选择x 1操作后nums [3,2,5,2]其中不等于1的数即2保持不变需要继续操作。核心洞察答案的理论最小值题目要求最少操作次数先看一个必要条件下界。对任意位置i如果nums[i] ≠ target[i]那么nums[i]这个值至少要被选中操作一次——否则该位置的值永远不会改变也就永远到不了target[i]。注意如果两个位置都持有同一个错误值x一次选择x的操作可以同时修复它们。于是答案的理论最小值等于满足nums[i] ≠ target[i]的不同nums[i]的个数。这些不同元素各自都至少要操作一次一次操作就能覆盖所有持有该错误值的位置所以这个下界天然紧凑。可达到性证明为什么正好做到理论最小值下界有了问题在于能达到理论最小值吗答案是肯定的而且操作顺序可以很随意。把满足nums[i] ≠ target[i]的nums[i]找出来相同元素只保留一个得到集合S。按任意顺序对S中的每个值各操作一次分析关键性质一旦某个nums[i]被改成了target[i]那么后续操作即使再次选中它即后续选中的值y恰好等于当前的target[i]也只是把target[i]改成target[i]保持不变若后续选中的值y ≠ target[i]则根本不会碰这个位置。因此操作后的数不会再变——每个位置最多被改变一次S中每个元素操作一次即可全部收敛到目标数组。操作的等价视角删除而非替换既然操作后的数不会再变原题操作就等价于选择一个x删除nums中的所有等于x的数——这些数操作后都等于目标值不用再管。从这个等价视角可以立刻看出答案每次操作消灭一种不同的错误值因此最少操作次数就是满足nums[i] ≠ target[i]的不同nums[i]的个数。这也是官方题解笔记leetcode/biweekly/174/b/README.md给出的最终结论。用样例验证结论仓库中的测试数据 b.txt 恰好包含三组样例可以逐一验证numstarget错误位置不同错误值集合 S答案[1,2,3][2,1,3]第 0、1 位{1, 2}2[4,1,4][5,1,4]第 0 位{4}1[7,3,7][5,5,9]全部 3 位{7, 3}2第三组中两个7位于不同位置且都指向不同目标值但一次选择x 7的操作会同时改写这两个位置因此只计入一次。多语言实现四套解法官方题解笔记同时给出了 Python3、Java两种写法、C 和 Go 的实现核心逻辑完全一致遍历下标筛出nums[i] ! target[i]的不同nums[i]计数。Python3集合推导式一行流class Solution: def minOperations(self, nums: List[int], target: List[int]) - int: return len({x for x, t in zip(nums, target) if x ! t})JavaHashSet 写法class Solution { public int minOperations(int[] nums, int[] target) { HashSetInteger set new HashSet(); // 更快的写法见【Java 数组】 for (int i 0; i nums.length; i) { int x nums[i]; if (x ! target[i]) { set.add(x); } } return set.size(); } }Java布尔数组写法省去哈希开销class Solution { public int minOperations(int[] nums, int[] target) { int mx 0; for (int x : nums) { mx Math.max(mx, x); } boolean[] vis new boolean[mx 1]; int ans 0; for (int i 0; i nums.length; i) { int x nums[i]; if (!vis[x] x ! target[i]) { vis[x] true; ans; } } return ans; } }当nums中元素的值域较小时mx不大用boolean数组代替哈希集合可以获得更好的缓存局部性从代码结构看代价是需要先扫描一遍nums求最大值mx空间为O(mx)。Cclass Solution { public: int minOperations(vectorint nums, vectorint target) { unordered_setint st; for (int i 0; i nums.size(); i) { int x nums[i]; if (x ! target[i]) { st.insert(x); } } return st.size(); } };Go仓库中的实际提交仓库中的实现位于 leetcode/biweekly/174/b/b.go与题解笔记中的sol-Go完全一致用map[int]struct{}充当集合func minOperations(nums, target []int) int { set : map[int]struct{}{} for i, x : range nums { if x ! target[i] { set[x] struct{}{} } } return len(set) }复杂度分析时间复杂度O(n)其中n是nums的长度。只需单次线性扫描Java 数组版额外多一次求最大值的扫描仍是O(n)。空间复杂度O(n)用于存储集合。最坏情况下所有位置都不同且全部错误Java 数组版为O(mx)其中mx max(nums)。仓库源码佐证样例数据与自动化测试这道题在仓库内并非孤立存在配套的测试基础设施完整可复现。测试数据文件b.txt 以输入/输出交替、空行分隔的格式存放了三组官方样例与上表一一对应由copypasta/template/leetcode/generator.go中的writeTestDataFile见 generator.go生成。该工具会抓取力扣比赛页面的题目模板、默认代码与pre样例块自动落盘为a.go/a_test.go/a.txt等文件对应逻辑见 generator.go。测试入口b_test.go 通过testutil.RunLeetCodeFuncWithFile驱动测试func Test_b(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, minOperations, b.txt, 0); err ! nil { t.Fatal(err) } }RunLeetCodeFuncWithFile定义于 leetcode/testutil/leetcode.go其职责是读取同目录b.txt中的样例把输入参数逐一解析后调用被测函数minOperations并将返回值与期望输出比对。也就是说仓库中leetcode/biweekly/174/b/目录下的三个文件构成了完整的源码 测试驱动 样例数据闭环读者只需在该目录执行go test即可复现验证。专题训练定位贪心与思维题单从题解笔记的专题训练指引看这类题被归入贪心与思维题单中的「§5.2 脑筋急转弯」一类与滑动窗口、二分、单调栈等常规套路题不同它考察的是对操作性质的抽象能力——把批量替换等价为删除一种值再结合已就位的位置永不再变这一不变式直接得出结论。同类问题在仓库的其他比赛目录中也有大量对应实现读者可结合 leetcode/biweekly/174/README.md 中的题单总览规划系统训练。小结本题给出一类重要思维模板先证下界再证可达。具体到最小化操作次数问题关键在于识别两个性质每种错误的原值必须且只需被操作一次下界一旦某个位置达到目标值之后任何操作都不会改变它可达性。由此批量替换问题被等价为去重计数问题一行集合操作即可求解。仓库中 leetcode/biweekly/174/b/ 目录下的实现与测试数据则为这一结论提供了可直接运行验证的完整示例。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 双周赛 168Minimum Operations to Transform Array 贪心分类讨论解法剖析codeforces-go 仓库题解LeetCode 双周赛 168Minimum Operations to Transform Array 贪心分类讨论解法剖析codeforces go科学计算codeforces-go 题解精讲双指针 循环递增判定子序列力扣第 111 场双周赛 T2codeforces go 题解精讲双指针 循环递增判定子序列力扣第 111 场双周赛 T2 本文围绕算法竞赛模板库 codeforces go 中科学计算Blender 仓库内 Google Mock 自定义扩展点Customization Points深度解析从注入头文件到命令行 Flag 宏体系Blender 仓库内 Google Mock 自定义扩展点Customization Points深度解析从注入头文件到命令行 Flag 宏体系 导读科学计算上一篇5分钟解锁Listen1插件从零开始打造你的全能音乐播放器终极指南下一篇如何轻松安装Listen1音乐聚合插件5个简单步骤实现全平台音乐畅听创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/7 2:25:27 · 阅读 1.2k codeforces-go 算法题解：力扣第 174 场双周赛 T2「Minimum Operations to Reach Target Array」的脑筋急转弯解析
科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载力扣第 174 场双周赛的第二题Q2考察的是一个典型的脑筋急转弯型结论每次操作可以把数组中所有等于某个值x的元素一次性改写成各自的目标值求最少操作次数。本文以仓库内 leetcode/biweekly/174/b/README.md 的官方题解笔记为核心完整还原从理论下界推导到可达到性证明的思维链条给出 Python / Java / C / Go 四种语言的实现与复杂度分析并结合 b.go、b_test.go、b.txt 等仓库源码说明该题的样例数据与自动化测试是如何落地的。读完本文你不仅能秒杀这道题还能掌握一类批量替换 集合计数思维的识别与证明方法。题目背景与题意拆解本题目录位于 leetcode/biweekly/174/属于力扣第 174 场双周赛Biweekly Contest 174的 Q2题面名称为Minimum Operations to Reach Target Array。整场比赛的四道题a/b/c/d都有对应的 Go 实现与测试文件本场总览见 leetcode/biweekly/174/README.md。规则描述给定两个等长数组nums和target每次操作选择一个值x把nums中所有等于x的数都改成对应的target[i]。注意nums中不等于x的数保持不变一次操作是批量的——所有等于x的位置被同时改写且改写的目标值是按位置对应的target[i]而不是统一值。官方题解给出一个直观示例设nums [1,2,1,2]target [3,4,5,6]。选择x 1操作后nums [3,2,5,2]其中不等于1的数即2保持不变需要继续操作。核心洞察答案的理论最小值题目要求最少操作次数先看一个必要条件下界。对任意位置i如果nums[i] ≠ target[i]那么nums[i]这个值至少要被选中操作一次——否则该位置的值永远不会改变也就永远到不了target[i]。注意如果两个位置都持有同一个错误值x一次选择x的操作可以同时修复它们。于是答案的理论最小值等于满足nums[i] ≠ target[i]的不同nums[i]的个数。这些不同元素各自都至少要操作一次一次操作就能覆盖所有持有该错误值的位置所以这个下界天然紧凑。可达到性证明为什么正好做到理论最小值下界有了问题在于能达到理论最小值吗答案是肯定的而且操作顺序可以很随意。把满足nums[i] ≠ target[i]的nums[i]找出来相同元素只保留一个得到集合S。按任意顺序对S中的每个值各操作一次分析关键性质一旦某个nums[i]被改成了target[i]那么后续操作即使再次选中它即后续选中的值y恰好等于当前的target[i]也只是把target[i]改成target[i]保持不变若后续选中的值y ≠ target[i]则根本不会碰这个位置。因此操作后的数不会再变——每个位置最多被改变一次S中每个元素操作一次即可全部收敛到目标数组。操作的等价视角删除而非替换既然操作后的数不会再变原题操作就等价于选择一个x删除nums中的所有等于x的数——这些数操作后都等于目标值不用再管。从这个等价视角可以立刻看出答案每次操作消灭一种不同的错误值因此最少操作次数就是满足nums[i] ≠ target[i]的不同nums[i]的个数。这也是官方题解笔记leetcode/biweekly/174/b/README.md给出的最终结论。用样例验证结论仓库中的测试数据 b.txt 恰好包含三组样例可以逐一验证numstarget错误位置不同错误值集合 S答案[1,2,3][2,1,3]第 0、1 位{1, 2}2[4,1,4][5,1,4]第 0 位{4}1[7,3,7][5,5,9]全部 3 位{7, 3}2第三组中两个7位于不同位置且都指向不同目标值但一次选择x 7的操作会同时改写这两个位置因此只计入一次。多语言实现四套解法官方题解笔记同时给出了 Python3、Java两种写法、C 和 Go 的实现核心逻辑完全一致遍历下标筛出nums[i] ! target[i]的不同nums[i]计数。Python3集合推导式一行流class Solution: def minOperations(self, nums: List[int], target: List[int]) - int: return len({x for x, t in zip(nums, target) if x ! t})JavaHashSet 写法class Solution { public int minOperations(int[] nums, int[] target) { HashSetInteger set new HashSet(); // 更快的写法见【Java 数组】 for (int i 0; i nums.length; i) { int x nums[i]; if (x ! target[i]) { set.add(x); } } return set.size(); } }Java布尔数组写法省去哈希开销class Solution { public int minOperations(int[] nums, int[] target) { int mx 0; for (int x : nums) { mx Math.max(mx, x); } boolean[] vis new boolean[mx 1]; int ans 0; for (int i 0; i nums.length; i) { int x nums[i]; if (!vis[x] x ! target[i]) { vis[x] true; ans; } } return ans; } }当nums中元素的值域较小时mx不大用boolean数组代替哈希集合可以获得更好的缓存局部性从代码结构看代价是需要先扫描一遍nums求最大值mx空间为O(mx)。Cclass Solution { public: int minOperations(vectorint nums, vectorint target) { unordered_setint st; for (int i 0; i nums.size(); i) { int x nums[i]; if (x ! target[i]) { st.insert(x); } } return st.size(); } };Go仓库中的实际提交仓库中的实现位于 leetcode/biweekly/174/b/b.go与题解笔记中的sol-Go完全一致用map[int]struct{}充当集合func minOperations(nums, target []int) int { set : map[int]struct{}{} for i, x : range nums { if x ! target[i] { set[x] struct{}{} } } return len(set) }复杂度分析时间复杂度O(n)其中n是nums的长度。只需单次线性扫描Java 数组版额外多一次求最大值的扫描仍是O(n)。空间复杂度O(n)用于存储集合。最坏情况下所有位置都不同且全部错误Java 数组版为O(mx)其中mx max(nums)。仓库源码佐证样例数据与自动化测试这道题在仓库内并非孤立存在配套的测试基础设施完整可复现。测试数据文件b.txt 以输入/输出交替、空行分隔的格式存放了三组官方样例与上表一一对应由copypasta/template/leetcode/generator.go中的writeTestDataFile见 generator.go生成。该工具会抓取力扣比赛页面的题目模板、默认代码与pre样例块自动落盘为a.go/a_test.go/a.txt等文件对应逻辑见 generator.go。测试入口b_test.go 通过testutil.RunLeetCodeFuncWithFile驱动测试func Test_b(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, minOperations, b.txt, 0); err ! nil { t.Fatal(err) } }RunLeetCodeFuncWithFile定义于 leetcode/testutil/leetcode.go其职责是读取同目录b.txt中的样例把输入参数逐一解析后调用被测函数minOperations并将返回值与期望输出比对。也就是说仓库中leetcode/biweekly/174/b/目录下的三个文件构成了完整的源码 测试驱动 样例数据闭环读者只需在该目录执行go test即可复现验证。专题训练定位贪心与思维题单从题解笔记的专题训练指引看这类题被归入贪心与思维题单中的「§5.2 脑筋急转弯」一类与滑动窗口、二分、单调栈等常规套路题不同它考察的是对操作性质的抽象能力——把批量替换等价为删除一种值再结合已就位的位置永不再变这一不变式直接得出结论。同类问题在仓库的其他比赛目录中也有大量对应实现读者可结合 leetcode/biweekly/174/README.md 中的题单总览规划系统训练。小结本题给出一类重要思维模板先证下界再证可达。具体到最小化操作次数问题关键在于识别两个性质每种错误的原值必须且只需被操作一次下界一旦某个位置达到目标值之后任何操作都不会改变它可达性。由此批量替换问题被等价为去重计数问题一行集合操作即可求解。仓库中 leetcode/biweekly/174/b/ 目录下的实现与测试数据则为这一结论提供了可直接运行验证的完整示例。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 双周赛 168Minimum Operations to Transform Array 贪心分类讨论解法剖析codeforces-go 仓库题解LeetCode 双周赛 168Minimum Operations to Transform Array 贪心分类讨论解法剖析codeforces go科学计算codeforces-go 题解精讲双指针 循环递增判定子序列力扣第 111 场双周赛 T2codeforces go 题解精讲双指针 循环递增判定子序列力扣第 111 场双周赛 T2 本文围绕算法竞赛模板库 codeforces go 中科学计算Blender 仓库内 Google Mock 自定义扩展点Customization Points深度解析从注入头文件到命令行 Flag 宏体系Blender 仓库内 Google Mock 自定义扩展点Customization Points深度解析从注入头文件到命令行 Flag 宏体系 导读科学计算上一篇5分钟解锁Listen1插件从零开始打造你的全能音乐播放器终极指南下一篇如何轻松安装Listen1音乐聚合插件5个简单步骤实现全平台音乐畅听创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考