跳转至

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

问题描述#

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

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

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

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

 

示例 1：

输入：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：

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

 

提示：

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

解题思路#

移动到第 \(i\) 个盒子的操作步数即其它位置与 \(i\) 的绝对差之和。

然后容易想到 \(\mathcal{O}(n^2)\) 的方案，直接遍历所有位置对即可。

方法一#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minOperations(self, s: str) -> List[int]:
        n = len(s)
        ans = [0] * n

        for i in range(n):
            for j in range(n):
                if s[j] == "1":
                    ans[i] += abs(i - j)

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> minOperations(string s) {
        int n = s.size();
        vector<int> ans(n);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (s[j] == '1') {
                    ans[i] += abs(j - i);
                }
            }
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}(n^2)\)
空间复杂度：\(\mathcal{O}(n)\)

方法二#

把某个位置 \(i\) 分成左右两边考虑，左边的球的数量为 \(k\)，所有位置之和为 \(t\)，则移动次数为 \(k\times i-t\)，右边同理为 \(t-k\times i\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minOperations(self, s: str) -> List[int]:
        n = len(s)
        ans = [0] * n

        k = t = 0
        for i in range(n):
            if s[i] == "1":
                k += 1
                t += i
            ans[i] = k * i - t

        k = t = 0
        for i in range(n - 1, -1, -1):
            if s[i] == "1":
                k += 1
                t += i
            ans[i] += t - k * i

        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
26
27
28
class Solution {
public:
    vector<int> minOperations(string s) {
        int n = s.size();
        vector<int> ans(n);
        int k, t;

        k = t = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                k += 1;
                t += i;
            }
            ans[i] = k * i - t;
        }

        k = t = 0;
        for (int i = n - 1; ~i; --i) {
            if (s[i] == '1') {
                k += 1;
                t += i;
            }
            ans[i] += t - k * i;
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)

返回顶部

在手机上阅读