题目

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

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

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

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

示例 1：

1
2
输入：boxes = "110"
输出：[1,1,3]

解释：每个盒子对应的最小操作数如下：

  1. 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
  2. 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
  3. 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

1
2
输入：boxes = "001011"
输出：[11,8,5,4,3,4]

提示：

n == boxes.length
1 <= n <= 2000
boxes[i] 为 '0' 或 '1'

解题思路

暴力：

先遍历一遍字符串，若为’1’则记录下来，然后遍历answer，每次将’1’所在的下标减去当前的下标就是我们移动次数。

前缀和

正序遍历一遍boxes计算出每个位置球到下一个位置要移动的次数，倒序遍历一遍boxes计算出每个球到下一个位置要移动的次数

代码

Python

暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        ball = []
        n = len(boxes)
        for i, x in enumerate(boxes):
            ball.append(i) if x == '1' else ...
        
        ans = [0] * n
        for i in range(n):
            cnt = 0
            for j in ball:
                cnt += abs(j - i)
            ans[i] = cnt
        return ans

前缀和

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        left, right = [0] * n, [0] * n
        cur = 0
        for i, c in enumerate(boxes):
            left[i], cur = left[i - 1] + cur, cur + (c == '1')
        cur = int(boxes[-1] == '1')
        for i in range(n - 2, -1, -1):
            right[i], cur = right[i + 1] + cur, cur + (boxes[i] == '1')
        return [left[i] + right[i] for i in range(n)]

C++

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> minOperations(string boxes) {
        vector<int> ball;
        int n = boxes.size();
        for (int i = 0; i < n; ++i) {
            if (boxes[i] == '1') ball.push_back(i);
        }
        
        vector<int> ans(n, 0);
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j: ball) {
                cnt += abs(j - i);
            }
            ans[i] = cnt;
        }
        return ans;
    }
};

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> ans(n, 0);
        vector<int> left(n, 0);
        vector<int> right(n, 0);
        int cur = (boxes[0] == '1');
        for (int i = 1; i < n; ++i) {
            char c = boxes[i];
            left[i] = left[i - 1] + cur;
            cur += (c == '1');
        }
        cur = (boxes[n - 1] == '1');
        for (int i = n - 2; i >= 0; i--) {
            char c = boxes[i];
            right[i] = right[i + 1] + cur;
            cur += (c == '1');
        }
        for (int i = 0; i < n; ++i) {
            ans[i] = left[i] + right[i];
        }
        return ans;
    }
};