企业官网建设流程全解析

• 科学计算

本文是算法竞赛模板库 codeforces-go 对 LeetCode 第 121 场双周赛第三题minimum-number-of-operations-to-make-x-and-y-equal（使 X 和 Y 相等的最少操作数）的完整技术解析。全文以仓库 leetcode/biweekly/121/c/README.md 题解为主体，结合仓库中同目录的 Go 实现、测试数据与 testutil 自动化测试框架，分别讲解图论建模 BFS 与记忆化搜索两种解法，并给出 Python / Java / C++ / Go 四语言可运行代码与复杂度推导。读完本文，你将掌握「带除法操作的加减最短路问题」的两类标准建模思路，以及此类题目在仓库中从题解文档到自动验证测试的完整工程化落地方式。

题目背景与操作规则

本题来自 2024 年 1 月举行的第 121 场双周赛第三题，题号为 2998，题目名为minimum-number-of-operations-to-make-x-and-y-equal。从题解代码可以确认，问题的操作集合为：对当前数x，每次操作可以：

• 执行x + 1（加一）；
• 执行x - 1（减一）；
• 当x是 5 的倍数时，执行x / 5（除以 5）；
• 当x是 11 的倍数时，执行x / 11（除以 11）。

目标是从给定的x出发，通过上述操作的最少次数到达y。题解给出了两条截然不同的思考路径：

• 方法一：把每个数看成图上的节点，每种操作看成一条边，跑 BFS 求最短路；
• 方法二：基于「除法操作能成规模缩小问题」这一观察，设计带记忆化的递归搜索，复杂度可从O(x)降到O(log²(x/y))。

方法一：BFS 最短路建模

核心思想：把操作看成连边

题解的第一句话就点明了本质：

每个操作都可以理解成：从x向操作后的数连边。

于是整个问题被抽象为一张无限图：节点是整数，+1、-1、/5、/11分别是从当前节点出发的四类有向边（后两者仅在整除时存在）。题目所求的「最少操作次数」就是图中从x到y的最短路长度，而所有边权都为 1，因此 BFS 天然是最短路的最优算法——第一次从队列中弹出y时，步数即为答案。

关键剪枝：x < y时无需 BFS

题解特别指出：如果x < y，那么只能使用加一操作。原因很直接：-1、/5、/11三种操作都会让数变小，只会使x与y的差距进一步拉大，因此唯一可行的路径就是一步步加一，操作次数直接等于y - x。

if x <= y: return y - x

双数组 BFS 与三个实现细节

题解代码采用「双数组」实现 BFS（交替使用两个队列，取代标准 BFS 中常用的"队列 + 距离数组"），并做了三处值得注意的优化：

1. 答案上界ans = x - y：既然只用减一操作，x - y步一定能到达y，这为搜索提供了一个"当前已知最好"的上界，BFS 过程中一旦发现更优的步数就更新它，最终min(ans, step)即答案。
2. vis数组的规模上界x + ans + 1：由于+1操作至多执行x - y次（若加一超过这个次数，直接减一回到y反而更优），所以 BFS 过程中涉及的最大数不会超过x + (x - y)，据此给vis数组分配容量，避免了对无限整数域做哈希或超大数组的开销。
3. add函数的提前收束：当某个待加入的节点v < y时，不再把它入队展开，而是直接假设后续只能加一，用step + 1 + y - v更新答案——此时step是当前层数，1是从v走到y方向的第一步加一，y - v是剩余加一步数。这本质上是一种"边界触底直接结算"的剪枝，大幅减少了无效状态的展开。

四语言实现

class Solution: def minimumOperationsToMakeEqual(self, x: int, y: int) -> int: if x <= y: return y - x ans = x - y # 总操作次数不会超过 x-y vis = [False] * (x + ans + 1) # +1 操作至多执行 x-y 次 q = [] step = 0 def add(v: int) -> None: if v < y: nonlocal ans ans = min(ans, step + 1 + y - v) # 只能执行 +1 操作 elif not vis[v]: vis[v] = True q.append(v) add(x) while True: tmp = q q = [] for v in tmp: if v == y: return min(ans, step) if v % 11 == 0: add(v // 11) if v % 5 == 0: add(v // 5) add(v - 1) add(v + 1) step += 1

class Solution { public int minimumOperationsToMakeEqual(int x, int y) { if (x <= y) { return y - x; } int ans = x - y; // 总操作次数不会超过 x-y boolean[] vis = new boolean[x + ans + 1]; // +1 操作至多执行 x-y 次 vis[x] = true; List<Integer> q = List.of(x); int step = 0; while (true) { List<Integer> tmp = q; q = new ArrayList<>(); for (int v : tmp) { if (v == y) { return Math.min(ans, step); } if (v < y) { ans = Math.min(ans, step + y - v); continue; } if (v % 11 == 0 && !vis[v / 11]) { vis[v / 11] = true; q.add(v / 11); } if (v % 5 == 0 && !vis[v / 5]) { vis[v / 5] = true; q.add(v / 5); } if (!vis[v - 1]) { vis[v - 1] = true; q.add(v - 1); } if (!vis[v + 1]) { vis[v + 1] = true; q.add(v + 1); } } step++; } } }

class Solution { public: int minimumOperationsToMakeEqual(int x, int y) { if (x <= y) { return y - x; } int ans = x - y; // 总操作次数不会超过 x-y vector<int> vis(x + ans + 1); // +1 操作至多执行 x-y 次 vector<int> q; int step = 0; auto add = & { if (v < y) { ans = min(ans, step + 1 + y - v); // 只能执行 +1 操作 } else if (!vis[v]) { vis[v] = true; q.push_back(v); } }; add(x); while (true) { auto tmp = move(q); // move 后 q 为空 for (int v : tmp) { if (v == y) { return min(ans, step); } if (v % 11 == 0) { add(v / 11); } if (v % 5 == 0) { add(v / 5); } add(v - 1); add(v + 1); } step++; } } };

func minimumOperationsToMakeEqual(x, y int) int { if x <= y { return y - x } ans := x - y // 总操作次数不会超过 x-y vis := make([]bool, x+ans+1) // +1 操作至多执行 x-y 次 q := []int{} step := 0 add := func(v int) { if v < y { ans = min(ans, step+1+y-v) // 只能执行 +1 操作 } else if !vis[v] { vis[v] = true q = append(q, v) } } add(x) for { tmp := q q = nil for _, v := range tmp { if v == y { return min(ans, step) } if v%11 == 0 { add(v / 11) } if v%5 == 0 { add(v / 5) } add(v - 1) add(v + 1) } step++ } }

复杂度分析

• 时间复杂度：O(x)。vis数组长度为x + (x - y) + 1，每个元素至多被访问一次，因此 BFS 展开的状态总数是O(x)的。
• 空间复杂度：O(x)。主要为vis布尔数组的开销。

方法二：记忆化搜索

状态转移推导：为什么可以只考虑最近的倍数

BFS 虽然直观，但O(x)的复杂度在面对较大输入时仍有压力。方法二观察到：除法是唯一能把数"打小"的操作，而且只要到达一个能被 5 或 11 整除的数，就可以执行一次除法让问题规模锐减。

设f(x)表示从x到y的最少操作数，题解先枚举了x > y时的全部可能性：

• 只用减一操作，代价是x - y；
• 通过若干次减一到达最近的小于等于x的 11 的倍数x' = x - x mod 11，再除以 11：问题变成f(x' / 11) = f(x / 11)，总代价x mod 11 + 1 + f(x / 11)。题解特别论证了"无需再往下减"：继续减到x' - 11再除以 11，等价于"先把x'除以 11 再减一"——两者到达同一个数，但后者操作次数更小，因此到达x'后应立即除 11，不再继续减；
• 通过若干次加一到达最近的大于x的 11 的倍数x' = x + 11 - x mod 11，再除以 11：代价11 - x mod 11 + 1 + f(x / 11 + 1)；
• 同理，对除数 5 有两条对称转移：x mod 5 + 1 + f(x / 5)与5 - x mod 5 + 1 + f(x / 5 + 1)。

取上述所有方式的最小值，即：

f(x) = min( x - y, f(x/11) + x%11 + 1, f(x/11+1) + 11 - x%11 + 1, f(x/5) + x%5 + 1, f(x/5+1) + 5 - x%5 + 1 )

而x <= y时只剩加一操作，直接返回y - x（递归出口）。

四语言实现

class Solution: @cache def minimumOperationsToMakeEqual(self, x: int, y: int) -> int: if x <= y: return y - x return min(x - y, self.minimumOperationsToMakeEqual(x // 11, y) + x % 11 + 1, self.minimumOperationsToMakeEqual(x // 11 + 1, y) + 11 - x % 11 + 1, self.minimumOperationsToMakeEqual(x // 5, y) + x % 5 + 1, self.minimumOperationsToMakeEqual(x // 5 + 1, y) + 5 - x % 5 + 1)

class Solution { private final Map<Integer, Integer> memo = new HashMap<>(); public int minimumOperationsToMakeEqual(int x, int y) { if (x <= y) { return y - x; } if (memo.containsKey(x)) { return memo.get(x); } int ans = x - y; ans = Math.min(ans, minimumOperationsToMakeEqual(x / 11, y) + x % 11 + 1); ans = Math.min(ans, minimumOperationsToMakeEqual(x / 11 + 1, y) + 11 - x % 11 + 1); ans = Math.min(ans, minimumOperationsToMakeEqual(x / 5, y) + x % 5 + 1); ans = Math.min(ans, minimumOperationsToMakeEqual(x / 5 + 1, y) + 5 - x % 5 + 1); memo.put(x, ans); return ans; } }

class Solution { unordered_map<int, int> memo; public: int minimumOperationsToMakeEqual(int x, int y) { if (x <= y) { return y - x; } auto it = memo.find(x); if (it != memo.end()) { return it->second; } return memo[x] = min({x - y, minimumOperationsToMakeEqual(x / 11, y) + x % 11 + 1, minimumOperationsToMakeEqual(x / 11 + 1, y) + 11 - x % 11 + 1, minimumOperationsToMakeEqual(x / 5, y) + x % 5 + 1, minimumOperationsToMakeEqual(x / 5 + 1, y) + 5 - x % 5 + 1}); } };

func minimumOperationsToMakeEqual(x, y int) int { memo := map[int]int{} var dfs func(int) int dfs = func(x int) int { if x <= y { return y - x } if v, ok := memo[x]; ok { return v } res := min(x-y, dfs(x/11)+x%11+1, dfs(x/11+1)+11-x%11+1, dfs(x/5)+x%5+1, dfs(x/5+1)+5-x%5+1) memo[x] = res return res } return dfs(x) }

复杂度分析：O(log²(x/y))

题解给出了严谨的规模推导：由于除法对x的影响远大于加减，可以认为每次递归都把x的规模变成x/5与x/11两个分支，当x <= y时递归终止。因此从x到y的过程中，x的规模会变成x / (5^p * 11^q)，其中指数p与q各有O(log(x/y))个取值，组合起来的状态个数为O(log²(x/y))。

• 时间复杂度：O(log²(x/y))。动态规划的时间复杂度等于「状态个数 × 单个状态的计算时间」，状态个数为O(log²(x/y))，单个状态只做常数次min比较与取模运算，故总复杂度为O(log²(x/y))。
• 空间复杂度：O(log²(x/y))。保存每个状态所需的空间等于状态个数（记忆化哈希表 /@cache缓存）。

对比方法一的O(x)，方法二在x远大于y的场景下优势显著，这也是它成为本题更优解的原因。

仓库工程化实践：Go 实现与自动化测试

提交版 Go 核心实现

仓库中的 c.go 正是方法二的 Go 版本（与题解文档中的sol-Go代码完全一致），以memo哈希表 + 闭包dfs实现记忆化，代码量极短且与题解一一对应，是"题解文档 ↔ 提交代码"同步维护的典型范例。

反射驱动的测试框架

testutil 测试目录 中的测试文件是Code generated by copypasta/template/leetcode/generator_test.go生成的，核心调用为：

if err := testutil.RunLeetCodeFuncWithFile(t, minimumOperationsToMakeEqual, "c.txt", 0); err != nil { t.Fatal(err) }

其中RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go：它按「函数参数个数 + 返回值个数」为一组，从c.txt中逐组切分输入输出，再借助反射（reflect.TypeOf(f)、fValue.Call(ins)）自动完成参数解析、调用与结果比对，同时支持-1指定最后一个用例、targetCaseNum定向运行单个用例等功能。测试数据文件 c.txt 中保存了本题的全部官方样例（如26 1 -> 3、54 2 -> 4、25 30 -> 5，每组输入输出占一行，中间以空行分隔），在仓库根目录执行go test ./leetcode/biweekly/121/c/即可一键验证实现。

题解文档的生成与维护链路

从源码结构看，c_test.go的生成依赖 copypasta/template/leetcode/generator.go 中的GenLeetCodeTests系列函数：它登录力扣国服账号后拉取指定场次（contestTag如biweekly-contest-121）的题目信息，解析题目 HTML 中的 Go 默认代码与 Input/Output 样例，然后批量生成a.go/b.go/c.go的实现文件、*_test.go测试文件与*.txt测试数据。README 题解文档中的sol-Go代码则与生成出的c.go保持一致，形成「题解 → 代码 → 测试数据 → 自动验证」的闭环，这正是本仓库把每道 LeetCode 题目沉淀为可复现工程资产的方式。

相似题目与延伸思考

题解文档在文末给出了两类思路的进阶训练方向：

• **方法一（图建模 + BFS）**的延伸题：转化数字的最小运算数（minimum-operations-to-convert-number，力扣难度分 1850）。该题同样是"给定一组运算、求从起点到目标的最少运算数"，建模方式与本题方法一几乎同构，适合巩固 BFS 最短路的思维；
• **方法二（除法缩规模 + 记忆化搜索）**的延伸题：吃掉 N 个橘子的最少天数（minimum-number-of-days-to-eat-n-oranges，力扣难度分 2048）。该题同样具备"只有除法能大幅缩小规模"的结构，其自顶向下搜索 + 记忆化的写法与本题方法二一脉相承。

两类题目共同揭示了一个可迁移的解题模式：当操作集中存在"整除类"操作时，优先考虑对倍数附近的状态做跳转（跳到最近的倍数再除），配合记忆化即可把线性复杂度压到对数级；而当状态空间可预测、规模可控时，图建模 + BFS 则是最通用、最不容易出错的兜底方案。结合仓库 leetcode/SOLUTIONS.md 中按题单分类整理的全部题解，可以系统地完成从"单个题型"到"解题套路"的进阶。

总结

本文以 codeforces-go 仓库对第 121 场双周赛第三题的题解文档为骨架，完整还原了两种解法：BFS 将每个操作视为图上的一条边，用双数组队列求最短路，并以x - y为上界做剪枝，复杂度O(x)；记忆化搜索则利用除法对规模的指数级压缩，只在 5/11 的最近倍数处做跳转，把复杂度优化到O(log²(x/y))。与此同时，仓库以 c.go、c_test.go、c.txt 与 testutil 反射测试框架，为这道题沉淀了一套可一键验证的工程化闭环。掌握这两种建模方式与复杂度论证手法，即可从容应对同类"运算集合 + 最少步数"问题。

• 科学计算