教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇文章讲解 LogicStack-LeetCode 仓库中 LeetCode 第 1769 题「移动所有球到每个盒子所需的最小操作数」的完整题解。题目给定一个长度为n的二进制字符串要求我们为每个盒子独立计算「将所有小球汇聚到该盒子」所需的最少移动步数本文给出基于双向预处理的模拟解法将朴素的 $O(n^2)$ 枚举优化到 $O(n)$并给出 Java、C、Python、TypeScript 四种语言的完整可运行代码。读完本文你将掌握「用两个方向递推累积步数」这一模拟类题目的核心套路并能直接迁移到仓库中大量同类的模拟题。一、题目描述与输入约束有n个盒子给你一个长度为n的二进制字符串boxes其中boxes[i]的值为0表示第i个盒子是空的而boxes[i]的值为1表示盒子里有一个小球。在一步操作中你可以将一个小球从某个盒子移动到一个与之相邻的盒子中。第i个盒子和第j个盒子相邻需满足abs(i - j) 1。注意操作执行后某些盒子中可能会存在不止一个小球即一个盒子可以同时容纳多个球。需要返回一个长度为n的数组answer其中answer[i]是将所有小球移动到第i个盒子所需的最小操作数且每个answer[i]都需要根据盒子的初始状态进行计算——也就是说每个位置 i 的答案是独立计算的不需要考虑其他位置移动方案之间的相互影响。示例 1输入boxes 110 输出[1,1,3]解释每个盒子对应的最小操作数如下第 1 个盒子将一个小球从第 2 个盒子移动到第 1 个盒子需要 1 步操作第 2 个盒子将一个小球从第 1 个盒子移动到第 2 个盒子需要 1 步操作第 3 个盒子将一个小球从第 1 个盒子移动到第 3 个盒子需要 2 步操作将一个小球从第 2 个盒子移动到第 3 个盒子需要 1 步操作共计 3 步操作。示例 2输入boxes 001011 输出[11,8,5,4,3,4]提示n boxes.length1 n 2000boxes[i]为0或1二、解题思路从暴力枚举到线性递推直观但低效的暴力做法先建立一个朴素认知若要把所有小球都移动到位置i那么位于i左侧的每个小球都要向右移动i - j步位于i右侧的每个小球都要向左移动j - i步。因此$$answer[i] \sum_{j i, boxes[j] 1} (i - j) \sum_{j i, boxes[j] 1} (j - i)$$直接按这个公式对每个i做一次 $O(n)$ 求和整体复杂度是 $O(n^2)$。虽然本题n 2000时 $O(n^2)$ 也能通过但既然我们追求的是尽可能简洁、尽可能高效的解法更优的做法是用一次线性扫描把左右两侧的信息全部预处理出来。核心观察代价可以按位置累积关键洞察在于代价不是离散跳跃的而是可以按步数递推累积的。想象从左往右扫描维护变量cur当前已扫过的前缀中有多少个小球维护变量step把这些前缀小球全部移动到当前位置i所需的步数。当扫描指针从位置i - 1移动到位置i时之前积累的每一个前缀小球都要再多移动 1 步所以step要增加cur前缀小球总数然后boxes[i]自身是否为球再决定cur是否加一。这就形成了 O(1) 的递推。从右往左扫描时逻辑完全对称处理的是后缀小球移动到当前位置的步数。三、核心解法双向预处理 线性扫描预处理两个与boxes等长的数组l和rl[i]代表「将 $[0, i]$ 的小球移动到位置 $i$」所需要的步数r[i]代表「将 $[i, n - 1]$ 的小球移动到位置 $i$」所需要的步数。所求的答案数组ans与数组l和r的关系为$$ans[i] l[i] r[i]$$预处理两个数组是简单的分别从两个方向遍历boxes使用变量cur代表当前处理到的前缀/后缀的小球总个数变量step代表将当前所有前缀/后缀小球移动到位置i所需要的步数。递推式的直觉以从左到右为例循环内核心只有两行step cur; // 所有已扫过的小球都要额外走 1 步才能到达当前盒子 i cur boxes[i] - 0; // 当前盒子自身是否新增一个小球1 则加 1 l[i] step;第一行是累积步数第二行是累积球数二者配合即可在单次遍历中同时维护两个信息这正是该解法优雅的地方。右侧同理只是遍历方向相反。用手动推导验证示例 1以boxes 110为例从左到右求li进入循环前 curstep cur 后cur 更新后l[i]0cur0, step0step0cur101cur1, step0step1cur212cur2, step1step3cur23从右到左求ri进入循环前 curstep cur 后cur 更新后r[i]2cur0, step0step0cur001cur0, step0step0cur100cur1, step0step1cur21最终ans[i] l[i] r[i]得到[1, 1, 3]与题目示例完全一致。当n 1只有一个盒子时l[0] r[0] 0答案是[0]边界情况天然正确。四、四种语言的完整代码实现原题解在仓库 LeetCode/1761-1770/1769. 移动所有球到每个盒子所需的最小操作数中等.md 中给出了 Java、C、Python、TypeScript 四种实现以下完整继承并补充关键注释。Javaclass Solution { public int[] minOperations(String boxes) { int n boxes.length(); int[] l new int[n 10], r new int[n 10]; // 从左到右l[i] 表示将 [0, i] 的小球移动到位置 i 的步数 for (int i 0, cur 0, step 0; i n; i) { step cur; // 已积累的前缀小球都要多走 1 步 cur boxes.charAt(i) - 0; // 当前盒子有球则前缀球数 1 l[i] step; } // 从右到左r[i] 表示将 [i, n - 1] 的小球移动到位置 i 的步数 for (int i n - 1, cur 0, step 0; i 0; i--) { step cur; cur boxes.charAt(i) - 0; r[i] step; } int[] ans new int[n]; for (int i 0; i n; i) ans[i] l[i] r[i]; return ans; } }Cclass Solution { public: vectorint minOperations(string boxes) { int n boxes.size(); vectorint l(n 10), r(n 10); for (int i 0, cur 0, step 0; i n; i) { step cur; cur boxes[i] - 0; l[i] step; } for (int i n - 1, cur 0, step 0; i 0; i--) { step cur; cur boxes[i] - 0; r[i] step; } vectorint ans(n); for (int i 0; i n; i) ans[i] l[i] r[i]; return ans; } };Pythonclass Solution: def minOperations(self, boxes: str) - List[int]: n len(boxes) l, r [0] * n, [0] * n step, cur 0, 0 for i in range(n): step, cur step cur, cur 1 if boxes[i] 1 else cur l[i] step step, cur 0, 0 for i in range(n - 1, -1, -1): step, cur step cur, cur 1 if boxes[i] 1 else cur r[i] step return [l[i] r[i] for i in range(n)]TypeScriptfunction minOperations(boxes: string): number[] { const n boxes.length const l new Arraynumber(n 10).fill(0), r new Arraynumber(n 10).fill(0) for (let i 0, cur 0, step 0; i n; i) { step cur; cur boxes[i] 1 ? 1 : 0; l[i] step; } for (let i n - 1, cur 0, step 0; i 0; i--) { step cur; cur boxes[i] 1 ? 1 : 0; r[i] step; } const ans new Arraynumber(n).fill(0) for (let i 0; i n; i) ans[i] l[i] r[i] return ans }五、复杂度分析时间复杂度$O(n)$从左到右、从右到左各一次线性扫描再加上一次合并答案的扫描总共 3 次遍历均为 $O(n)$空间复杂度$O(n)$使用了与boxes等长的辅助数组l和rJava/C/TypeScript 实现中开到了n 10的容量纯属冗余余量实际只用前n个位置Python 实现则精确开到n。若追求更极致的空间可以观察到l和r都只被使用一次完全可以先只求l再在从右往左的第二次扫描中边求r边累加进答案从而把辅助空间降到 $O(1)$代码上只需略作改写即可不影响算法本质。六、在仓库中的定位模拟思想家族本解法被归档为「模拟」类题目。仓库的 Index/模拟.md 索引页收录了大量同类模拟题解例如K 次取反后最大化的数组和简单删除字符串中的所有相邻重复项简单拆炸弹简单从这些题可以看到模拟并非简单的按题意逐字翻译而是常常需要在模拟过程中引入预处理、递推、双指针或方向切换等技巧来压缩复杂度。本题的双向预处理思路与「前缀和」思想同源——l和r本质上就是带权的前缀/后缀代价累积只是这里累积的权是步数而非元素和。七、小结LeetCode 1769 是一道非常适合练习模拟 递推的经典中等题每个answer[i]相互独立天然适合拆成左侧贡献 右侧贡献左右两侧贡献各自可以通过一次单向扫描用cur球数与step步数两个变量线性递推得到最终答案即l[i] r[i]整体时间复杂度 $O(n)$、空间复杂度 $O(n)$。掌握了移动过程中的代价累积递推你就能从容应对这类把所有东西搬到某个位置的模拟题也能为后续学习前缀和、差分等思想打下直观基础。完整题解与四种语言代码见仓库文件 LeetCode/1761-1770/1769. 移动所有球到每个盒子所需的最小操作数中等.md。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 1769 移动所有球到每个盒子所需的最少操作数暴力、前缀和与两趟遍历全解NeetCode 解法库LeetCode 1769 移动所有球到每个盒子所需的最少操作数暴力、前缀和与两趟遍历全解NeetCode 解法库 本文以仓库 articles/mini示例工程教程刷穿 LeetCode 1742盒子中小球的最大数量 —— 「哈希表 模拟」计数思想的实战拆解刷穿 LeetCode 1742盒子中小球的最大数量 —— 「哈希表 模拟」计数思想的实战拆解 本文是 LogicStack LeetCode「宫水三叶教程文档kkFileView 实现 DWG 在线预览完整指南10 分钟跑通 CAD 图纸预览服务kkFileView 实现 DWG 在线预览完整指南10 分钟跑通 CAD 图纸预览服务 工程图纸在设计、审核、施工之间流转时本地打不开 DWG、装 CA教程文档上一篇Open Glean自带模型BYOM实战接入任意OpenAI兼容端点含本地Ollama/LM Studio下一篇给你的Agent装上实时进度条LLM-as-a-Verifier的track细粒度进度追踪完全指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考