天津市南开区网站开发有限公司,网站开发技术指标是什么,为自家企业做网站,泰安网站建设xtempire文章目录1. 题目2. 解题1. 题目
有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes #xff0c;其中 boxes[i] 的值为 0 表示第 i 个盒子是 空 的#xff0c;而 boxes[i] 的值为 1 表示盒子里有 一个 小球。
在一步操作中#xff0c;你可以将 一个 小球从某个盒子移动到…
文章目录1. 题目2. 解题1. 题目
有 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
正反前缀和计算每个位置前面和后面的盒子移到该位置的步数
class Solution {
public:vectorint minOperations(string boxes) {int n boxes.size(), b 0;vectorint ans(n), temp(n);for(int i 0; i n; i){ans[i] b (i 0 ? ans[i-1] : 0);// 移动到前一个位置的步数 前面盒子的个数if(boxes[i]1)b;//前面的盒子个数}b 0;for(int i n-1; i 0; i--){temp[i] b (i n-1 ? temp[i1] : 0);if(boxes[i]1)b;ans[i] temp[i];//两侧的步数合并}return ans;}
};8 ms 8.9 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
