题目描述

有 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 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
• 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
• 第 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’

方法一：两次遍历

class Solution {
public:vector minOperations(string boxes) {int n = boxes.size();vector flag;vector answer(n);// 一次遍历：保存有小球的下标for(int i=0; iif(boxes[i] == '1') flag.push_back(i);}// 二次遍历：小球下标和当前下标的差值就是操作次数for(int i=0; ifor(int j=0; janswer[i] += abs(flag[j] - i);}}return answer;}
};

方法二：方法一的优化-一次遍历
没必要保存小球下标的位置，直接计算即可

class Solution {
public:vector minOperations(string boxes) {int n = boxes.size();vector answer(n);// 一次遍历for(int i=0; i// 外层遍历移动目标盒子for(int j=0; j// 内层遍历盒子里是否有小球if(boxes[j] == '1') answer[i] += abs(j - i);}}return answer;}
};

方法三：方法二的优化，减少时间
首先考虑该盒子中是否有小球，如果有再继续考虑，没有的话直接遍历下一个小球

class Solution {
public:vector minOperations(string boxes) {int n = boxes.size();vector answer(n);for(int i=0; i// 外层遍历是否有小球需要移动if(boxes[i] == '0') continue;for(int j=0; j// 内层遍历要移动目标盒子answer[j] += abs(j - i);}}return answer;}
};

心得
这道题不算很难，一开始先用 动态规划 去做，但是我还是不太熟练，不太会去找临界条件，觉得有些麻烦，最后还是用最普通的思路，以下做介绍。

方法一：双重循环模拟

• 思路
  • 问题在于计算将 所有小球 移动到第 i 个盒子所需的 最小 操作数，并且每次只能移动 一个 小球。从第二个例子可以发现，第 j 个盒子里的小球移动到 第 i 个盒子，所需的操作数就是 abs（j - i） ，这里使用了 abs 是考虑到可能是将左边的小球移动到右边的盒子，此时 j - i 为负数。
  • 确定好 「abs（j - i）」之后，需要知道 j 的位置，因此我首先遍历了 boxes 数组，将有小球的盒子下标保存在 flag 数组里。
  • 之后只需要双重模拟循环，依次将每个盒子 i 与 flag 中有小球的盒子下标相减，就可以得到操作次数。
• 时间复杂度： O（n²）
• 空间复杂度： O（n）
  

方法二：双重循环模拟（方法一的优化）

• 思路
  • 总体思路和方法一差不多，考虑到 flag数组 有点多余，因为可以在双重循环的时候顺便判断该盒子里是否有小球，即 「 if ( boxes[j] == ‘1’ ) 」，因此方法二去掉了第一次遍历，空间复杂度降低了。
• 时间复杂度： O（n²）
• 空间复杂度： O（n）
  

方法三：双重循环模拟（方法二的优化）

• 思路
• 总体思路和方法二差不多，将内外层循环的定义做了调换，首先考虑遍历到的盒子里是否有小球，如果有的话再把它加入到移动目标盒子中。除了极端情况（每个盒子都有小球），这样子的遍历次数肯定会少于 n²，运行时间提高了一倍。
• 时间复杂度 < O（n²）
• 空间复杂度： O（n）