力扣双周赛 172 全题解：从二维 0-1 背包到 O(1) 位运算（基于 codeforces-go 算法模板库）-北京尧图网络

科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以 leetcode/biweekly/172/README.md 为核心完整复盘力扣第 172 场双周赛的四道题目Q1 去重最少操作、Q2 可被三整除的三数最大和、Q3 二进制交换后的最大分数、Q4 交替删除后的最后整数。四题分别覆盖「哈希去重」「二维 0-1 背包」「堆贪心」「等差数列模拟与位运算」四类高频算法考点每道题都给出 Python/Java/C/Go 多语言解法。读完本文你将掌握将计数约束转化为背包状态、用堆维护动态前 k 大、以及用等差数列性质把 O(n) 模拟压缩为 O(log n) 乃至 O(1) 的完整实战套路。比赛概览与仓库文件结构本仓库将每场双周赛按题号分目录存放主索引文档 leetcode/biweekly/172/README.md 列出四道题目的题解链接与视频讲解而每题的详细推导、多语言代码位于子目录中题目仓库文件核心考点Q1 使数组元素互不相同的最少操作次数leetcode/biweekly/172/a/README.md哈希集合、一次遍历Q2 可被三整除的三数最大和leetcode/biweekly/172/b/README.md、b/b.go恰好装满型二维 0-1 背包Q3 二进制交换后的最大分数leetcode/biweekly/172/c/README.md、c/c.go堆优先队列贪心Q4 交替删除操作后剩余的最后整数leetcode/biweekly/172/d/README.md、d/d.go等差数列模拟、位运算 O(1)每个题解目录同时包含*_test.go测试文件与*.txt样例数据例如 b/b_test.go、c/c_test.go、d/d_test.go测试文件均由 copypasta/template/leetcode/generator_test.go 自动生成通过 leetcode/testutil 提供的RunLeetCodeFuncWithFile驱动可直接go test验证全部样例。Q1使数组元素互不相同的最少操作次数哈希去重题目理解每次操作可以删除数组最前面的若干元素按题目定义一次操作删除前 3 个元素目标是让剩余的元素互不相同求最少操作次数。子目录 a/README.md 明确指出本题与 3396 号题完全一致属于「一次遍历」的经典送分题。核心思路从右往左找第一个重复位置正向思考很难直接确定要删多少反向思考则清晰只要从后往前扫描用哈希集合记录已经见过的元素一旦发现某个元素在右侧已经出现过说明它必须被删除而它左侧的所有元素连同它自己都处在需要删除的前缀区间内。具体地从n-1往0遍历维护一个set若nums[i]已在set中记录i为最靠左的重复起点继续向左扫描取最靠左的重复位置否则把nums[i]加入set。删除量就是「最靠左的重复位置及其左侧所有元素」再按每次删除 3 个的规则向上取整得到最少操作次数。时间复杂度O(n)一次遍历空间复杂度O(n)哈希集合。这道题的价值在于训练正难则反的遍历方向选择需要删除前缀时后缀的唯一性天然适合从尾部扫描判定。Q2可被三整除的三数最大和恰好装满型二维 0-1 背包这是本场比赛的重头戏。b/README.md 给出的建模思路非常精妙把每个x nums[i]看成一个体积为 (1, x)、价值为 x 的物品其中第一类体积为 1代表选了一个数第二类体积为 x代表数值本身。题目要求恰好选 3 个数且选出的元素和是 3 的倍数——这正是「恰好装满型」二维 0-1 背包。状态定义与转移方程参考经典题 474「一和零」的状态设计定义f[i1][j][r]在下标[0, i]中选元素恰好选了j个数元素和模 3 为r时所选元素之和的最大值。对当前元素x nums[i]讨论选或不选不选 x继承f[i][j][r]选 x从f[i][j-1][(r-x) mod 3]转移而来并加上价值x。二者取最大值f[i1][j][r] max(f[i][j][r], f[i][j-1][(r-x) mod 3] x)初始状态f[0][0][0] 0其余f[0][j][r] -∞一开始没选任何数只有j r 0合法。答案取f[n][3][0]——恰好选 3 个数且元素和模 3 为 0 的最大值若f[n][3][0] 0说明无解返回 0。由于转移只依赖i和i1两层第一维可以滚动优化掉实现时对j采用倒序循环防止同一个元素被重复选择。写法一查表法拉式 DP用「当前状态由哪个先前状态推来」的视角对每个x倒序更新jfunc maximumSum(nums []int) int { const K 3 const MOD 3 f : [K 1][MOD]int{} for i : range f { for j : range f[i] { f[i][j] math.MinInt } } f[0][0] 0 for _, x : range nums { for j : K; j 0; j-- { for r : range MOD { f[j][r] max(f[j][r], f[j-1][(r-x%MODMOD)%MOD]x) } } } return max(f[K][0], 0) }注意 Go/Java/C 写法中(r - x%MOD MOD) % MOD的细节保证取模结果非负。在 Go 中负数取模结果仍为负数-1 % 3 -1直接用作数组下标会越界因此必须先加MOD再取模。这份代码与 b/b.go 中的maximumSum完全一致。写法二刷表法推式 DP反过来用「当前状态f[j][r]去更新未来状态f[j1][(rx) mod 3]」即为刷表法。j仍需倒序枚举保证每个物品至多使用一次func maximumSum2(nums []int) int { const K 3 const MOD 3 f : [K 1][MOD]int{} for i : range f { for j : range f[i] { f[i][j] math.MinInt } } f[0][0] 0 for _, x : range nums { for j : K - 1; j 0; j-- { for r : range MOD { f[j1][(rx)%MOD] max(f[j1][(rx)%MOD], f[j][r]x) } } } return max(f[K][0], 0) }两种写法对应 b/b.go 中的maximumSum与maximumSum2结果一致。刷表法的好处是转移方向直观适合写成从已有状态推出新状态的递推风格。复杂度分析时间复杂度O(n·K·M)其中 n 为nums长度K3 为目标子序列长度M3 为模数空间复杂度O(K·M)两个维度都是常数因此整体 O(n) 时间、O(1) 额外空间。关联题目与训练方向本题是「恰好装满型」背包的绝佳范例。原文档给出两个推荐延伸经典题 [474. 一和零]二维 0-1 背包入门与 [1262. 可被三整除的最大和]同模数但选择数量不限的变体。在仓库的 copypasta 动态规划模板中也可以找到一维/多维背包状态压缩的通用实现思路可对照学习恰好装满的-∞初始化技巧。Q3二进制交换后的最大分数堆贪心本题给出数组nums与二进制串s。把s[i] 1理解成一根指向nums[i]的红色箭头一次操作相当于把一根箭头向左移一个单位若左边有空位目标是最优化被箭头最终指向的元素之和。c/README.md 给出了两个方向的贪心解法。方法一从左到右最大堆第一根箭头只能落在最左侧它可选择的数是[2,1]以示例nums[2,1,5,2,3],s01010为例贪心选最大者 2第二根箭头可选的数包括[5,2]以及前面剩下的 1贪心选最大者 5答案 257。这个过程需要一种数据结构支持添加遍历过的元素、查询最大值、删除最大值——最大堆是最自然的选择。扫描到s[i]1时从堆中弹出当前最大值计入答案func maximumScore(nums []int, s string) (ans int64) { h : hp{} for i, x : range nums { heap.Push(h, x) if s[i] 1 { ans int64(heap.Pop(h).(int)) } } return } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] h.IntSlice[j] } func (h *hp) Push(v any) { h.IntSlice append(h.IntSlice, v.(int)) } func (h *hp) Pop() any { a : h.IntSlice; v : a[len(a)-1]; h.IntSlice a[:len(a)-1]; return v }这里通过自定义Less把标准库最小堆改造成最大堆Go 中没有内置最大堆封装hp的写法与 c/c.go 一致。在 Python 中则取相反数入堆来模拟最大堆。时间复杂度O(n·log k₀)k₀ 为s中0的个数空间复杂度O(k₀)。方法二从右到左最小堆箭头只能左移不能右移因此最右边箭头右侧的数永远无法被选中。倒着遍历时每个元素都可能被「当前已遇到的所有箭头」选择问题转化为在倒序遍历中维护前 k 大元素之和其中 k 是已遍历过的s[i]1的个数。先让nums[i]入堆若s[i]1箭头数加一无需额外操作否则s[i]0把堆顶当前最小值弹出因为它不可能被任何箭头选中。Go 实现含一次heap.Fix的优化写法直接用新值替换堆顶func maximumScore2(nums []int, s string) (ans int64) { h : hp2{} for i, x : range slices.Backward(nums) { if s[i] 1 { ans int64(x) heap.Push(h, x) } else if h.Len() 0 x h.IntSlice[0] { ans int64(x - h.IntSlice[0]) h.IntSlice[0] x heap.Fix(h, 0) } } return }这一版利用slices.Backward倒序遍历并在x 堆顶最小值时直接替换堆顶并heap.Fix省去一次入堆出堆常数更小对应 c/c.go 的maximumScore2。时间复杂度O(n·log k₁)k₁ 为s中1的个数空间复杂度O(k₁)。小结左右两个方向揭示了同一问题的两种视角正向贪心用「最大堆取当前最优」反向贪心用「最小堆淘汰当前最差」本质都是维护动态前缀/后缀的 top-k。仓库 copypasta/heap.go 中提供了更多自定义堆的封装可复用其中的类型定义加速比赛写题。Q4交替删除操作后剩余的最后整数等差数列模拟位运算初始序列为1,2,...,n第一轮从左侧删除所有奇数下标第二轮从右侧删除所有奇数下标如此左右交替直到剩一个数为止。d/README.md 给出了两条路径其中第二条把复杂度压到 O(1)是全场最亮眼的结论。方法一等差数列模拟O(log n)以n8为例观察操作流程[1,2,3,4,5,6,7,8]首项 1公差 1删除奇数下标得[1,3,5,7]反转为[7,5,3,1]首项 7公差 -2反转后下一次删除仍等价于从左侧删删除奇数下标得[7,3]反转为[3,7]首项 3公差 4删除奇数下标得[3]。由此提炼出四条不变量每次删除⌊n/2⌋个元素序列长度从 n 变为⌈n/2⌉间隔删除等差数列的元素结果仍是等差数列公差初始d1每次操作d * -2反转带来符号翻转间隔带来倍数翻倍若 n 为奇数末元素保留新首项start (n-1)·d若 n 为偶数倒数第二个元素保留新首项start (n-2)·d。两者可合并为start (n-2 n%2)·d。func lastInteger1(n int64) int64 { start, d : int64(1), int64(1) // 等差数列首项公差 for ; n 1; n (n 1) / 2 { start (n - 2 n%2) * d d * -2 } return start }每轮 n 减半故时间复杂度 O(log n)空间 O(1)。此实现与 d/d.go 的lastInteger1相同。Python 侧还有一个优雅的写法直接用range对象模拟——range本身是等差数列对象切片r r[::2][::-1]可在 O(1) 时间内通过数学公式完成不必真实构造列表。方法二位运算O(1)为方便推导把序列改为从 0 开始0,1,...,n-1。第一次操作删除所有奇数剩余都是偶数说明最终答案的最低位一定是 0把剩余元素全部右移一位又得到0,1,2,...在此基础上执行第二次操作第二次操作从右往左删删除结果由「序列最后一个数即(n-1)1的奇偶性」决定——最后一个数是偶数则删奇数、剩偶数是奇数则删偶数、剩奇数。也就是说最终答案的次低位一定等于n-1的次低位依此类推从低到高第 1,3,5,... 位恒为 0第 2,4,6,... 位恒等于n-1的对应位。因此最终答案0 起始就是把n-1的偶数位第 2、4、6... 位取出再整体加 1 还原为 1 起始的编号。用掩码0xAAAAAAAAAAAAAAA二进制...1010一步完成func lastInteger(n int64) int64 { const mask 0xAAAAAAAAAAAAAAA // ...1010 return (n-1)mask 1 // 取出 n-1 的从低到高第 2,4,6,... 位最后再加一从 1 开始 }时间复杂度O(1)空间复杂度O(1)。这份实现与 d/d.go 的lastInteger完全一致代码中注释https://oeis.org/A090569还指出了该结果对应的整数序列编号。作为对比本题与经典的 [390. 消除游戏] 同源——390 题同样是左右交替间隔删除只是方向恰好相反可一并练习。测试验证用仓库测试框架跑通全部样例本仓库的每题目录都配有自动生成的测试文件与样例数据例如b/b_test.go 调用testutil.RunLeetCodeFuncWithFile(t, maximumSum, b.txt, 0)c/c_test.go 调用maximumScore与c.txtd/d_test.go 调用lastInteger与d.txt。RunLeetCodeFuncWithFile由 leetcode/testutil 提供会读取同目录的*.txt样例文件每组输入/期望输出对目标函数逐组比对。这些测试由 copypasta/template/leetcode/generator_test.go 的模板生成器产出——仓库的模板体系支持从题号、样例文件自动生成测试骨架这也是该模板库的日常工作流之一。在本仓库根目录下可直接运行验证需要 Go 环境与go.mod依赖就绪go test ./leetcode/biweekly/172/b ./leetcode/biweekly/172/c ./leetcode/biweekly/172/d总结力扣双周赛 172 的四道题串起了一条完整的从基础到奥妙的算法链Q1用一次反向遍历解决前缀删除问题训练遍历方向的直觉Q2把恰好 k 个和模 3的约束拆成二维 0-1 背包展示状态压缩与-∞初始化、以及查表/刷表两种 DP 风格Q3用最大堆/最小堆两个方向实现同构贪心说明动态前 k 大问题的堆化通解Q4先用等差数列不变量把模拟降到 O(log n)再借位运算规律直达 O(1)是全场的思维高潮。上述四题的多语言题解、Go 实现与测试数据都已完整收录在本仓库的 leetcode/biweekly/172 目录下可以作为赛后复盘、模板复习与面试冲刺的直接素材。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 139最大序列值——二维 0-1 背包前后缀分解的 Go 实战解析codeforces-go 仓库力扣双周赛 139最大序列值——二维 0 1 背包前后缀分解的 Go 实战解析codeforces go 仓库导读本题LeetCode 双周赛科学计算actions-runner-controller 指标暴露Exposing Metrics方案解析从设计决策到 gha_controller / gha_ 系列指标的采集实战actions runner controller 指标暴露Exposing Metrics方案解析从设计决策到 gha_controller / gha科学计算codeforces-go 力扣双周赛 139 题解从 0-1 BFS 到前后缀分解与 LIScodeforces go 力扣双周赛 139 题解从 0 1 BFS 到前后缀分解与 LIS 力扣第 139 场双周赛共四题本仓库 leetcode/bi科学计算上一篇终极OneNote Markdown插件完整指南让传统笔记焕发专业光彩下一篇GraphRAG-Local-UI故障排除大全常见问题与解决方案汇总创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

力扣双周赛 172 全题解：从二维 0-1 背包到 O(1) 位运算（基于 codeforces-go 算法模板库）

相关推荐

Goa 仓库开发指南全解析：AGENTS.md 编码规范、代码生成契约与问题复现协议

XMall 分布式电商项目中的 Dubbo 架构实践：服务注册、消费与负载均衡全解析

openpilot 开源驾驶辅助实战指南：车道居中和自适应巡航，三步装好上手

更多资讯

Unity 2D黄金矿工开发实战：物理参数、DistanceJoint2D关节与碰撞检测全解析

Nginx Proxy Manager实战：告别IP加端口，统一内网服务域名

车辆调度思维链：把老师傅经验变成可解释的决策流程

2026 AI编程工具全景解析：从IDE插件到Agent的选型指南

CSGO盲盒开箱源码解析：概率算法、对战结算与防刷设计

Python+uniapp预约小程序实战：从疫苗预约到通用预约系统

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？