移动所有球到每个盒子所需要的最小操作数【LC1769】

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

我承认我飘了

暴力

• 思路：暴力

如果第j jj个盒子里装有小球，那么移到到第i ii个盒子，所需要的操作数为a b s ( j − i ) abs(j-i)abs(j−i)，累加计算总和既可

• 实现

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

。复杂度

• 时间复杂度：O(n ² )
• 空间复杂度：O ( 1 )

贡献

• 思路：将所有球移入盒子i 所需要的操作数取决于其右侧盒子内的小球和左侧盒子内的小球至其的距离，最终操作数即为距离的累加和。因此盒子i+1所需要的操作数，可以由盒子i ii所需要的操作数推出。

。假设所有球移入盒子i 所需要的操作数为r e s _i ，右侧盒子的小球个数为r i g h t _i ，左侧盒子的小球个数为l e f t _i （包括其自身），那么盒子i+1所需要的操作数为 res_i+left_i-right_i

• 实现

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

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )