LeetCode 1769 移动所有球到每个盒子所需的最少操作数暴力、前缀和与两趟遍历全解NeetCode 解法库【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库 articles/minimum-number-of-operations-to-move-all-balls-to-each-box.md 为骨架系统讲解 LeetCode 第 1769 题「移动所有球到每个盒子所需的最少操作数」的三种递进解法朴素暴力法、前缀和法与最优的两趟遍历法。读完本文你将掌握如何用 O(n) 时间一次性求出每个盒子作为汇聚点时所有球移动的总代价并能将其中的「前缀和 左右两次扫描」技巧迁移到仓库内其他同类问题如 Product of Array Except Self、Find Pivot Index上。问题概述给定一个长度为n的二进制字符串boxes其中boxes[i]为0表示第i个盒子为空为1表示该盒子中有且只有一个球。一次操作可以把某个球向左或向右移动一个盒子。对每个位置pos0 ≤ pos n需要回答把所有球都移动到第pos个盒子所需的最少操作数。最终返回一个长度为n的数组res其中res[pos]即对应答案。核心观察把球从位置i移动到位置pos的代价恰好是两者下标的绝对距离|pos - i|因此res[pos] Σ |pos - i|对所有满足boxes[i] 1的i求和。问题本质是对一维坐标轴上的若干质量点求它们到每个整数坐标点的加权距离和。前置知识开始编码前需要熟悉以下三项基础能力数组遍历Array Traversal理解如何迭代数组并维护累计值是本题所有解法的前提。前缀和Prefix Sums优化解法利用前缀和高效计算来自左侧与右侧的贡献避免重复扫描。两趟遍历Two-Pass Technique最优方案从左到右、从右到左各扫描一次数组在两次遍历中完成全部贡献的累加。解法一暴力法Brute Force—— O(n²)思路对于每个目标盒子pos直接遍历所有盒子凡是有球的盒子i就把距离|pos - i|累加到res[pos]。这完全按照题面定义逐项计算是最直观、最不容易出错的写法。算法步骤创建长度为n的结果数组res初始化为 0。对每个目标位置pos外层循环遍历所有盒子i内层循环。若boxes[i] 1执行res[pos] abs(pos - i)。返回res。多语言实现class Solution: def minOperations(self, boxes: str) - List[int]: n len(boxes) res [0] * n for pos in range(n): for i in range(n): if boxes[i] 1: res[pos] abs(pos - i) return respublic class Solution { public int[] minOperations(String boxes) { int n boxes.length(); int[] res new int[n]; for (int pos 0; pos n; pos) { for (int i 0; i n; i) { if (boxes.charAt(i) 1) { res[pos] Math.abs(pos - i); } } } return res; } }class Solution { public: vectorint minOperations(string boxes) { int n boxes.size(); vectorint res(n, 0); for (int pos 0; pos n; pos) { for (int i 0; i n; i) { if (boxes[i] 1) { res[pos] abs(pos - i); } } } return res; } };class Solution { /** * param {string} boxes * return {number[]} */ minOperations(boxes) { const n boxes.length; const res new Array(n).fill(0); for (let pos 0; pos n; pos) { for (let i 0; i n; i) { if (boxes[i] 1) { res[pos] Math.abs(pos - i); } } } return res; } }public class Solution { public int[] MinOperations(string boxes) { int n boxes.Length; int[] res new int[n]; for (int pos 0; pos n; pos) { for (int i 0; i n; i) { if (boxes[i] 1) { res[pos] Math.Abs(pos - i); } } } return res; } }func minOperations(boxes string) []int { n : len(boxes) res : make([]int, n) for pos : 0; pos n; pos { for i : 0; i n; i { if boxes[i] 1 { if pos i { res[pos] pos - i } else { res[pos] i - pos } } } } return res }class Solution { fun minOperations(boxes: String): IntArray { val n boxes.length val res IntArray(n) for (pos in 0 until n) { for (i in 0 until n) { if (boxes[i] 1) { res[pos] kotlin.math.abs(pos - i) } } } return res } }class Solution { func minOperations(_ boxes: String) - [Int] { let n boxes.count var res Int let chars Array(boxes) for pos in 0..n { for i in 0..n { if chars[i] 1 { res[pos] abs(pos - i) } } } return res } }impl Solution { pub fn min_operations(boxes: String) - Veci32 { let n boxes.len(); let bytes boxes.as_bytes(); let mut res vec![0; n]; for pos in 0..n { for i in 0..n { if bytes[i] b1 { res[pos] (pos as i32 - i as i32).abs(); } } } res } }class Solution { /** * param {string} boxes * return {number[]} */ minOperations(boxes: string): number[] { const n boxes.length; const res: number[] new Array(n).fill(0); for (let pos 0; pos n; pos) { for (let i 0; i n; i) { if (boxes[i] 1) { res[pos] Math.abs(pos - i); } } } return res; } }复杂度分析时间复杂度O(n²)。外层 n 个位置 × 内层 n 个盒子。空间复杂度O(1) 额外空间不含输出数组输出数组本身占用 O(n)。暴力法在n较大时本题数据范围可到 2000仍可接受但它重复计算了大量信息相邻位置pos与pos 1的结果高度相关却被各自独立地完整扫描了一遍。解法二前缀和Prefix Sum—— O(n)思路把res[i]拆成左侧贡献与右侧贡献两部分对位置i左侧的球每个球到i的距离为i - index总和为i * count_left - sum_of_indices_left对位置i右侧的球每个球到i的距离为index - i总和为sum_of_indices_right - i * count_right。因此只需要预先求出两类前缀信息——球的个数前缀和与球下标之和前缀和——就能在 O(1) 时间内算出任意位置i的左右贡献。算法步骤构建两个前缀数组长度为n 1prefix_count[i] 盒子0到i-1中球的个数index_sum[i] 盒子0到i-1中所有球的下标之和。对每个位置i左侧贡献 i * left_count - left_sum右侧贡献 right_sum - i * right_count两者相加写入res[i]。返回res。其中left_count prefix_count[i]、left_sum index_sum[i]直接取自前缀数组右侧信息用总前缀减去当前位置之后的前缀得到right_count prefix_count[n] - prefix_count[i 1]、right_sum index_sum[n] - index_sum[i 1]。多语言实现class Solution: def minOperations(self, boxes: str) - List[int]: n len(boxes) res [0] * n prefix_count [0] * (n 1) index_sum [0] * (n 1) for i in range(n): prefix_count[i 1] prefix_count[i] (boxes[i] 1) index_sum[i 1] index_sum[i] (i if boxes[i] 1 else 0) for i in range(n): left prefix_count[i] left_sum index_sum[i] right prefix_count[n] - prefix_count[i 1] right_sum index_sum[n] - index_sum[i 1] res[i] (i * left - left_sum) (right_sum - i * right) return respublic class Solution { public int[] minOperations(String boxes) { int n boxes.length(); int[] res new int[n]; int[] prefixCount new int[n 1]; int[] indexSum new int[n 1]; for (int i 0; i n; i) { prefixCount[i 1] prefixCount[i] (boxes.charAt(i) 1 ? 1 : 0); indexSum[i 1] indexSum[i] (boxes.charAt(i) 1 ? i : 0); } for (int i 0; i n; i) { int left prefixCount[i]; int leftSum indexSum[i]; int right prefixCount[n] - prefixCount[i 1]; int rightSum indexSum[n] - indexSum[i 1]; res[i] i * left - leftSum (rightSum - i * right); } return res; } }class Solution { public: vectorint minOperations(string boxes) { int n boxes.size(); vectorint res(n), prefixCount(n 1, 0), indexSum(n 1, 0); for (int i 0; i n; i) { prefixCount[i 1] prefixCount[i] (boxes[i] 1 ? 1 : 0); indexSum[i 1] indexSum[i] (boxes[i] 1 ? i : 0); } for (int i 0; i n; i) { int left prefixCount[i]; int leftSum indexSum[i]; int right prefixCount[n] - prefixCount[i 1]; int rightSum indexSum[n] - indexSum[i 1]; res[i] i * left - leftSum (rightSum - i * right); } return res; } };class Solution { /** * param {string} boxes * return {number[]} */ minOperations(boxes) { const n boxes.length; const res new Array(n).fill(0); const prefixCount new Array(n 1).fill(0); const indexSum new Array(n 1).fill(0); for (let i 0; i n; i) { prefixCount[i 1] prefixCount[i] (boxes[i] 1 ? 1 : 0); indexSum[i 1] indexSum[i] (boxes[i] 1 ? i : 0); } for (let i 0; i n; i) { const left prefixCount[i]; const leftSum indexSum[i]; const right prefixCount[n] - prefixCount[i 1]; const rightSum indexSum[n] - indexSum[i 1]; res[i] i * left - leftSum (rightSum - i * right); } return res; } }public class Solution { public int[] MinOperations(string boxes) { int n boxes.Length; int[] res new int[n]; int[] prefixCount new int[n 1]; int[] indexSum new int[n 1]; for (int i 0; i n; i) { prefixCount[i 1] prefixCount[i] (boxes[i] 1 ? 1 : 0); indexSum[i 1] indexSum[i] (boxes[i] 1 ? i : 0); } for (int i 0; i n; i) { int left prefixCount[i]; int leftSum indexSum[i]; int right prefixCount[n] - prefixCount[i 1]; int rightSum indexSum[n] - indexSum[i 1]; res[i] i * left - leftSum (rightSum - i * right); } return res; } }func minOperations(boxes string) []int { n : len(boxes) res : make([]int, n) prefixCount : make([]int, n1) indexSum : make([]int, n1) for i : 0; i n; i { if boxes[i] 1 { prefixCount[i1] prefixCount[i] 1 indexSum[i1] indexSum[i] i } else { prefixCount[i1] prefixCount[i] indexSum[i1] indexSum[i] } } for i : 0; i n; i { left : prefixCount[i] leftSum : indexSum[i] right : prefixCount[n] - prefixCount[i1] rightSum : indexSum[n] - indexSum[i1] res[i] i*left - leftSum (rightSum - i*right) } return res }class Solution { fun minOperations(boxes: String): IntArray { val n boxes.length val res IntArray(n) val prefixCount IntArray(n 1) val indexSum IntArray(n 1) for (i in 0 until n) { prefixCount[i 1] prefixCount[i] if (boxes[i] 1) 1 else 0 indexSum[i 1] indexSum[i] if (boxes[i] 1) i else 0 } for (i in 0 until n) { val left prefixCount[i] val leftSum indexSum[i] val right prefixCount[n] - prefixCount[i 1] val rightSum indexSum[n] - indexSum[i 1] res[i] i * left - leftSum (rightSum - i * right) } return res } }class Solution { func minOperations(_ boxes: String) - [Int] { let n boxes.count var res Int var prefixCount Int var indexSum Int let chars Array(boxes) for i in 0..n { prefixCount[i 1] prefixCount[i] (chars[i] 1 ? 1 : 0) indexSum[i 1] indexSum[i] (chars[i] 1 ? i : 0) } for i in 0..n { let left prefixCount[i] let leftSum indexSum[i] let right prefixCount[n] - prefixCount[i 1] let rightSum indexSum[n] - indexSum[i 1] res[i] i * left - leftSum (rightSum - i * right) } return res } }impl Solution { pub fn min_operations(boxes: String) - Veci32 { let n boxes.len(); let bytes boxes.as_bytes(); let mut res vec![0i32; n]; let mut prefix_count vec![0i32; n 1]; let mut index_sum vec![0i32; n 1]; for i in 0..n { let is_one if bytes[i] b1 { 1 } else { 0 }; prefix_count[i 1] prefix_count[i] is_one; index_sum[i 1] index_sum[i] if bytes[i] b1 { i as i32 } else { 0 }; } for i in 0..n { let left prefix_count[i]; let left_sum index_sum[i]; let right prefix_count[n] - prefix_count[i 1]; let right_sum index_sum[n] - index_sum[i 1]; res[i] i as i32 * left - left_sum (right_sum - i as i32 * right); } res } }class Solution { /** * param {string} boxes * return {number[]} */ minOperations(boxes: string): number[] { const n boxes.length; const res: number[] new Array(n).fill(0); const prefixCount: number[] new Array(n 1).fill(0); const indexSum: number[] new Array(n 1).fill(0); for (let i 0; i n; i) { prefixCount[i 1] prefixCount[i] (boxes[i] 1 ? 1 : 0); indexSum[i 1] indexSum[i] (boxes[i] 1 ? i : 0); } for (let i 0; i n; i) { const left prefixCount[i]; const leftSum indexSum[i]; const right prefixCount[n] - prefixCount[i 1]; const rightSum indexSum[n] - indexSum[i 1]; res[i] i * left - leftSum (rightSum - i * right); } return res; } }复杂度分析时间复杂度O(n)。构建前缀数组 O(n)逐位计算 O(n)。空间复杂度O(n)。两个长度n 1的前缀数组。这种「维护前缀个数与前缀下标和」的思想与仓库内 Find Pivot Index 一文的左右和拆分一脉相承是前缀和思想的又一典型应用。解法三前缀和最优版两趟遍历—— O(n) 时间、O(1) 额外空间思路解法二用两个前缀数组换来了 O(1) 的查询但能否把空间也压到 O(1)关键在于观察相邻位置之间结果的增量关系从左向右扫描时想象所有已扫描到的球每向前推进一个位置它们到当前盒子的距离总和就会增加球的个数。于是可以维护两个滚动变量balls已经看到的球的总数moves把这些球全部移到当前位置所需的累计操作数。每次到达新位置i时moves就是左侧所有球到i的贡献直接累加到res[i]然后moves balls全体左侧球再右移一格再把当前位置的球并入balls。从右向左做同样的扫描把右侧贡献累加进res[i]。两次遍历之和即最终答案。算法步骤从左到右的遍历初始化balls 0, moves 0。对每个位置ires[i] balls moves随后moves balls最后若boxes[i] 1则balls 1。注意顺序先记录结果再更新 moves最后并入当前球。从右到左的遍历重置balls 0, moves 0。对每个位置i从n - 1到0res[i] balls moves随后moves balls最后并入当前球。返回res。多语言实现class Solution: def minOperations(self, boxes: str) - List[int]: n len(boxes) res [0] * n balls moves 0 for i in range(n): res[i] balls moves moves balls balls int(boxes[i]) balls moves 0 for i in range(n - 1, -1, -1): res[i] balls moves moves balls balls int(boxes[i]) return respublic class Solution { public int[] minOperations(String boxes) { int n boxes.length(); int[] res new int[n]; int balls 0, moves 0; for (int i 0; i n; i) { res[i] balls moves; moves balls; balls boxes.charAt(i) - 0; } balls moves 0; for (int i n - 1; i 0; i--) { res[i] balls moves; moves balls; balls boxes.charAt(i) - 0; } return res; } }class Solution { public: vectorint minOperations(string boxes) { int n boxes.size(); vectorint res(n, 0); int balls 0, moves 0; for (int i 0; i n; i) { res[i] balls moves; moves balls; balls boxes[i] - 0; } balls moves 0; for (int i n - 1; i 0; i--) { res[i] balls moves; moves balls; balls boxes[i] - 0; } return res; } };class Solution { /** * param {string} boxes * return {number[]} */ minOperations(boxes) { const n boxes.length; const res new Array(n).fill(0); let balls 0, moves 0; for (let i 0; i n; i) { res[i] balls moves; moves balls; balls Number(boxes[i]); } balls moves 0; for (let i n - 1; i 0; i--) { res[i] balls moves; moves balls; balls Number(boxes[i]); } return res; } }public class Solution { public int[] MinOperations(string boxes) { int n boxes.Length; int[] res new int[n]; int balls 0, moves 0; for (int i 0; i n; i) { res[i] balls moves; moves balls; balls boxes[i] - 0; } balls moves 0; for (int i n - 1; i 0; i--) { res[i] balls moves; moves balls; balls boxes[i] - 0; } return res; } }func minOperations(boxes string) []int { n : len(boxes) res : make([]int, n) balls, moves : 0, 0 for i : 0; i n; i { res[i] balls moves moves balls balls int(boxes[i] - 0) } balls, moves 0, 0 for i : n - 1; i 0; i-- { res[i] balls moves moves balls balls int(boxes[i] - 0) } return res }class Solution { fun minOperations(boxes: String): IntArray { val n boxes.length val res IntArray(n) var balls 0 var moves 0 for (i in 0 until n) { res[i] balls moves moves balls balls boxes[i] - 0 } balls 0 moves 0 for (i in n - 1 downTo 0) { res[i] balls moves moves balls balls boxes[i] - 0 } return res } }class Solution { func minOperations(_ boxes: String) - [Int] { let n boxes.count var res Int let chars Array(boxes) var balls 0 var moves 0 for i in 0..n { res[i] balls moves moves balls balls chars[i] 1 ? 1 : 0 } balls 0 moves 0 for i in stride(from: n - 1, through: 0, by: -1) { res[i] balls moves moves balls balls chars[i] 1 ? 1 : 0 } return res } }impl Solution { pub fn min_operations(boxes: String) - Veci32 { let n boxes.len(); let bytes boxes.as_bytes(); let mut res vec![0i32; n]; let mut balls 0i32; let mut moves 0i32; for i in 0..n { res[i] balls moves; moves balls; balls (bytes[i] - b0) as i32; } balls 0; moves 0; for i in (0..n).rev() { res[i] balls moves; moves balls; balls (bytes[i] - b0) as i32; } res } }class Solution { /** * param {string} boxes * return {number[]} */ minOperations(boxes: string): number[] { const n boxes.length; const res: number[] new Array(n).fill(0); let balls 0, moves 0; for (let i 0; i n; i) { res[i] balls moves; moves balls; balls Number(boxes[i]); } balls moves 0; for (let i n - 1; i 0; i--) { res[i] balls moves; moves balls; balls Number(boxes[i]); } return res; } }复杂度分析时间复杂度O(n)。两趟线性扫描。空间复杂度O(1) 额外空间不含输出数组输出数组本身占用 O(n)。增量计算的具体推演以boxes 110为例逐步推演第一趟从左到右过程位置 i进入循环前 balls, movesres[i] balls movesmoves ballsballs 当前球0balls0, moves0res[0] 0moves0balls11balls1, moves0res[1] 1moves1balls22balls2, moves1res[2] 3moves3balls2此时res [0, 1, 3]分别表示左侧球下标 0、1对位置 0、1、2 的贡献。第二趟从右到左同理累加右侧球本题中仅位置 2 右侧无球最终得到res [1, 1, 3]把两个球都移到盒子 0 需要 1 步下标 1 的球左移 1 格移到盒子 1 需要 1 步下标 0 的球右移 1 格移到盒子 2 需要 3 步。这个「先记录、再平移、后并入」的滚动更新手法与仓库内 Product of Array Except Self 一文中左右两次累乘得到除自身外乘积的思路完全同构本质上都是把全局信息所有球/所有元素拆成左侧信息 右侧信息用两趟遍历分别累积最终合成完整答案。三种解法对比解法时间额外空间核心技巧适用场景暴力法O(n²)O(1)直接按定义计算代码量最小适合快速验证思路前缀和法O(n)O(n)前缀个数 前缀下标和思路清晰便于公式化推导两趟遍历法O(n)O(1)滚动增量更新面试/竞赛最优解常见陷阱Common Pitfalls1. 字符与整数的比较错误输入boxes是字符串其中每个元素是字符0或1而不是整数。在大多数语言中写成boxes[i] 1而非boxes[i] 1会永远为false如 Java 中 char 与 int 比较虽然合法但字符1的码值是 49不等于 1导致算法看不见任何球结果全为 0。Python、JavaScript 等语言同样需要显式区分字符与数值可用int(boxes[i])、Number(boxes[i])或boxes[i] - 0完成转换。2. 两趟遍历中更新顺序错误在最优解法中res[i]、moves、balls三条语句的先后顺序至关重要。若在计算res[i]之前就执行balls ...把当前位置的球并入则当前位置自己的球会被错误地计入它到自身的移动代价本应为 0造成 off-by-one 误差。正确顺序永远是先用旧状态记录结果 → 再平移 moves → 最后并入新球。3. 左右贡献公式的越界off-by-one错误使用公式i * leftCount - leftSum计算左侧贡献时前缀数组是 0 基还是 1 基、用i还是i 1取前缀值会整体平移所有计算。务必先明确prefix[k]的语义本解法约定为前 k 个盒子的信息再核对左边界prefix[i]与右边界prefix[n] - prefix[i 1]是否分别对应[0, i)与(i, n)两个开区间确保当前盒子i既不重复计、也不被遗漏。总结「Minimum Number of Operations to Move All Balls to Each Box」是练习前缀和与两趟遍历的经典题目暴力法帮助建立直觉前缀和法展示信息复用两趟遍历法则把空间压到 O(1)。掌握这一左右拆解 增量更新的思维模式后可以顺藤摸瓜继续阅读仓库中的 Find Pivot Index前缀和的左右和比较与 Product of Array Except Self两趟累乘等文章它们共享同一套方法论一通百通。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考