预处理两个与 boxes 等长的数组 l 和 r:$l[i]$ 和 $r[i]$ 分别代表「将 $[0, i]$ 的小球移动到位置 $i$」以及「将 $[i, n - 1]$ 的小球移动到位置 $i$」所需要的步数。
所求的答案数组 ans 与数组 l 和 r 的关系为:$ans[i] = l[i] + r[i]$。
预处理两数组是简单的:分别从两个方向遍历 boxes,使用变量 cur 代表当前处理到的前缀/后缀的小球总个数,变量 step 代表将当前所有前缀/后缀小球移动到位置 $i$ 所需要的步数。
Java 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { publicint[] minOperations(String boxes) { intn= boxes.length(); int[] l = newint[n + 10], r = newint[n + 10]; for (inti=0, cur = 0, step = 0; i < n; i++) { step += cur; cur += boxes.charAt(i) - '0'; l[i] = step; } for (inti= n - 1, cur = 0, step = 0; i >= 0; i--) { step += cur; cur += boxes.charAt(i) - '0'; r[i] = step; } int[] ans = newint[n]; for (inti=0; i < n; i++) ans[i] = l[i] + r[i]; return ans; } }
TypeScript 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
functionminOperations(boxes: string): number[] { const n = boxes.length const l = newArray<number>(n + 10).fill(0), r = newArray<number>(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 = newArray<number>(n).fill(0) for (let i = 0; i < n; i++) ans[i] = l[i] + r[i] return ans }
Python 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: defminOperations(self, boxes: str) -> List[int]: n = len(boxes) l, r = [0] * n, [0] * n step, cur = 0, 0 for i inrange(n): step, cur = step + cur, cur + 1if boxes[i] == '1'else cur l[i] = step step, cur = 0, 0 for i inrange(n - 1, -1, -1): step, cur = step + cur, cur + 1if boxes[i] == '1'else cur r[i] = step return [l[i] + r[i] for i inrange(n)]