[leetcode每日一题]12.2

​​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'​​

Solution

我的做法是开两个前缀和和后缀和数组，记录下前面的小球和后面的小球移动到当前位置需要的次数，然后相加。

class Solution {
  List<int> minOperations(String boxes) {
      var n = boxes.length;
      var l = '1'.allMatches(boxes).length;
      List<int> prefix = List<int>.filled(n+2, 0);
      List<int> suffix = List<int>.filled(n+2, 0);
      var x = 0;
      var y = 0;
      for(int i=1;i<=n;i++){
        if(boxes[i-1]=='1')x++;
        prefix[i] = prefix[i-1] + x;
      }
      for(int i=n;i>0;i--){
        if(boxes[i-1]=='1')y++;
        suffix[i] = suffix[i+1] + y;
      }
    //   print(prefix);
    //   print(suffix);
      List<int> ans =List<int>.filled(n, 0);
      for(int i=0;i<n;i++){
          ans[i] = prefix[i] + suffix[i+2];
      }
      return ans;
  }
}

看了题解的做法是正着遍历一遍，求出都移动到最右边所需的操作数和球数。之后通过数学关系通过相邻的盒子的次数求出当前盒子次数。

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        left, right, operations = int(boxes[0]), 0, 0
        for i in range(1, len(boxes)):
            if boxes[i] == '1':
                right += 1
                operations += i
        res = [operations]
        for i in range(1, len(boxes)):
            operations += left - right
            if boxes[i] == '1':
                left += 1
                right -= 1
            res.append(operations)
        return res

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/solution/yi-dong-suo-you-qiu-dao-mei-ge-he-zi-suo-y50e/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。