LeetCode_前缀和_中等_1769.移动所有球到每个盒子所需的最小操作数

ゞ浴缸里的玫瑰 2023-10-07 21:43 7阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

有 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’

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法比较容易想到，即使用**两层 for 循环来进行遍历**，第一层 for 循环遍历所有小球要移动到的目的地，即 n 个盒子；第二层 for 循环则计算把所有小球转移到某个目的地盒子的最小操作数，将第二层循环结束后的结果存储到数组 answer 中，待两层循环都结束后返回 answer 即可。不过该方法的时间复杂度较高，为 O(n2)，方法 2 将对其进行优化。

（2）前缀和 & 后缀和  
为了优化方法 1，我们可以通过两次遍历的方法来求解答案：  
① 第一次遍历：从前往后遍历，计算将前面盒子中的所有球移动到当前位置 i 上需要的最小操作数，并将答案记录到数组 answer 中；  
② 第二次遍历：从后往前遍历，计算将后面盒子中的所有球移动到当前位置 i 上需要的最小操作数，数组 answer 累加第一次遍历的答案；  
上述两次遍历结束后，数组 answer 中记录的便是题目要的答案，直接返回即可。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int[] minOperations(String boxes) {
        
            int n = boxes.length();
            int[] answer = new int[n];
            for (int i = 0; i < n; i++) {
        
                int minCnt = 0;
                for (int j = 0; j < n; j++) {
        
                    if (boxes.charAt(j) == '1') {
        
                        minCnt += Math.abs(j - i);
                    }
                }
                answer[i] = minCnt;
            }
            return answer;
        }
    }

//思路2————前缀和 & 后缀和
    class Solution {
        
        public int[] minOperations(String boxes) {
        
            int n = boxes.length();
            int[] answer = new int[n];
            int pre = 0;
            int cnt = 0;
            //从前往后遍历，计算将前面盒子中的所有球移动到当前位置 i 上需要的最小操作数
            for (int i = 1; i < n; i++) {
        
                if (boxes.charAt(i - 1) == '1') {
        
                    cnt++;
                }
                answer[i] += pre + cnt;
                pre += cnt;
            }
            //从后往前遍历，计算将后面盒子中的所有球移动到当前位置 i 上需要的最小操作数
            int suf = 0;
            cnt = 0;
            for (int i = n - 2; i >= 0; i--) {
        
                if (boxes.charAt(i + 1) == '1') {
        
                    cnt++;
                }
                answer[i] += suf + cnt;
                suf += cnt;
            }
            return answer;
        }
    }