Question

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

English Version

题目描述

有 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$ 的操作数，记为 $left[i]$；每个位置 $i$ 右边的小球移动到 $i$ 的操作数，记为 $right[i]$。那么答案数组的第 $i$ 个元素就是 $left[i] + right[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为 boxes 的长度。

我们还可以进一步优化空间复杂度，只用一个答案数组 $ans$ 以及若干个变量即可。

时间复杂度 $O(n)$，忽略答案数组的空间消耗，空间复杂度 $O(1)$。其中 $n$ 为 boxes 的长度。

class Solution:
  def minOperations(self, boxes: str) -> List[int]:
    n = len(boxes)
    left = [0] * n
    right = [0] * n
    cnt = 0
    for i in range(1, n):
      if boxes[i - 1] == '1':
        cnt += 1
      left[i] = left[i - 1] + cnt
    cnt = 0
    for i in range(n - 2, -1, -1):
      if boxes[i + 1] == '1':
        cnt += 1
      right[i] = right[i + 1] + cnt
    return [a + b for a, b in zip(left, right)]

class Solution {
  public int[] minOperations(String boxes) {
    int n = boxes.length();
    int[] left = new int[n];
    int[] right = new int[n];
    for (int i = 1, cnt = 0; i < n; ++i) {
      if (boxes.charAt(i - 1) == '1') {
        ++cnt;
      }
      left[i] = left[i - 1] + cnt;
    }
    for (int i = n - 2, cnt = 0; i >= 0; --i) {
      if (boxes.charAt(i + 1) == '1') {
        ++cnt;
      }
      right[i] = right[i + 1] + cnt;
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = left[i] + right[i];
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> minOperations(string boxes) {
    int n = boxes.size();
    int left[n];
    int right[n];
    memset(left, 0, sizeof left);
    memset(right, 0, sizeof right);
    for (int i = 1, cnt = 0; i < n; ++i) {
      cnt += boxes[i - 1] == '1';
      left[i] = left[i - 1] + cnt;
    }
    for (int i = n - 2, cnt = 0; ~i; --i) {
      cnt += boxes[i + 1] == '1';
      right[i] = right[i + 1] + cnt;
    }
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) ans[i] = left[i] + right[i];
    return ans;
  }
};

func minOperations(boxes string) []int {
  n := len(boxes)
  left := make([]int, n)
  right := make([]int, n)
  for i, cnt := 1, 0; i < n; i++ {
    if boxes[i-1] == '1' {
      cnt++
    }
    left[i] = left[i-1] + cnt
  }
  for i, cnt := n-2, 0; i >= 0; i-- {
    if boxes[i+1] == '1' {
      cnt++
    }
    right[i] = right[i+1] + cnt
  }
  ans := make([]int, n)
  for i := range ans {
    ans[i] = left[i] + right[i]
  }
  return ans
}

function minOperations(boxes: string): number[] {
  const n = boxes.length;
  const left = new Array(n).fill(0);
  const right = new Array(n).fill(0);
  for (let i = 1, count = 0; i < n; i++) {
    if (boxes[i - 1] == '1') {
      count++;
    }
    left[i] = left[i - 1] + count;
  }
  for (let i = n - 2, count = 0; i >= 0; i--) {
    if (boxes[i + 1] == '1') {
      count++;
    }
    right[i] = right[i + 1] + count;
  }
  return left.map((v, i) => v + right[i]);
}

impl Solution {
  pub fn min_operations(boxes: String) -> Vec<i32> {
    let s = boxes.as_bytes();
    let n = s.len();
    let mut left = vec![0; n];
    let mut right = vec![0; n];
    let mut count = 0;
    for i in 1..n {
      if s[i - 1] == b'1' {
        count += 1;
      }
      left[i] = left[i - 1] + count;
    }
    count = 0;
    for i in (0..n - 1).rev() {
      if s[i + 1] == b'1' {
        count += 1;
      }
      right[i] = right[i + 1] + count;
    }
    (0..n)
      .into_iter()
      .map(|i| left[i] + right[i])
      .collect()
  }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* minOperations(char* boxes, int* returnSize) {
  int n = strlen(boxes);
  int* left = malloc(sizeof(int) * n);
  int* right = malloc(sizeof(int) * n);
  memset(left, 0, sizeof(int) * n);
  memset(right, 0, sizeof(int) * n);
  for (int i = 1, count = 0; i < n; i++) {
    if (boxes[i - 1] == '1') {
      count++;
    }
    left[i] = left[i - 1] + count;
  }
  for (int i = n - 2, count = 0; i >= 0; i--) {
    if (boxes[i + 1] == '1') {
      count++;
    }
    right[i] = right[i + 1] + count;
  }
  int* ans = malloc(sizeof(int) * n);
  for (int i = 0; i < n; i++) {
    ans[i] = left[i] + right[i];
  }
  free(left);
  free(right);
  *returnSize = n;
  return ans;
}

方法二

class Solution:
  def minOperations(self, boxes: str) -> List[int]:
    n = len(boxes)
    ans = [0] * n
    cnt = 0
    for i in range(1, n):
      if boxes[i - 1] == '1':
        cnt += 1
      ans[i] = ans[i - 1] + cnt
    cnt = s = 0
    for i in range(n - 2, -1, -1):
      if boxes[i + 1] == '1':
        cnt += 1
      s += cnt
      ans[i] += s
    return ans

class Solution {
  public int[] minOperations(String boxes) {
    int n = boxes.length();
    int[] ans = new int[n];
    for (int i = 1, cnt = 0; i < n; ++i) {
      if (boxes.charAt(i - 1) == '1') {
        ++cnt;
      }
      ans[i] = ans[i - 1] + cnt;
    }
    for (int i = n - 2, cnt = 0, s = 0; i >= 0; --i) {
      if (boxes.charAt(i + 1) == '1') {
        ++cnt;
      }
      s += cnt;
      ans[i] += s;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> minOperations(string boxes) {
    int n = boxes.size();
    vector<int> ans(n);
    for (int i = 1, cnt = 0; i < n; ++i) {
      cnt += boxes[i - 1] == '1';
      ans[i] = ans[i - 1] + cnt;
    }
    for (int i = n - 2, cnt = 0, s = 0; ~i; --i) {
      cnt += boxes[i + 1] == '1';
      s += cnt;
      ans[i] += s;
    }
    return ans;
  }
};

func minOperations(boxes string) []int {
  n := len(boxes)
  ans := make([]int, n)
  for i, cnt := 1, 0; i < n; i++ {
    if boxes[i-1] == '1' {
      cnt++
    }
    ans[i] = ans[i-1] + cnt
  }
  for i, cnt, s := n-2, 0, 0; i >= 0; i-- {
    if boxes[i+1] == '1' {
      cnt++
    }
    s += cnt
    ans[i] += s
  }
  return ans
}

function minOperations(boxes: string): number[] {
  const n = boxes.length;
  const ans = new Array(n).fill(0);
  for (let i = 1, count = 0; i < n; i++) {
    if (boxes[i - 1] === '1') {
      count++;
    }
    ans[i] = ans[i - 1] + count;
  }
  for (let i = n - 2, count = 0, sum = 0; i >= 0; i--) {
    if (boxes[i + 1] === '1') {
      count++;
    }
    sum += count;
    ans[i] += sum;
  }
  return ans;
}

impl Solution {
  pub fn min_operations(boxes: String) -> Vec<i32> {
    let s = boxes.as_bytes();
    let n = s.len();
    let mut ans = vec![0; n];
    let mut count = 0;
    for i in 1..n {
      if s[i - 1] == b'1' {
        count += 1;
      }
      ans[i] = ans[i - 1] + count;
    }
    let mut sum = 0;
    count = 0;
    for i in (0..n - 1).rev() {
      if s[i + 1] == b'1' {
        count += 1;
      }
      sum += count;
      ans[i] += sum;
    }
    ans
  }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* minOperations(char* boxes, int* returnSize) {
  int n = strlen(boxes);
  int* ans = malloc(sizeof(int) * n);
  memset(ans, 0, sizeof(int) * n);
  for (int i = 1, count = 0; i < n; i++) {
    if (boxes[i - 1] == '1') {
      count++;
    }
    ans[i] = ans[i - 1] + count;
  }
  for (int i = n - 2, count = 0, sum = 0; i >= 0; i--) {
    if (boxes[i + 1] == '1') {
      count++;
    }
    sum += count;
    ans[i] += sum;
  }
  *returnSize = n;
  return ans;
}