【算法】1769. 移动所有球到每个盒子所需的最小操作数(java / c / c++ / python / go / rust
【摘要】 1769. 移动所有球到每个盒子所需的最小操作数:有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ,其中 boxes[i] 的值为 ‘0’ 表示第 i 个盒子是 空 的,而 boxes[i] 的值为 ‘1’ 表示盒子里有 一个 小球。在一步操作中,你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == ...
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’
分析
answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数,包含:
- 当前盒子的不用移动
- 左边盒子的小球与当前盒子的距离之和
- 右边盒子的小球与当前盒子的距离之和
乍看之下,每个位置都需要统计左边和右边的小球距离之和,O( )的节奏,但是如果我们能够复用前一个位置的结果,那就可以降低时间复杂度。
题解
java
class Solution {
public int[] minOperations(String boxes) {
int[] ans = new int[boxes.length()];
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
int ops = 0;
// 左边小球数量
int count = 0;
for (int i = 0; i < boxes.length(); ++i) {
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count;
ans[i] = ops;
if (boxes.charAt(i) == '1') {
count++;
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
for (int i = boxes.length() - 1; i >= 0; --i) {
ops += count;
ans[i] += ops;
if (boxes.charAt(i) == '1') {
count++;
}
}
return ans;
}
}
c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* minOperations(char * boxes, int* returnSize){
int len = strlen(boxes);
*returnSize = len;
int *ans = (int *) malloc(sizeof(int) * len);
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
int ops = 0;
// 左边小球数量
int count = 0;
for (int i = 0; i < len; ++i) {
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count;
ans[i] = ops;
if (boxes[i] == '1') {
count++;
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
for (int i = len - 1; i >= 0; --i) {
ops += count;
ans[i] += ops;
if (boxes[i] == '1') {
count++;
}
}
return ans;
}
c++
class Solution {
public:
vector<int> minOperations(string boxes) {
int n = boxes.length();
vector<int> ans;
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
int ops = 0;
// 左边小球数量
int count = 0;
for (int i = 0; i < n; ++i) {
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count;
ans.push_back(ops);
if (boxes[i] == '1') {
count++;
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
for (int i = n - 1; i >= 0; --i) {
ops += count;
ans[i] += ops;
if (boxes[i] == '1') {
count++;
}
}
return ans;
}
};
python
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
ans = []
# === 从左向右移动 ===
# 左边小球移动到当前位置的操作次数
ops = 0
# 左边小球数量
count = 0
for i in range(n):
# 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count
ans.append(ops)
if boxes[i] == '1':
count += 1
# === 从右左向移动 ===
# 右边小球移动到当前位置的操作次数
ops = 0
# 右边小球数量
count = 0
for i in range(n - 1, -1, -1):
# 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count
ans[i] += ops
if boxes[i] == '1':
count += 1
return ans
go
func minOperations(boxes string) []int {
n := len(boxes)
ans := make([]int, n)
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
ops := 0
// 左边小球数量
count := 0
for i, c := range boxes {
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count
ans[i] = ops
if c == '1' {
count++
}
}
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0
// 右边小球数量
count = 0
for i := n - 1; i >= 0; i-- {
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count
ans[i] += ops
if boxes[i] == '1' {
count++
}
}
return ans
}
rust
impl Solution {
pub fn min_operations(boxes: String) -> Vec<i32> {
let n = boxes.len();
let mut ans = vec![];
//===从左向右移动===
// 左边小球移动到当前位置的操作次数
let mut ops = 0;
// 左边小球数量
let mut count = 0;
boxes.chars().enumerate().for_each(|(i,c)|{
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count;
ans.push(ops);
if (c == '1') {
count += 1;
}
});
//===从右左向移动===
// 右边小球移动到当前位置的操作次数
ops = 0;
// 右边小球数量
count = 0;
boxes.chars().rev().enumerate().for_each(|(i,c)|{
// 每次移动,所有小球的操作次数都要加1,也就是操作次数需要增加小球的数量那么多次
ops += count;
ans[n - i - 1] += ops;
if (c == '1') {
count += 1;
}
});
ans
}
}
原题传送门:https://leetcode-cn.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://bbs.huaweicloud.cn/community/usersnew/id_1628396583336561 博客原创~
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)