【每日一题Day343】LC2731移动机器人 | 脑筋急转弯+数学
移动机器人【LC2731】
有一些机器人分布在一条无限长的数轴上,他们初始坐标用一个下标从 0 开始的整数数组
nums表示。当你给机器人下达命令时,它们以每秒钟一单位的速度开始移动。给你一个字符串
s,每个字符按顺序分别表示每个机器人移动的方向。'L'表示机器人往左或者数轴的负方向移动,'R'表示机器人往右或者数轴的正方向移动。当两个机器人相撞时,它们开始沿着原本相反的方向移动。
请你返回指令重复执行
d秒后,所有机器人之间两两距离之和。由于答案可能很大,请你将答案对109 + 7取余后返回。注意:
- 对于坐标在
i和j的两个机器人,(i,j)和(j,i)视为相同的坐标对。也就是说,机器人视为无差别的。- 当机器人相撞时,它们 立即改变 它们的前进方向,这个过程不消耗任何时间。
- 当两个机器人在同一时刻占据相同的位置时,就会相撞。
- 例如,如果一个机器人位于位置 0 并往右移动,另一个机器人位于位置 2 并往左移动,下一秒,它们都将占据位置 1,并改变方向。再下一秒钟后,第一个机器人位于位置 0 并往左移动,而另一个机器人位于位置 2 并往右移动。
- 例如,如果一个机器人位于位置 0 并往右移动,另一个机器人位于位置 1 并往左移动,下一秒,第一个机器人位于位置 0 并往左行驶,而另一个机器人位于位置 1 并往右移动。
-
思路
-
两个相同位置的机器人发生碰撞后,同时改变方向,相当于没有变化发生,可以近似为穿透,即每个机器人按照初始方向前进d个距离
-
将机器人的最终位置进行排序后,计算所有机器人之间两两距离之和
( n u m s [ i ] − n u m s [ i − 1 ] ) + . . . + ( n u m s [ i ] − n u m s [ 0 ] ) = i ∗ n u m s [ i ] − ( n u m s [ 0 ] + . . . + n u m s [ i − 1 ] ) (nums[i]-nums[i-1]) + ... + (nums[i]-nums[0]) = i * nums[i] - (nums[0] + ... +nums[i-1]) (nums[i]−nums[i−1])+...+(nums[i]−nums[0])=i∗nums[i]−(nums[0]+...+nums[i−1])
上述公式为第i个机器人与其左侧机器人的距离和,即 i ∗ n u m s [ i ] − 前缀和 i * nums[i] - 前缀和 i∗nums[i]−前缀和。从第0个机器人依次计算与其左侧机器人的距离和。
-
-
实现
class Solution {public static final int MOD = (int)(1e9 + 7);public int sumDistance(int[] nums, String s, int d) {// 两个相同位置的机器人发生碰撞后,同时改变方向,相当于没有变化发生,可以近似为穿透,即每个机器人按照初始方向前进d个距离// 将机器人的最终位置进行排序后,计算所有机器人之间两两距离之和// (nums[i]-nums[i-1]) + ... + (nums[i]-nums[0]) = i * nums[i] - (nums[0] + ... +nums[i-1])// 上述公式为第i个机器人与其左侧机器人的距离和,即 i * nums[i] - 前缀和。从第0个机器人依次计算与其左侧机器人的距离和。int n = nums.length;long[] arr = new long[n];for (int i = 0; i < n; i++){arr[i] = (long)(nums[i] + (s.charAt(i) == 'R' ? d : -d));}Arrays.sort(arr);long res = 0L, sum = 0L;for (int i = 0; i < n; i++){res = (res + i * arr[i] - sum) % MOD;sum += arr[i];}return (int)res;} }- 复杂度
- 时间复杂度: O ( n log n ) \mathcal{O}(n \log n ) O(nlogn)
- 空间复杂度: O ( n ) \mathcal{O}(n) O(n)
- 复杂度
相关文章:
【每日一题Day343】LC2731移动机器人 | 脑筋急转弯+数学
移动机器人【LC2731】 有一些机器人分布在一条无限长的数轴上,他们初始坐标用一个下标从 0 开始的整数数组 nums 表示。当你给机器人下达命令时,它们以每秒钟一单位的速度开始移动。 给你一个字符串 s ,每个字符按顺序分别表示每个机器人移动…...
疯狂java 1.7垃圾回收机制
内存泄漏:如果一些分配出去的内存得不到及时回收,就会引起系统运行速度下降,甚至导致程序瘫痪 Java程序的内存分配和回收都是由JRE在后台自动进行的。JRE会负责回收哪些不再使用的内存,这种机制被称为垃圾回收(Garbag…...
day01_基础
零、今日内容 1 jdk 2 idea使用 3 HelloWorld程序 4 变量 5 数据类型 6 String 一、JDK安装 JDK java开发工具包,敲代码的环境 1.1 卸载 控制面板 -> 卸载程序 -> 选择jdk,右键卸载 1.2 安装 注意: 现在安装的是JDK8版本,虽然最新的版本是21版本,但是工作市场中最流行的…...
RabbitMQ开启消息发送确认和消费手动确认
开启RabbitMQ的生产者发送消息到RabbitMQ服务端的接收确认(ACK)和消费者通过手动确认或者丢弃消费的消息。 通过配置 publisher-confirm-type: correlated 和publisher-returns: true开启生产者确认消息。 server:port: 8014spring:rabbitmq:username: …...
嵌入式系统开发【深入浅出】 GPIO 类设备的驱动程序
目录 GPIO管脚的输出功能相当于控制、输入相当于检测 使用GPIO基本流程 对于某一个管脚来说最多有几种功能? 拓展 【定时器与系统定时器】 决定定时长短的因素: 普通定时器 系统定时器 STM32F103RBT6的时钟源有哪五种 sysclk 的时钟频率由哪个时钟源提供基…...
项目管理必备的22个公式
大家好,我是老原。 趁着国庆时间比较空闲,给你们整理了一些项目管理必备的计算公式,一共22个。 每一个公式都给你们标注了适用情况和使用方法,为了方便你们理解,也加了一些例子,保准你看了就会。 觉得不…...
ccache加速编译速度
ccache https://gitee.com/lixiaoxmm/ccache.git 依赖hiredis、zstd(zstd的cmakelists.txt在build/cmake目录下) 下载mingw,https://www.mingw-w64.org/downloads/#w64devkit hiredis、zstd使用mingw编译 cmake -G “MinGW Makefiles” cmakecache.txt手动修改去掉网络下载,…...
Apache POI使用
1.导入坐标 <!-- poi --><dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>${poi}</version></dependency><dependency><groupId>org.apache.poi</groupId><a…...
UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323)
A - Weak Beats 链接 : A - Weak Beats 思路 : 模拟即可,如果在偶数位上出现了非0得元素,直接输出"No"后返回即可,循环顺利结束的话,就直接输出"Yes"; 代码 : #include<bits/stdc.h> #define IOS ios::sy…...
Docker 网络管理
Docker 网络实现原理 Docker使用Linux桥接,在宿主机虚拟一个Docker容器网桥(docker0),Docker启动一个容器时会根据Docker网桥的网段分配给容器一个IP地址,称为Container-IP,同时Docker网桥是每个容器的默认网关。因为在同一宿主机…...
网络安全国家队-安防思考与实践
按照工信部“三同步”安全建设的统一要求,本项目的实施应具备符合等级保护要求的安全防护措施(主要为传输控制、防火墙隔离、入侵检测、安全审计等网络安全措施;操作系统安全、数据库安全、防病毒管理、安全审计等基础系统安全措施࿰…...
epoll 定时器
参考: Linux下使用epoll监听定时器-CSDN博客 但是这个用的是gettimeofday。 本人使用的是 #include <stdlib.h> #include<stdio.h> #include <sys/timerfd.h> #include <sys/epoll.h> #include <unistd.h> #include <sys/time.…...
BUUCTF Java逆向解密 1
Class文件是Java编译后的二进制字节码文件。 我这里使用的是jadx-gui,直接将class文件拖进去即可 package defpackage;import java.util.ArrayList; import java.util.Scanner;/* renamed from: Reverse reason: default package */ /* loaded from: Reverse.clas…...
BUUCTF [MRCTF2020]Ez_bypass1
这道题全程我都是用bp做的 拿到题目 我们查看页面源代码得到 代码审计 我们要用get传入id和gg两个参数,id和gg的值要求不能相等,但是id和gg的md5强比较必须相等 if(isset($_GET[gg])&&isset($_GET[id])) {$id$_GET[id];$gg$_GET[gg];if (md5($…...
深入理解强化学习——强化学习和有监督学习
分类目录:《深入理解强化学习》总目录 通过前文的介绍,我们现在应该已经对强化学习的基本数学概念有了一定的了解。这里我们回过头来再看看一般的有监督学习和强化学习的区别。以图片分类为例,有监督学习(Supervised Learning&…...
设计模式 - 结构型模式考点篇:装饰者模式(概念 | 案例实现 | 优缺点 | 使用场景)
目录 一、结构型模式 1.1、装饰者模式 1.1.1、概念 1.1.2、案例实现 1.1.3、优缺点 1.1.4、使用场景 一、结构型模式 1.1、装饰者模式 1.1.1、概念 装饰者模式就是指在不改变现有对象结构的情况下,动态的给该对象增加一些职责(增加额外功能&#…...
计算机竞赛 题目:基于深度学习的手势识别实现
文章目录 1 前言2 项目背景3 任务描述4 环境搭配5 项目实现5.1 准备数据5.2 构建网络5.3 开始训练5.4 模型评估 6 识别效果7 最后 1 前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习的手势识别实现 该项目较为新颖,适合作为竞赛课题…...
手撕各种排序
> 作者简介:დ旧言~,目前大一,现在学习Java,c,c,Python等 > 座右铭:松树千年终是朽,槿花一日自为荣。 > 目标:掌握每种排序的方法,理解每种排序利弊…...
视频号的链接在哪,视频号视频链接地址获取办法!
不少人问视频号的链接在哪里可以获取,本质的在腾讯微信中目前视频号的链接是无法获取的,但好事多磨今天就分享一个第三方的视频号视频链接地址获取办法,希望对你有所帮助! 1:在微信客户端中,我们可以通过搜…...
深度学习笔记之优化算法(六)RMSprop算法的简单认识
深度学习笔记之优化算法——RMSProp算法的简单认识 引言回顾:AdaGrad算法AdaGrad算法与动量法的优化方式区别AdaGrad算法的缺陷 RMProp算法关于AdaGrad问题的优化方式RMSProp的算法过程描述 RMSProp示例代码 引言 上一节对 AdaGrad \text{AdaGrad} AdaGrad算法进行…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...
