LeetCode-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 个盒子:将一个小球从第 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’
https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/description/
解题思路一:简单暴力,对每个位置单独计算。
class Solution {
public:
vector<int> minOperations(string boxes) {
int n=boxes.size();
vector<int> res(n);
for (int i=0;i<n;i ) {
int sm=0;
for (int j=0; j < n; j )
if (boxes[j]=='1') sm =abs(j-i);
res[i]=sm;
}
return res;
}
};
时间复杂度:O(n2)
空间复杂度:O(1)
解题思路二:根据前一个盒子的操作数得到下一个盒子的操作数,先初始化第0个位置的操作数和right的个数,遍历到下一个位置时操作数为operation lefti−righti
class Solution {
public:
vector<int> minOperations(string boxes) {
int left=boxes[0]-'0',right=0,operations=0;
int n=boxes.size();
for (int i=1;i<n;i ) {
if (boxes[i]=='1') {
right ;
operations = i;
}
}
vector<int> res(n);
res[0]=operations;
for (int i=1;i<n;i ) {
operations =left-right;
if (boxes[i]=='1') {
left ;
right--;
}
res[i]=operations;
}
return res;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
解题思路三:0
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggihge
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13