LeetCode-1138. 字母板上的路径【哈希表,字符串】
LeetCode-1138. 字母板上的路径【哈希表,字符串】
- 题目描述:
- 解题思路一:首先考虑坐标位置,字符是有序的从0开始,当前字符c的行为(c-'a')/5,列为(c-'a')%5。其次是考虑特殊情况'z'。若当前从‘z’开始则只能往上走;若是其他字符到'z'统一先往左走再往下走。那么每次移动时优先保证选择上移和左移即可。
- 解题思路二:优化判断条件。
- 解题思路三:0
题目描述:
我们从一块字母板上的位置 (0, 0) 出发,该坐标对应的字符为 board[0][0]。
在本题里,字母板为board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”],如下所示。

我们可以按下面的指令规则行动:
如果方格存在,‘U’ 意味着将我们的位置上移一行;
如果方格存在,‘D’ 意味着将我们的位置下移一行;
如果方格存在,‘L’ 意味着将我们的位置左移一列;
如果方格存在,‘R’ 意味着将我们的位置右移一列;
‘!’ 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
(注意,字母板上只存在有字母的位置。)
返回指令序列,用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。
示例 1:
输入:target = “leet”
输出:“DDR!UURRR!!DDD!”
示例 2:
输入:target = “code”
输出:“RR!DDRR!UUL!R!”
提示:
1 <= target.length <= 100
target 仅含有小写英文字母。
https://leetcode.cn/problems/alphabet-board-path/description/
解题思路一:首先考虑坐标位置,字符是有序的从0开始,当前字符c的行为(c-‘a’)/5,列为(c-‘a’)%5。其次是考虑特殊情况’z’。若当前从‘z’开始则只能往上走;若是其他字符到’z’统一先往左走再往下走。那么每次移动时优先保证选择上移和左移即可。
class Solution {
public:string alphabetBoardPath(string target) {string ans;int x = 0, y = 0;//当前位置for (char c:target) {int nx=(c-'a')/5,ny=(c-'a')%5;//目标位置(x是行,y是列)if(nx<x) ans.append(x-nx,'U');//目标行小,在上边添加x-nx个'U'if(ny<y) ans.append(y-ny,'L');//目标列小,在左边添加y-ny个'L'if(nx>x) ans.append(nx-x,'D');//目标行大,在下边添加nx-x个'D'if(ny>y) ans.append(ny-y,'R');//目标列大,在右边添加ny-y个'R'ans.push_back('!');//取当前字符x=nx,y=ny;//更新当前位置}return ans;}
};
时间复杂度:O(n*(r+c))//其中 n表示给定字符串的长度,r表示字母板的行数, c表示字母板的列数。每次移动到新的字符生成移动指令时,需要的时间复杂度为r+c,一共需要生成指令 n 次,因此时间复杂度为O(n×(r+c))。
空间复杂度:O(1)
解题思路二:优化判断条件。
class Solution {
public:string alphabetBoardPath(string target) {string ans;int x = 0, y = 0;//当前位置for (char c:target) {int nx=(c-'a')/5,ny=(c-'a')%5;//目标位置(x是行,y是列)string v(abs(nx-x), "UD"[nx > x]);//竖直(例如nx>x,那么条件为true即是1,取的是nx-x个'D')string h(abs(ny-y), "LR"[ny > y]);//水平ans+=(c!='z'?v+h:h+v)+"!";//是z则先竖直后水平,非z相反x=nx,y=ny;//更新当前位置}return ans;}
};
时间复杂度:O(n*(r+c))//其中 n表示给定字符串的长度,r表示字母板的行数, c表示字母板的列数。每次移动到新的字符生成移动指令时,需要的时间复杂度为r+c,一共需要生成指令 n 次,因此时间复杂度为O(n×(r+c))。
空间复杂度:O(1)
解题思路三:0
相关文章:
LeetCode-1138. 字母板上的路径【哈希表,字符串】
LeetCode-1138. 字母板上的路径【哈希表,字符串】题目描述:解题思路一:首先考虑坐标位置,字符是有序的从0开始,当前字符c的行为(c-a)/5,列为(c-a)%5。其次是考虑特殊情况z。若当前从‘z’开始则只能往上走;若是其他字符…...
Vue 可配置化的路由缓存(Vu2 Vue3)
Vue 可配置化的路由缓存(Vu2 & Vue3) 1 介绍 在Vue的项目当中,路由缓存是一个比较常见的功能,譬如,从列表页面进入到详情页面,返回到列表页面时,如果可以保持列表的状态,那用户…...
Linux VPU驱动
1. 前言 限于作者能力水平,本文可能存在谬误,因此而给读者带来的损失,作者不做任何承诺。 2. 概述 VPU 是用来进行图像、视频数据进行硬件编、解码的硬件模块。内部集成了 Encoder、Decoder 功能部件进行图像、视频数据进行硬件编、解码&a…...
spring 笔记
一、spring概述 1.1 spring介绍 spring是一个轻量级的控制反转和面向切面的容器框架,用来解决企业项目开发的复杂度问题---解耦 轻量级:体积小,对代码没有侵入性控制反转:IOC inverse of control, 把创建对象的工作交…...
Java日志框架学习
首先,Java日志框架可以分为两类:门面型日志框架和记录型日志框架。 门面型日志框架 JCL:Java日志接口,后更名为Commons LoggingSLF4J:是一套简易Java日志门面,本身并无日志的实现 记录型日志框架 JUL&a…...
基础面试题:堆和栈的区别
面试题:堆和栈的区别(往往讲的是内存zha) 为什么说访问栈栈比访问堆快些? 目录 一、数据结构中的堆栈 1、数据结构中的堆 1)堆的定义 2)堆的效率 2、 数据结构中的栈 二、内存中的堆栈 1、内存堆的定义…...
(干货教程)在VSCode并使用chatgtp插件编写CC++语言程序
(干货教程)在VSCode并使用chatgtp插件编写CC语言程序 下载并安装VSCODE 第1步,下载VSCODE https://code.visualstudio.com/Download 第2步,安装VSCODE 安装过程较简单,这里省略。 安装好后效果如图:…...
【思维模型】概率思维的价值:找到你的人生算法,实现阶级跃迁!
把同样公平的机会放在放在很多人面前,不同的人生算法,会得到迥然不同的结果。 概率思维是什么? 【ChatGPT】概率思维是一种通过使用数学模型来思考和评估不确定性事件的方法。它通过计算不同可能性的概率来预测事件的结果,并评估风险和机会。 概率思维的价值在于它可以帮…...
SpringBoot + kotlin/java + Mybatis-Plus +Sqlite + Gradle多模块项目
前言 我自己的业务项目,先用kotlinspringboot 搭建, 发现gradle支持kts脚本,于是我就搭建试试。我就选用了最流行的Sqlite内嵌数据库,虽然H2也不错,但是Sqlite才是最流行的。orm框架我还是选择了Mybatis-Plus ,为此中…...
Docker 容器与容器云读书笔记(一)
最近都没时间看书,闲暇之余看看书,写写笔记,记录一下这难得的时光。 docker容器的出现 2013年初, 一个名字从云计算领域横空出世,并在整个IT行业激起千层浪,这就是Docker。Docker选择容器作为核心和基础&…...
软件设计(九)
软件设计(八)https://blog.csdn.net/ke1ying/article/details/128954569?spm1001.2014.3001.5501 81、模块A将学生信息,即学生姓名、学号、手机等放到一个结构体系中,传递给模块B,模块A和B之间的耦合类型为 什么耦合…...
FoveaBox原理与代码解析
paper:FoveaBox: Beyond Anchor-based Object Detectorcode:https://github.com/taokong/FoveaBox背景基于anchor的检测模型需要仔细设计anchor,常用方法之一是根据特定数据集的统计结果确定anchor的number、scale、ratio等,但这种…...
Linux内核启动(1,0.11版本)启动BIOS与加载内核
从电源到启动BIOS 从我们按下启动电源到BIOS,按下电源–>主板会向电源组发出信号–> 接受到信号后,当主板收到电源正常启动信号后,主板会启动CPU(CPU重置所有寄存器数据,并且初始化数据),比如32位系统ÿ…...
python制作贪吃蛇小游戏,畅玩无限制
前言 大家早好、午好、晚好吖 ❤ ~ 现在这年头,无论玩个什么游戏都有健康机制, 这让我们愉悦玩游戏得步伐变得承重起来, 于是无聊之下我写了个贪吃蛇小游戏,来玩个快乐 代码展示 导入模块 import random import sys import …...
MySQL-InnoDB数据页结构浅析
在MySQL-InnoDB行格式浅析中,们简单提了一下 页 的概念,它是 InnoDB 管理存储空间的基本单位,一个页的大小一般是 16KB 。 InnoDB 为了不同的目的而设计了许多种不同类型的 页: 存放表空间头部信息的页存放 Insert Buffer信息的…...
Java、JSP职工人事管理系统设计与实现
技术:Java、JSP等摘要:现在随着我们这个社会的计算机技术的快速发展,计算机在企业管理中得到普遍的应用,现在我们利用计算机在实现企业职工的管理越来越重要。当今社会是快速发展的信息社会,自动化信息的作用也变得越来…...
数据结构与算法这么难,为什么我们还要学习?
文章目录前言1. 数据结构与算法是什么?2. 为什么数据结构与算法很难?3. 如何系统学习数据结构与算法?🍑 复杂度🍑 线性表🍑 树形结构🍑 图🍑 排序🍑 字符串🍑…...
剑指 Offer 52. 两个链表的第一个公共节点
摘要 剑指 Offer 52. 两个链表的第一个公共节点 一、双指针解法 使用双指针的方法,可以将空间复杂度降至 O(1)。只有当链表 headA headB都不为空时,两个链表才可能相交。因此首先判断链表 headA和 headB是否为空,如果其中至少有一个链表为…...
可以写进简历的软件测试电商项目,不进来get一下?
前言 说实话,在找项目的过程中,我下载过(甚至付费下载过)N多个项目、联系过很多项目的作者,但是绝大部分项目,在我看来,并不适合你拿来练习,它们或多或少都存在着“问题”ÿ…...
蓝桥杯-算法-印章问题
这个题真的顶啊!思路:n种图案,m张印章,每一个图案的概率是1/n,这个概率以后用P表示首先我们定义dp[i][j]是买了i张印章(对应于上面的m),凑齐j种图案的概率(对应于上面的n…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
