1769.minimum-number-of-operations-to-move-all-balls-to-each-box.md

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

朴素解法

算法思路

• f[i][j] 表示将第 i 个位置的球移动到 j 位置需要的最小操作数
• answer[i] = 所有f[0,...,boxes.length-1][i]的和

时间复杂度

O(N^2)

代码实现

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[][] f = new int[n][n];

        for (int i = 0; i < n; i++) {
            if (boxes.charAt(i) == '1') {
                for (int j = 0; j < n; j++) {
                    f[i][j] = Math.abs(i - j);
                }
            }
        }

        int[] res = new int[n];
        for (int i =0;i<n; i++){
            for (int j = 0; j< n; j++){
                res[i] += f[j][i];
            }
        }
        return res;
    }
}

前缀和

算法思路

• 定义一个前缀和数组，一个后缀和数组
• 前缀和数组每个元素的值 等于 当前位置左边的小球移动到当前位置需要的操作数
• 同理，后缀和数组每个元素的值 等于 当前位置右边的小球移动到当前位置需要的操作数
• 返回前缀和数组和后缀和数组合并后的结果，即所得

时间复杂度

O(N)

代码实现

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        if (n < 2) {
            return new int[n];
        }
        int[] pre = new int[n];
        int[] suf = new int[n];

        // i:前缀和下标；k:当前位置左边有多少个球
        for (int i = 1, k = 0; i < n; i++) {
            if (boxes.charAt(i - 1) == '1') k++;
            pre[i] = pre[i - 1] + k;
        }

        for (int i = n - 2, k = 0; i >= 0; i--) {
            if (boxes.charAt(i + 1) == '1') k++;
            suf[i] = suf[i + 1] + k;
        }

        for (int i = 0; i <n; i++){
            pre[i] += suf[i];
        }
        return pre;
    }
}