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'
分析
answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数，包含：
- 当前盒子的不用移动
- 左边盒子的小球与当前盒子的距离之和
- 右边盒子的小球与当前盒子的距离之和
乍看之下，每个位置都需要统计左边和右边的小球距离之和，O(n2)的节奏，但是如果我们能够复用前一个位置的结果，那就可以降低时间复杂度。
题解
java
class Solution {
public int[] minOperations(String boxes) {
int[] ans = new int[boxes.length()];
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
int ops = 0;
// 左边小球数量
int count = 0;
for (int i = 0; i < boxes.length(); ++i) {
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count;
ans[i] = ops;
if (boxes.charAt(i) == '1') {
count++;
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
for (int i = boxes.length() - 1; i >= 0; --i) {
ops += count;
ans[i] += ops;
if (boxes.charAt(i) == '1') {
count++;
}
}
return ans;
}
}c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* minOperations(char * boxes, int* returnSize){
int len = strlen(boxes);
*returnSize = len;
int *ans = (int *) malloc(sizeof(int) * len);
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
int ops = 0;
// 左边小球数量
int count = 0;
for (int i = 0; i < len; ++i) {
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count;
ans[i] = ops;
if (boxes[i] == '1') {
count++;
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
for (int i = len - 1; i >= 0; --i) {
ops += count;
ans[i] += ops;
if (boxes[i] == '1') {
count++;
}
}
return ans;
}c++
class Solution {
public:
vector<int> minOperations(string boxes) {
int n = boxes.length();
vector<int> ans;
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
int ops = 0;
// 左边小球数量
int count = 0;
for (int i = 0; i < n; ++i) {
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count;
ans.push_back(ops);
if (boxes[i] == '1') {
count++;
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
for (int i = n - 1; i >= 0; --i) {
ops += count;
ans[i] += ops;
if (boxes[i] == '1') {
count++;
}
}
return ans;
}
};python
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
ans = []
# === 从左向右移动 ===
# 左边小球移动到当前位置的操作次数
ops = 0
# 左边小球数量
count = 0
for i in range(n):
# 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count
ans.append(ops)
if boxes[i] == '1':
count += 1
# === 从右左向移动 ===
# 右边小球移动到当前位置的操作次数
ops = 0
# 右边小球数量
count = 0
for i in range(n - 1, -1, -1):
# 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count
ans[i] += ops
if boxes[i] == '1':
count += 1
return ansgo
func minOperations(boxes string) []int {
n := len(boxes)
ans := make([]int, n)
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
ops := 0
// 左边小球数量
count := 0
for i, c := range boxes {
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count
ans[i] = ops
if c == '1' {
count++
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0
// 右边小球数量
count = 0
for i := n - 1; i >= 0; i-- {
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count
ans[i] += ops
if boxes[i] == '1' {
count++
}
}
return ans
}rust
impl Solution {
pub fn min_operations(boxes: String) -> Vec<i32> {
let n = boxes.len();
let mut ans = vec![];
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
let mut ops = 0;
// 左边小球数量
let mut count = 0;
boxes.chars().enumerate().for_each(|(i,c)|{
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count;
ans.push(ops);
if (c == '1') {
count += 1;
}
});
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
boxes.chars().rev().enumerate().for_each(|(i,c)|{
// 每次移动，所有小球的操作次数都要加1，也就是操作次数需要增加小球的数量那么多次
ops += count;
ans[n - i - 1] += ops;
if (c == '1') {
count += 1;
}
});
ans
}
}
原题传送门：https://leetcode-cn.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
