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

从零学算法2833

2833.给你一个长度为 n 的字符串 moves ,该字符串仅由字符 ‘L’、‘R’ 和 ‘’ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。
你的初始位置就在原点(0),第 i 次移动过程中,你可以根据对应字符选择移动方向:
如果 moves[i] = ‘L’ 或 moves[i] = '
’ ,可以选择向左移动一个单位距离
如果 moves[i] = ‘R’ 或 moves[i] = '’ ,可以选择向右移动一个单位距离
移动 n 次之后,请你找出可以到达的距离原点 最远 的点,并返回 从原点到这一点的距离 。
示例 1:
输入:moves = “L_RL__R”
输出:3
解释:可以到达的距离原点 0 最远的点是 -3 ,移动的序列为 “LLRLLLR” 。
示例 2:
输入:moves = “R__LL
输出:5
解释:可以到达的距离原点 0 最远的点是 -5 ,移动的序列为 “LRLLLLL” 。
示例 3:
输入:moves = "
______"
输出:7
解释:可以到达的距离原点 0 最远的点是 7 ,移动的序列为 “RRRRRRR” 。

  • 我的思路:首先这可以看成一棵二叉树,所以直接 dfs。首先入参,为了知道遍历到哪里了,用一个 int 表示当前 moves 下标。由于可以向左或者向右,所以用两个 int 表示向两边移动的距离;递归出口,当遍历完这棵树也就是 moves 遍历到最后一个字符时返回 max(左距离,右距离)。如果在遍历的过程中发现遍历到某个点时已经遇到过此时向(左,右)移动了多少距离这种情况,那可以直接返回 0 了,因为这种可能性我们已经考虑过了(比如 l__r_,我们可能是 llrr_ ,也可能是lrlr_,那此时其实就是重复的情况了,遍历到第五个点的 _ 时都是还在原点);否则就看当前字符了,为 L 说明向左走了一步,左距离 加 1,相对应的,别忘了,这就代表着右距离减了 1, R 同理,如果为 _ 就返回 max(左,右)
  •   char[] moves;// l[i][j] 遍历到第 i 个点并且此时往左走了长度 jint[][] l;// // l[i][j] 遍历到第 i 个点并且此时往右走了长度 jint[][] r;public int furthestDistanceFromOrigin(String moves) {this.moves = moves.toCharArray();int n = this.moves.length;l=new int[n][n];r=new int[n][n];return dfs(0,0,0);}// left 和 right 最多只可能有一个大于 0,一正一负,或者都为 0int dfs(int cur,int left,int right){// 遍历完了if(cur==moves.length){return Math.max(left,right);}// 如果这种情况已经考虑过了 return 0if((left>=0 && l[cur][left]==1) || (right>=0 && r[cur][right]==1))return 0;// 如果在左边,记录这种情况if(left>=0)l[cur][left]=1;// // 如果在右边,记录这种情况if(right>=0)r[cur][right]=1;if(moves[cur]=='L')return dfs(cur+1,left+1,right-1);if(moves[cur]=='R')return dfs(cur+1,left-1,right+1);return Math.max(dfs(cur+1,left+1,right-1),dfs(cur+1,left-1,right+1));}
    
  • 其实这题我想的复杂了,因为当遇到 _ 时,你的选择丝毫不影响之后的选择。也就是说你只需要记录有几个 _ ,然后看剩下的 L 和 R 会让你走到哪里,如果在左边你就把 _ 都选择往左走,在右边同理。
  •   public int furthestDistanceFromOrigin(String moves) {int x=0;int distance=0;for(char c:moves.toCharArray()){if(c=='_')x++;else distance+=c=='L'?-1:1;}return x+Math.abs(distance);}
    

相关文章:

从零学算法2833

2833.给你一个长度为 n 的字符串 moves ,该字符串仅由字符 ‘L’、‘R’ 和 ‘’ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。 你的初始位置就在原点(0),第 i 次移动过程中,你可以根据对应字符选择移动方…...

python安装cfg模块时报错,ERROR: No matching distribution found for cfg

使用pip3 install cfg2 才行 pip3 install cfg2...

优思学院|六西格玛中的概率分布有哪些?

为什么概率分布重要? 概率分布是统计学中一个重要的概念,它帮助我们理解随机变量的分布情况以及与之相关的概率。在面对具体问题时,了解概率分布可以帮助我们选择适当的检验或分析策略,以解决问题并做出合理的决策。 常见的概率…...

工控上位机程序为什么只能用C语言?

工控上位机程序并不只能用C#开发,实际上在工业自动化领域中,常见的上位机开发语言包括但不限于以下几种:C#: C#是一种常用的编程语言,在工控领域中被广泛使用。它具有良好的面向对象特性和丰富的类库支持,可以实现高性…...

Go操作各大消息队列教程(RabbitMQ、Kafka)

Go操作各大消息队列教程 1 RabbitMQ 1.1 概念 ①基本名词 当前市面上mq的产品很多,比如RabbitMQ、Kafka、ActiveMQ、ZeroMQ和阿里巴巴捐献给Apache的RocketMQ。甚至连redis这种NoSQL都支持MQ的功能。 Broker:表示消息队列服务实体Virtual Host&#x…...

对话出海企业:2023亚马逊云科技出海日圆桌论坛

在全球经济亟待复苏的今天,持续对外开放是中国未来经济发展重要的“两条腿”之一。在愈发饱和的国内市场,中国企业需要对外寻找全新机遇才能在未来不确定的市场博弈下生存下去。“出海”,也成为近几年最炙手可热的词汇之一,大量中…...

【图解算法数据结构】分治算法篇 + Java代码实现

文章目录 一、重建二叉树二、数值的整数次方三、打印从 1 到最大的 n 位数四、二叉搜索树的后序遍历序列五、数组中的逆序对 一、重建二叉树 public class Solution {int[] preorder;HashMap<Integer, Integer> dic new HashMap<>();public TreeNode buildTree(in…...

Ubuntu系统环境搭建(八)——Ubuntu开机自动执行命令

ubuntu环境搭建专栏&#x1f517;点击跳转 Ubuntu系统环境搭建&#xff08;八&#xff09;——Ubuntu开机自动执行命令 修改文件 vim /etc/rc.local以自启动mysql为例&#xff0c;在文件末尾添加 /usr/local/mysql8/bin/mysqld_safe --defaults-file/usr/local/etc/my.cnf …...

c++(8.29)auto关键字,lambda表达式,数据类型转换,标准模板库,list,文件操作+Xmind

作业&#xff1a; 封装一个学生的类&#xff0c;定义一个学生这样类的vector容器, 里面存放学生对象&#xff08;至少3个&#xff09; 再把该容器中的对象&#xff0c;保存到文件中。 再把这些学生从文件中读取出来&#xff0c;放入另一个容器中并且遍历输出该容器里的学生。…...

Docker学习笔记(持续更新)

Docker学习目录 1.基础1.1 Docker简介1.1.1 Why Docker&#xff1f;1.1.2 Docker理念1.1.3 容器与虚拟机1.1.4 Docker能做什么&#xff1f; 1.2 Docker的基本组成1.2.1 Docker的三要素1.2.2 Docker平台架构 1.基础 1.1 Docker简介 1.1.1 Why Docker&#xff1f; 在个人笔记本…...

无涯教程-Android - 应用组件

应用程序组件是Android应用程序的基本组成部分&#xff0c;这些组件需要在应用程序清单文件 AndroidManifest.xml 注册&#xff0c;该文件描述了应用程序的每个组件以及它们如何交互。 Android应用程序可以使用以下四个主要组件- Sr.NoComponents & 描述1 Activities 它们…...

树与图c++

1.树 前言 本文主要介绍的数据结构之树型结构的相关知识&#xff0c;树型数据结构是面试官面试的时候非常喜欢考的一种数据结构&#xff0c;树形结构的遍历也是大厂笔试非常喜欢设置的考点&#xff0c;这些内容都会在本篇文章中进行详细的介绍&#xff0c;并且还会介绍一些常…...

中小企业常用的 IT 项目管理软件有哪些?

越热门&#xff0c;越贵的IT项目管理软件越好用吗&#xff1f;对于预算有限的中小型企业来说&#xff0c;如何选择一款适合自己的项目管理工具着实是个头疼的问题。 首先适用于中小型企业使用的 IT 项目管理软件需要具备哪些特点呢&#xff1f; 1、简单易用&#xff1a;中小企…...

汇编原理计算方法:物理地址=段地址*16+偏移地址

文章目录 计算方法计算错误分析 计算方法 根据进制的不同选择不同的计算方法 注意&#xff1a;物理地址、段地址和偏移地址的进制统一&#xff0c;要么都是二进制&#xff0c;要么都是十六进制&#xff0c;一般而言多是十六进制 若是二进制表达&#xff0c;则将段地址左移四…...

jdk-8u371-linux-x64.tar.gz jdk-8u371-windows-x64.exe 【jdk-8u371】 全平台下载

jdk-8u371 全平台下载 jdk-8u371-windows-x64.exejdk-8u371-linux-x64.rpmjdk-8u371-linux-x64.tar.gzjdk-8u371-macosx-x64.dmgjdk-8u371-linux-aarch64.tar.gz 下载地址 迅雷云盘 链接&#xff1a;https://pan.xunlei.com/s/VNdLL3FtCnh45nIBHulh_MDjA1?pwdw4s6 百度…...

数据结构体--5.0图

目录 一、定义 二、图的顶点与边之间的关系 三、图的顶点与边之间的关系 四、连通图 五、连通图的生成树定义 一、定义 图&#xff08;Graph&#xff09;是由顶点的又穷非空集合合顶点之间边的集合组成&#xff0c;通常表示为&#xff1a;G&#xff08;V&#xff0c;E&…...

深入剖析 Golang 程序启动原理 - 从 ELF 入口点到GMP初始化到执行 main!

大家好&#xff0c;我是飞哥&#xff01; 在过去的开发工作中&#xff0c;大家都是通过创建进程或者线程来工作的。Linux进程是如何创建出来的&#xff1f; 、聊聊Linux中线程和进程的联系与区别&#xff01; 和你的新进程是如何被内核调度执行到的&#xff1f; 这几篇文章就是…...

C语言——多文件编程

多文件编程 把函数声明放在头文件xxx.h中&#xff0c;在主函数中包含相应头文件在头文件对应的xxx.c中实现xxx.h声明的函数 防止头文件重复包含 当一个项目比较大时&#xff0c;往往都是分文件&#xff0c;这时候有可能不小心把同一个头文件 include 多次&#xff0c;或者头…...

Git学习part1

02.尚硅谷_Git&GitHub_为什么要使用版本控制_哔哩哔哩_bilibili 1.Git必要性 记录代码开发的历史状态 &#xff0c;允许很多人同时修改文件&#xff08;分布式&#xff09;且不会丢失记录 2.版本控制工具应该具备的功能 1&#xff09;协同修改 多人并行不悖的修改服务器端…...

2309C++均为某个类型

#include <常用> 构 A{空 f(){打印("啊");} }; 元<类 T>构 是点啊:假型{}; 元<>构 是点啊<A>:真型{}; 元<类 T>概念 是呀是点啊<T>::值;元<是呀...T>空 f(T&...t){(t.f(),...); }//均为元<类...T>要求 均为值&l…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...