【每日一题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算法进行…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
