一、题目
有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。
在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。
每个 answer[i] 都需要根据盒子的 初始状态 进行计算。
二、示例
2.1> 示例 1：
【输入】boxes = "110"
【输出】[1,1,3]
【解释】每个盒子对应的最小操作数如下：
- 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
- 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
- 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。
2.2> 示例 2：
【输入】boxes = "001011"
【输出】[11,8,5,4,3,4]
提示：
- n == boxes.length
-
1<= n <=2000 - boxes[i] 为 '
0' 或 '1'
三、解题思路
3.1> 思路1：每当发现字符‘1’，则计算每个盒子的操作数
每当发现boxes字符串中存在字符“1”时，则针对这个位置计算每一个盒子的操作数。当遍历完boxes中所有字符之后，再针对于每个盒子，执行操作数的sum求和即可。
3.2> 思路2：根据前一个盒子的操作数，计算当前盒子的操作数
首先，我们需要3个变量：
【变量1】result[0]：第1个盒子的总操作数。
【变量2】lc：第i个盒子，它左侧'1'的总数。
【变量3】rc：第i个盒子，它右侧'1'的总数。
根据观察，我们可以得出如下结论，即：result[i] = result[i-1] + lc - rc。具体逻辑，如下图所示：
四、代码实现
4.1> 代码1：每当发现字符‘1’，则计算每个盒子的操作数
class Solution {
public int[] minOperations(String boxes) {
int[] result = new int[boxes.length()];
for (int i = 0; i < boxes.length(); i++) {
if (boxes.charAt(i) == '0') continue;
for (int j = 0; j < result.length; j++)
result[j] += Math.abs(j - i); // 当发现字符为'1'时，计算每个盒子的操作数。
}
return result;
}
}
4.2> 代码2：根据前一个盒子的操作数，计算当前盒子的操作数
class Solution {
public int[] minOperations(String boxes) {
int[] result = new int[boxes.length()];
char[] bc = boxes.toCharArray();
int rc = 0, lc = (bc[0] == '1' ? 1 : 0); // rc:右侧'1'的总数 lc:左侧'1'的总数
for (int i = 1; i < bc.length; i++)
if (bc[i] == '1') {
result[0] += i; // 初始化第1个盒子操作数
rc++; // 右侧'1'的总数加1
}
for (int i = 1; i < result.length; i++) {
result[i] = result[i-1] + lc - rc; // 第N个盒子操作数
if (bc[i] == '1') {
lc++; rc--; // 重新计算lc与rc的值
}
}
return result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论