当前位置: 首页 > 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…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

HTML 语义化

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

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...