[LeetCode] 1769. Minimum Number of Operations to Move All Balls to Each Box

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Constraints:

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] is either '0' or '1'.

移动所有球到每个盒子所需的最小操作数。

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题我提供两种思路，一种是暴力解，一种是类似前缀和。

暴力解，对于字符串 boxes 的每一个位置 i，把位置 i 当做目标位置，然后对于其他所有的index j，我们计算一下如果 j 位置上的数字是 1 的话，这个 1 移动到位置 i 的花费是多少。

时间O(n^2)

空间O(n) - output array

Java实现

 1 class Solution {
 2     public int[] minOperations(String boxes) {
 3         int len = boxes.length();
 4         int[] res = new int[len];
 5         for (int i = 0; i < len; i++) {
 6             res[i] = helper(boxes, i);
 7         }
 8         return res;
 9     }
10     
11     private int helper(String s, int index) {
12         int res = 0;
13         int len = s.length();
14         for (int i = 0; i < len; i++) {
15             if (i != index) {
16                 int c = s.charAt(i) - '0';
17                 res += c * Math.abs(i - index);
18             }
19         }
20         return res;
21     }
22 }

另外一种思路是类似前缀和，需要从左往右和从右往左各扫描一次。对于中间的任何一个位置 i 来说，如果他左边的位置 i - 1 是一个1，那么这个 1 走到 i 位置的花费是 1 步。按照这个逻辑，我们就可以从左往右试着累加 1 走到任何一个位置的花费。比如 index = 0 位置上是一个 1 好了，那么对于 index = 1 这个位置而言，他的左侧的所有数字走到这个位置上的花费 = 左侧所有的 1 走到 i - 1 位置上的花费 + i - 1 位置上的所有的 1 走到位置 i 的花费。对于任何一个位置，因为右侧也有可能有 1 ，所以需要从左往右，从右往左各自扫描一遍。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int[] minOperations(String boxes) {
 3         int len = boxes.length();
 4         int[] res = new int[len];
 5         int[] left = new int[len];
 6         int[] right = new int[len];
 7 
 8         int count = boxes.charAt(0) - '0';
 9         for (int i = 1; i < len; i++) {
10             left[i] = left[i - 1] + count;
11             count += boxes.charAt(i) - '0';
12         }
13 
14         count = boxes.charAt(len - 1) - '0';
15         for (int i = len - 2; i >= 0; i--) {
16             right[i] = right[i + 1] + count;
17             count += boxes.charAt(i) - '0';
18         }
19 
20         for (int i = 0; i < len; i++) {
21             res[i] += left[i];
22             res[i] += right[i];
23         }
24         return res;
25     }
26 }

LeetCode 题目总结