友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1769. 移动所有球到每个盒子所需的最小操作数
有 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'
思路分析
这道题可以理解成各个 1 到“本地”的距离之和。最容易想到的方案是，两重循环，计算当前节点到各个 1 的距离之和。
更取巧的解法是利用前缀和的原理，先从左到右，统计左侧有多少个 1, 从左侧到当前节点，则需要从左侧的操作次数再加上左侧节点的数量，这不就是“前缀和”吗？然后，分别计算左右两侧到当前节点的距离。最后，两组距离分别分别对应相加，则可以计算书最后结果。
-
一刷
-
一刷（优化）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-11 20:51:33
*/
public int[] minOperations(String boxes) {
int length = boxes.length();
int[] result = new int[length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (boxes.charAt(j) == '1') {
result[i] += Math.abs(i - j);
}
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-11 20:51:33
*/
public int[] minOperations(String boxes) {
int length = boxes.length();
int[] lop = new int[length];
int left = 0;
for (int i = 0; i < length; i++) {
if (i > 0) {
lop[i] = lop[i - 1] + left;
}
if (boxes.charAt(i) == '1') {
left++;
}
}
int right = 0;
int[] result = new int[length];
for (int i = length - 1; i >= 0; i--) {
if (i < length - 1) {
result[i] = result[i + 1] + right;
}
if (boxes.charAt(i) == '1') {
right++;
}
}
for (int i = 0; i < length; i++) {
result[i] = lop[i] + result[i];
}
return result;
}