【算法学习】1769. 移动所有球到每个盒子所需的最小操作数(java / c / c++ / python / go / rust)

二当家的白帽子 2021-10-27 00:35:43
学习 算法 移动 每个 法学

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~



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(n2)的节奏,但是如果我们能够复用前一个位置的结果,那就可以降低时间复杂度。


题解

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://le-yi.blog.csdn.net/article/details/120785658

  1. 用python实现千图成像工具,快给你的男/女神弄一张吧~
  2. python csv中dwlimiter用不了,有没有大咖能解释一下
  3. 新手学Python要打好哪些基础?从软件安装到全面基础讲解,就它了!
  4. Python中字符串子串的输出
  5. python判断是否一个序列是超增序列
  6. Python爬虫框架的读取和创建
  7. python对数据框中两列进行判断, 得到新的列的
  8. Python做一个模仿文本进度条的编程
  9. python 中使用MS SQL问题 怎样解决
  10. python有没有类似传送门功能的代码,,就是比如这边运行完然后输入一些指令然后可以跳转到程序里的某个地方
  11. Python基操教学!不会?(熟能生巧)
  12. python画图,有没有初学者的代码
  13. 朋友股票亏惨了,我一怒用Python爬取了证券最新数据
  14. 被称之为永远的神!就这6个Python爬虫开源项目?
  15. python Qtreeview 如何选择子行,选择第一行下面的行数
  16. Python随机生成100个1~200之间的不重复数字
  17. 关于#python#的问题,请各位专家解答!
  18. Python编写程序先输入一组10个元素,再输入数组中比平均值小的所有奇数
  19. Ubuntu终端下安装Python需要import的库
  20. 为什么下载pandas和xlwings运行不了,出现No system module pywintypes(系统查不到pywin32具体位置)(又不能重新下载pywin32)
  21. python求带我脱离苦海,哎_
  22. Python 数据分析里面轴的问题
  23. python初学者,请问使用openpyxl库读取文件后出现图片中的报错要怎么解决?
  24. 大学毕业论文写有关python
  25. 授人以鱼吧友友python编写程序自动计算个人总分平均分各科最高最低平均分
  26. python怎么将四行代码换成一行啊
  27. 用Python如何编写啊 真不会啊?
  28. 这个布尔变化怎么做啊(Python
  29. PYTHON求集合交集需要用户手动输入集合名
  30. Python运行哈姆雷特词频统计时出错(如图),是哪方面的问题?
  31. 【Python表白代码合集】”我还是很喜欢你,像风走了八千里,不问归期”!!
  32. python实现学生信息管理系统(含代码)
  33. wxpython中如何按键停止死循环?
  34. python 类的问题?不懂这种方法的作用?不是继承那是什么作用?
  35. Python 题目不会写 求帮助!
  36. Python,turtle制图,要求使用for,while编写
  37. Python题目不会 求帮助! 谢谢您!
  38. Python题目不会!求帮助!
  39. Python这个看不太懂,,大神们帮个忙
  40. 安装拓展库pandas失败怎么解决
  41. python将字符串转成特定列表格式
  42. Python做一个保护手机号编程
  43. 用Spyder运行Python爬虫时仅输出“runfile(xx), wdir=xx”
  44. 使用Python对一组数据进行分段拟合,如何处理断点处的左右倒数相等
  45. Python输出符合条件的文件的路径名
  46. Python中pandas怎么实现分组去重统计和求和
  47. python xpath 爬虫,请帮帮我吧!
  48. python 用泰勒公式近似计算sinx的值 求解代码中哪里出现了错误
  49. Python语法2
  50. python如何将输出的各行数字对齐
  51. 使用 Python 进行数据可视化之Matplotlib
  52. python新鲜题 老公们 救救孩子
  53. 如何用python解答 要如何着手
  54. 请问Python正则表达式如何在多个文本中匹配出关键字
  55. Python 三天打鱼两天晒网问题
  56. mac安装python3
  57. 請問python要怎麼印数字倒等腰三角形
  58. 【算法学习】807. 保持城市天际线(java / c / c++ / python / go / rust)
  59. 【算法学习】1512. 好数对的数目(java / c / c++ / python / go / rust)
  60. 【算法学习】剑指 Offer 64. 求1+2+…+n(java / c / c++ / python / go / rust)