当前位置: 首页 > news >正文

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. 第 1 个盒子:将一个小球从第 2 个盒子移动到第 1 个盒子,需要 1 步操作。
  2. 第 2 个盒子:将一个小球从第 1 个盒子移动到第 2 个盒子,需要 1 步操作。
  3. 第 3 个盒子:将一个小球从第 1 个盒子移动到第 3 个盒子,需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子,需要 1 步操作。共计 3 步操作。

n == boxes.length
1 <= n <= 2000
boxes[i] 为 ‘0’ 或 ‘1’

解法一:直接模拟:

class Solution {
public:vector<int> minOperations(string boxes) {int boxNum = boxes.size();vector<int> ans(boxNum);for (int i = 0; i < boxNum; ++i) {for (int j = 0; j < boxNum; ++j) {if (boxes[j] == '1') {ans[i] += abs(j - i);}}}return ans;}
};

如果有n个盒子,此算法时间复杂度为O(n2^22),空间复杂度为O(1)。

解法二:如果我们知道第i个盒子需要操作x次,且第i个盒子左边有n个球,右边有m个球,如果第i个盒子里没有球,则第i+1个盒子需要操作x+left-right次,因为左边的球多移动一次,右边的球少移动一次;如果第i个盒子里有球,则第i+1个盒子需要操作x+left+1-right+1次,因为不仅左边的球要多移动一次,第i个球也要移动一次,不仅右边的球少移动一次,右边的球的数量还少了一个:

class Solution {
public:vector<int> minOperations(string boxes) {int boxNum = boxes.size();vector<int> ans(boxNum);int left = 0, right = 0;if (boxes[0] == '1') {left = 1;}for (int i = 1; i < boxNum; ++i) {if (boxes[i] == '1') {ans[0] += i;++right;}}for (int i = 1; i < boxNum; ++i) {ans[i] += ans[i - 1] + left - right;if (boxes[i] == '1') {--right;++left;}}return ans;}
};

此算法时间复杂度为O(n),空间复杂度为O(1)。

相关文章:

LeetCode 1769. 移动所有球到每个盒子所需的最小操作数

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes &#xff0c;其中 boxes[i] 的值为 ‘0’ 表示第 i 个盒子是 空 的&#xff0c;而 boxes[i] 的值为 ‘1’ 表示盒子里有 一个 小球。 在一步操作中&#xff0c;你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。…...

MKS SKIPR V1.0船长版(Voron 2.4 R2)配置简要笔记

第一次用MKS SKIPR V1.0&#xff0c;设置过程中&#xff0c;也不知道怎么回事&#xff0c;跟现有的资料有些出入。首先&#xff0c;基本的配置调试可以参考官方的使用说明。 MKS SKIPR V1.0 使用说明书 这个说明比较简单&#xff0c;很多深一点的东西没有提现&#xff0c;不过…...

90后,转行软件测试3年,从月入7000+到月入过万,整理出的这一万字经验分享。

周一发工资了&#xff0c;到手12857.65&#xff0c;美滋滋 今年是我毕业参加工作的第3年&#xff0c;工资终于来到5位数了。上一家公司月薪7000&#xff0c;实际拿到手就6450左右&#xff0c;感觉今年真的是元气满满啊&#xff0c;工资翻倍&#xff0c;良好的人生开端。 想起…...

Java之关于String字符串笔试面试重点

目录 一.关于字符串的常量池 1.关于字符串产生的三种方式 2.关于字符串的常量池 3.直接赋值法和new的方式产生对象的区别 二.关于intern方法 1.情况一(已经包含) 2.情况二(已经包含) 3.情况三(未包含) 4.情况四 三.关于字符串的不可变性 1.了解字符串的不可变性 2.Str…...

mdio协议

1. 简介 MDIO接口中有特定的术语定义总线上的各种设备&#xff0c;驱动MDIO总线的设备被定义为站管理实体&#xff08;STA&#xff09;&#xff0c;而被MDC管理的目标设备称为可被MDIO管理的设备&#xff08;MMD&#xff09;。 STA初始化MDIO所有的通信&#xff0c;同时负责驱动…...

kubectl命令

kubectl命令是操作 Kubernetes 集群的最直接和最高效的途径。 1、kubectl自动补全 $ source <(kubectl completion bash) # setup autocomplete in bash, bash-completion package should be installed first. $ source <(kubectl completion zsh) # setup autocomple…...

题库-JAVASE01

文章目录1.JAVA开发环境2.JAVA变量3.JAVA基本类型4.运算符和表达式5.分支结构6.循环结构7.数组8.方法1.JAVA开发环境 (单选题)在Java中&#xff0c;以下描述错误的是&#xff08; &#xff09; A…class是源文件 B…java是编译前的源文件 C…class是编译后的文件 D.Java程序需…...

Java序列化机制

Java序列化机制 概述 java中的序列化可能都停留在实现Serializable接口上&#xff0c;对于它里面的一些核心机制没有深入了解过。直到最近在项目中踩了一个坑&#xff0c;就是序列化对象添加一个字段以后&#xff0c;使用方系统报了反序列化失败&#xff0c;原因是我们双方的…...

3款强大到离谱电脑软件,都是效率神器,从此远离加班

闲话少说&#xff0c;直接上狠货。 1、ImageGlass ImageGlass是一款值得吹爆的电脑图片浏览工具&#xff0c;使用极其方便&#xff0c;体积50M左右&#xff0c;非常小巧&#xff0c;功能却强大到离谱&#xff0c;ImageGlass打开图片的速度极快&#xff0c;实现快速不同图像间切…...

【项目】Vue3+TS CMS 登录模块搭建

&#x1f4ad;&#x1f4ad; ✨&#xff1a;Vue3 TS   &#x1f49f;&#xff1a;东非不开森的主页   &#x1f49c;: keep going&#x1f49c;&#x1f49c;   &#x1f338;: 如有错误或不足之处&#xff0c;希望可以指正&#xff0c;非常感谢&#x1f609;   Vue3TS一、…...

Java 8 的那些常见写法

前言 现在Java已经发展到Java19版本了&#xff0c;由于Java后面一些版本&#xff0c;就开始商用收费了&#xff0c;所以目前绝大多数公司的JDK版本都是采用的之前稳定且免费的1.8版本&#xff0c;也就是Java8&#xff0c;这个版本已经能满足几乎所有业务的需求开发了&#xff…...

PyQt5数据库开发1 4.3 QSqlTableModel 之 相关槽函数的实现(多图长文详解)

目录 一、打开数据库表 1. 写打开数据库的槽函数 2. 运行后发现数据库可以打开了 3. ODBC配通了&#xff0c;数据库还是打不开 4. 写在tableView上显示数据库表的函数 5. 运行后发现表可以显示了 6. 代码分析 7. 添加列名称 8. 根据内容调整列宽 9. 备注&#xff1a;…...

QT 设计一个串口调试工具,用一个工程就能轻松解决,外加虚拟串口工具模拟调试,在日常工作中可类比模块间通信,非常详细建议收藏

QT 串口调试工具第一节 虚拟串口工具安装第二节 QT创建一个基于QWidget的项目第三节 UI界面设计第三节 项目头文件widget.h第四节 项目实现文件widget.cpp第五节 main函数第六节 编译结果重点第七节 使用QT打包程序&#xff0c;不安装QT的电脑可使用第一节 虚拟串口工具安装 -…...

OpenSumi 是信创开发云的首选

原文作者&#xff1a;行云创新技术总监 邓冰寒 引言 随着云原生应用的日益普及&#xff0c;开发上云也逐步被越来越多的厂商和开发者接受&#xff0c;在这个赛道国内外有不少玩家&#xff0c;国外的 GitHub Codespaces、CodeSandbox&#xff0c;GitPod、亚马逊 Cloud9&#xf…...

JdbcTemplate常用方法解析

文章目录1.JdbcTemplate简介2.JdbcTemplate主要方法&#xff1a;3.常用方法介绍update()方法增删改query()查询方法1.JdbcTemplate简介 JdbcTemplate是Spring JDBC的核心类&#xff0c;借助该类提供的方法可以很方便的实现数据的增删改查。 Spring对数据库的操作在jdbc上面做…...

生物素标记试剂1869922-24-6,Alkyne-PEG3-Biotin PC,炔烃PEG3生物素PC

1、试剂基团反应特点&#xff08;Reagent group reaction characteristics&#xff09;&#xff1a;PC alkyne-PEG3-Biotin含一个炔烃和一个 PEG 链接的可光裂解生物素基团。含 3 个单元 PEG 的 ADC linker&#xff0c;生物素本身是个游离的小分子&#xff0c;在生物实验中常常…...

CS224W课程学习笔记(三):DeepWalk算法原理与说明

引言 什么是图嵌入&#xff1f; 图嵌入&#xff08;Graph Embedding&#xff0c;也叫Network Embedding&#xff09; 是一种将图数据&#xff08;通常为高维稠密的矩阵&#xff09;映射为低微稠密向量的过程&#xff0c;能够很好地解决图数据难以高效输入机器学习算法的问题。…...

rk3568 开发板Ubuntu系统说明

Ubuntu MinimalUbuntu Minimal系统基于Ubuntu 64bit系统构建&#xff0c;目前发布有Ubuntu18.04这个版本。与Ubuntu Desktop 相比具有以下特性&#xff1a;没有桌面环境&#xff0c;占用资源少&#xff0c;在简化网络管理之后&#xff0c;只需40M内存&#xff1b;针对嵌入式平台…...

Windows和Linux常用HASH算法使用命令

Windows和Linux常用hash算法使用命令 Windows&#xff0c;以文件xxx.zip为例 Windows 求文件 md5 certutil -hashfile xxx.zip md5Windows 求文件 sha1 certutil -hashfile xxx.zip sha1Windows 求文件 sha256 certutil -hashfile xxx.zip sha256Linux&#xff0c;以文件xxx.z…...

货仓选址 AcWing(JAVA)

在一条数轴上有 N家商店&#xff0c;它们的坐标分别为 A1∼AN。 现在需要在数轴上建立一家货仓&#xff0c;每天清晨&#xff0c;从货仓到每家商店都要运送商品。 为了提高效率&#xff0c;求把货仓建在何处&#xff0c;可以使得货仓到每家商店的距离之和最小。 输入格式&#…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践

在电商行业蓬勃发展的当下&#xff0c;多平台运营已成为众多商家的必然选择。然而&#xff0c;不同电商平台在商品数据接口方面存在差异&#xff0c;导致商家在跨平台运营时面临诸多挑战&#xff0c;如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...