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'

方法一：双重循环模拟

思路

使用双重循环，第一层循环是遍历所有小球的目的地，第二层循环是计算把所有小球转移到某个目的地盒子的最小操作数，最后返回结果。

代码

[sol1-Python3]

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        res = []
        for i in range(len(boxes)):
            s = sum(abs(j - i) for j, c in enumerate(boxes) if c == '1')
            res.append(s)
        return res

[sol1-Java]

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int sm = 0;
            for (int j = 0; j < n; j++) {
                if (boxes.charAt(j) == '1') {
                    sm += Math.abs(j - i);
                }
            }
            res[i] = sm;
        }
        return res;
    }
}

[sol1-C#]

public class Solution {
    public int[] MinOperations(string boxes) {
        int n = boxes.Length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int sm = 0;
            for (int j = 0; j < n; j++) {
                if (boxes[j] == '1') {
                    sm += Math.Abs(j - i);
                }
            }
            res[i] = sm;
        }
        return res;
    }
}

[sol1-C++]

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            int sm = 0;
            for (int j = 0; j < n; j++) {
                if (boxes[j] == '1') {
                    sm += abs(j - i);
                }
            }
            res[i] = sm;
        }
        return res;
    }
};

[sol1-C]

int* minOperations(char * boxes, int* returnSize) {
    int n = strlen(boxes);
    int *res = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        int sm = 0;
        for (int j = 0; j < n; j++) {
            if (boxes[j] == '1') {
                sm += abs(j - i);
            }
        }
        res[i] = sm;
    }
    *returnSize = n;
    return res;
}

[sol1-JavaScript]

var minOperations = function(boxes) {
    const n = boxes.length;
    const res = [];
    for (let i = 0; i < n; i++) {
        let sm = 0;
        for (let j = 0; j < n; j++) {
            if (boxes[j] === '1') {
                sm += Math.abs(j - i);
            }
        }
        res.push(sm);
    }
    return res;
};

[sol1-Golang]

func minOperations(boxes string) []int {
    ans := make([]int, len(boxes))
    for i := range boxes {
        for j, c := range boxes {
            if c == '1' {
                ans[i] += abs(i - j)
            }
        }
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

复杂度分析

• 时间复杂度：O(n^2)，需要二重循环。

• 空间复杂度：O(1)，除了结果数组外，只需要常数空间。

方法二：根据前一个盒子的操作数得到下一个盒子的操作数

思路

记把所有球转移到当前下标为 i 的盒子的操作数为 operation}_i，初始情况下当前盒子及其左侧有 left}i 个球，右侧有 right}i 个球。那么，已知这三者的情况下，把所有球转移到当前下标为 i+1 的盒子的操作数 operation}{i+1 就可以由 operation}i + \textit{left}i - \textit{right}i 快速得出，因为原来左侧的 left}i 个球各需要多操作一步，原来右侧的 right}i 个球可以各少操作一步。计算完 operation}{i+1 后，需要更新 left}{i+1 和 right}{i+1。而初始的 operation}{0，left}{0 和 right}{0 可以通过模拟计算。

代码

[sol2-Python3]

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

[sol2-Java]

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

[sol2-C#]

public class Solution {
    public int[] MinOperations(string boxes) {
        int left = boxes[0] - '0', right = 0, operations = 0;
        int n = boxes.Length;
        for (int i = 1; i < n; i++) {
            if (boxes[i] == '1') {
                right++;
                operations += i;
            }
        }
        int[] res = new int[n];
        res[0] = operations;
        for (int i = 1; i < n; i++) {
            operations += left - right;
            if (boxes[i] == '1') {
                left++;
                right--;
            }
            res[i] = operations;
        }
        return res;
    }
}

[sol2-C++]

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int left = boxes[0] - '0', right = 0, operations = 0;
        int n = boxes.size();
        for (int i = 1; i < n; i++) {
            if (boxes[i] == '1') {
                right++;
                operations += i;
            }
        }
        vector<int> res(n);
        res[0] = operations;
        for (int i = 1; i < n; i++) {
            operations += left - right;
            if (boxes[i] == '1') {
                left++;
                right--;
            }
            res[i] = operations;
        }
        return res;
    }
};

[sol2-C]

int* minOperations(char * boxes, int* returnSize) {
    int left = boxes[0] - '0', right = 0, operations = 0;
    int n = strlen(boxes);
    for (int i = 1; i < n; i++) {
        if (boxes[i] == '1') {
            right++;
            operations += i;
        }
    }
    int *res = (int *)malloc(sizeof(int) * n);
    res[0] = operations;
    for (int i = 1; i < n; i++) {
        operations += left - right;
        if (boxes[i] == '1') {
            left++;
            right--;
        }
        res[i] = operations;
    }
    *returnSize = n;
    return res;
}

[sol2-JavaScript]

var minOperations = function(boxes) {
    let left = boxes[0].charCodeAt() - '0'.charCodeAt(), right = 0, operations = 0;
    const n = boxes.length;
    for (let i = 1; i < n; i++) {
        if (boxes[i] === '1') {
            right++;
            operations += i;
        }
    }
    const res = new Array(n).fill(0);
    res[0] = operations;
    for (let i = 1; i < n; i++) {
        operations += left - right;
        if (boxes[i] === '1') {
            left++;
            right--;
        }
        res[i] = operations;
    }
    return res;
}

[sol2-Golang]

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

复杂度分析

• 时间复杂度：O(n)，只需要遍历两次输入。

• 空间复杂度：O(1)，除了结果数组外，只需要常数空间。