华为OD机考算法题:最远足迹
目录
题目部分
解读与分析
代码实现
题目部分
题目 | 最远足迹 |
难度 | 易 |
题目说明 | 某探险队负责对地下洞穴进行探险。 探险队成员在进行探险任务时,随身携带的记录器会不定期地记录自身的坐标,但在记录的间隙中也会记录其他数据。探索工作结束后,探险队需要获取到某成员在探险过程中相对于探险队总部的最远的足迹位置。 1. 仪器记录坐标时,坐标的数据格式为(x,y),如(1,2)、(100,200),其中0<x<1000,0<y<1000。同时存在非法坐标,如(01,1)、(1,01),(0,100)属于非法坐标。如果 x = 0, y = 0 或者 x、y 值存在前导 0 (首位为 0),则认为坐标不合法。(笔者注) 2. 设定探险队总部的坐标为(0,0),某位置相对总部的距离为:x * x+ y * y。 3. 若两个座标的相对总部的距离相同,则第一次到达的坐标为最远的足迹。 4. 若记录仪中的坐标都不合法,输出总部坐标(0,0)。 备注:不需要考虑双层括号嵌套的情况,比如sfsdfsd((1,2))。 |
输入描述 | 字符串,表示记录仪中的数据。 如:ferga13fdsf3(100,200)f2r3rfasf(300,400) |
输出描述 | 字符串,表示最远足迹到达的坐标。 如: (300,400) |
补充说明 | 无 |
------------------------------------------------------ | |
示例 | |
示例1 | |
输入 | ferg(3,10)a13fdsf3(3,4)f2r3rfasf(5,10) |
输出 | (5,10) |
说明 | 记录仪中的合法坐标有3个: (3,10), (3,4), (5,10),其中(5,10)是相距总部最远的坐标, 输出(5,10)。 |
示例2 | |
输入 | asfefaweawfaw(0,1)fe |
输出 | (0,0) |
说明 | 记录仪中的坐标都不合法,输出总部坐标(0,0) |
解读与分析
题目解读:
此题要求从输入字符串中过滤出所有合法的坐标,计算出最远坐标,并输出它。合法坐标的意思是:
1. 首字母是'(',尾字母是')',中间是两个数字,用',' 隔开。
2. 两个数字的首位都不能为 0(数字不能等于0,而且大于0的数字不能有前导 0)。
如果不存在合法坐标,则输出 (0,0)。
本题题干关于坐标合法,没有明确的说,只能通过题目的样例总结。
一个好的题目,应该使用概括的语言描述合法(或不合法)的情况,然后举例说明。否则,举例如果不能覆盖所有的场景,将会产生歧义。
分析与思路:
先设置两个变量:
1. maxPosition ,字符串类型,用以记录最远的坐标,初始值为 "(0,0)"。
2. maxDistance,整形数字,记录最远的距离,初始值为0。
遍历字符串,在遍历字符串的过程中,找到一个合法坐标后,计算其到总部的距离,设为 tmpDistance,如果 tmpDistance 大于 maxDistance,则把它赋值给 maxDistance,并把把它坐标赋值给 maxPosition。继续遍历字符串,寻找下一个合法坐标,循环判断到总部距离,直到字符串结束。
在计算到总部的距离时,假设坐标为 (x,y) , 则距离为 sqrt( x * x + y * y )。由于此题只关心坐标的相对距离,不需要绝对值,所以可以使用 x * x + y * y 代替其平方根值进行比较,以减少计算量。
代表合法坐标的字符串,在去除首位的小括号后必须满足如下条件:
1. 中间某个位置(既不是首字母,也不是尾字母)包含字符','。
2. 通过分隔符 ',' 分开为 2 个字符串,这两个字符串首字母不为 0,且都能解析成正整数。
此算法只需要遍历一次字符串,时间复杂度为 O(n),使用了 2 个额外的原始数据类型变量,空间复杂度为 O(1)。
代码实现
Java代码
import java.util.Scanner;/*** 最远足迹* * @since 2023.09.07* @version 0.1* @author Frank**/
public class MaxDistance {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String record = sc.nextLine();int i = 0;int maxDistance = 0;String maxPosition = "(0,0)";while (i < record.length()) {int leftPT = record.indexOf('(', i);int rightPT = record.indexOf(')', i);if (leftPT < 0) {break;}String position = record.substring(leftPT + 1, rightPT);int tmpDistance = getDistance(position);if (tmpDistance > maxDistance) {maxDistance = tmpDistance;maxPosition = "(" + position + ")";}i = rightPT + 1;}System.out.println(maxPosition);}private static int getDistance(String position) {int ret = 0;String[] posArr = position.split(",");if (posArr == null || posArr.length != 2) {return 0;}for (int i = 0; i < posArr.length; i++) {String strPos = posArr[i];if (strPos.length() == 0 || strPos.startsWith("0")) {return 0;}try {int intPos = Integer.parseInt(strPos);ret += (intPos * intPos);} catch (NumberFormatException e) {return 0;}}return ret;}}
JavaScript代码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;function getDistance( position ) {var ret = 0;var posArr = position.split(",");if (posArr == null || posArr.length != 2) {return 0;}for (var i = 0; i < posArr.length; i++) {var strPos = posArr[i];if (strPos.length == 0 || strPos.startsWith("0")) {return 0;}var intPos = Number(strPos);if( Number.isNaN( intPos) ){return 0;}ret += (intPos * intPos);}return ret;
}function processInput( line )
{var record = line;var i = 0;var maxDistance = 0;var maxPosition = "(0,0)";if( !record ){console.log(maxPosition);return;}while (i < record.length) {var leftPT = record.indexOf('(', i);var rightPT = record.indexOf(')', i);if (leftPT < 0) {break;}var position = record.substring(leftPT + 1, rightPT);var tmpDistance = getDistance(position);if (tmpDistance > maxDistance) {maxDistance = tmpDistance;maxPosition = "(" + position + ")";}i = rightPT + 1;}console.log(maxPosition);
}void async function() {let input = [];while (line = await readline()) {processInput( line );}}();
(完)
相关文章:
华为OD机考算法题:最远足迹
目录 题目部分 解读与分析 代码实现 题目部分 题目最远足迹难度易题目说明某探险队负责对地下洞穴进行探险。 探险队成员在进行探险任务时,随身携带的记录器会不定期地记录自身的坐标,但在记录的间隙中也会记录其他数据。探索工作结束后,…...

QScrollBar滚动条、QSlider滑块、 QDial表盘
QAbstractSlider 类、 QSCrollBar 类、 QSlider 类 一、 基本原理 1、 QAbstractSlider 继承自 QWidget,该类主要用于提供一个范围内的整数值, 2、 QAbstractSlider 类是 QScrollBar 类(滚动条)、 QSlider 类(滑块)、 QDial 类(表盘)的父类,因…...

Prometheus+Grafana可视化监控【MySQL状态】
文章目录 一、安装Docker二、安装MySQL数据库(Docker容器方式)三、安装Prometheus四、安装Grafana五、Pronetheus和Grafana相关联六、安装mysqld_exporter七、Grafana添加MySQL监控模板 一、安装Docker 注意:我这里使用之前写好脚本进行安装Docker,如果…...
五,编译定制rom并刷机实现硬改(二)
系列文章目录 第一章 安卓aosp源码编译环境搭建 第二章 手机硬件参数介绍和校验算法 第三章 修改安卓aosp代码更改硬件参数 第四章 编译定制rom并刷机实现硬改(一) 第五章 编译定制rom并刷机实现硬改(二) 第六章 不root不magisk不xposed lsposed frida原生修改定位 第七章 安卓…...

Modbus协议详解3:数据帧格式 - RTU帧 ASCII帧的区别
Modbus既然是一种通信协议,那它就应该有规定的通信格式用于在设备之间的指令接收与识别。 本文就着重讲讲Modbus协议的RTU帧和ASCII帧。 Modbus帧在串行链路上的格式如下: 在上图的格式中: 1)地址域:指代的是子节点地址…...

认识数据分析
文章目录 1. 认识数据分析1.1 数据自身的三大属性1.2 建数仓 数据分析的工程技术1.3 数据分析解决问题的原理1.4 数据分析的具体流程1.5 数据的中心化和智能化1.6 数据分析的四种类型和六个方向 1. 认识数据分析 1.1 数据自身的三大属性 客观:用数字衡量和表现一件…...
Learn Prompt-ChatGPT 精选案例:写作博客
在 ChatGPT 的帮助下,文本内容的产出,尤其是撰写博客文章的过程得到了进一步的简化。你可以让 ChatGPT 激发你的灵感,也可以让它美化你的文章内容。 这里我们希望能通过prompt写出一篇以“ChatGPT对社会各行各业的影响”为主题的博客。 本页…...

《确保安全:PostgreSQL安全配置与最佳实践》
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🐅🐾猫头虎建议程序员必备技术栈一览表📖: 🛠️ 全栈技术 Full Stack: 📚…...

Unity中Shader抓取屏幕并实现扭曲效果
文章目录 前言一、屏幕抓取,在上一篇文章已经写了二、实现抓取后的屏幕扭曲实现思路:1、屏幕扭曲要借助传入 UV 贴图进行扭曲2、传入贴图后在顶点着色器的输入参数处,传入一个 float2 uv : TEXCOORD,用于之后对扭曲贴图进行采样3、…...

深浅拷贝详解
深浅拷贝 经典真题 深拷贝和浅拷贝的区别?如何实现 深拷贝和浅拷贝概念 首先,我们需要明确深拷贝和浅拷贝的概念。 浅拷贝:只是拷贝了基本类型的数据,而引用类型数据,复制后也是会发生引用,我们把这种拷…...
@Scheduled 定时任务
Scheduled(cron"30 * * * * ?") 1.cron表达式格式: {秒数} {分钟} {小时} {日期} {月份} {星期} {年份(可为空)} 2.cron表达式各占位符解释: {秒数}{分钟} > 允许值范围: 0~59 ,不允许为空值,若值不合法,调度器将…...

丙烯酸共聚聚氯乙烯树脂
声明 本文是学习GB-T 42790-2023 丙烯酸共聚聚氯乙烯树脂. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本文件规定了丙烯酸共聚聚氯乙烯树脂的外观、物化性能等技术要求,描述了相应的采样、试验方 法、检验规则、标志、包装、…...

Navicat导入Excel数据顺序变了
项目场景: Navicat导入Excel数据 问题描述 从Excel表格中导入数据到数据库中。但是,在导入的过程中,我们常会发现数据顺序出现了问题,导致数据错位,给数据的处理带来了极大的麻烦。 原因分析: 这个问题的…...
uni-app的生命周期
uni-app的生命周期包括应用生命周期和页面生命周期。 应用生命周期涵盖了整个uni-app应用的启动、运行和销毁过程,主要包括以下几个生命周期函数: onLaunch:应用初始化时触发,只触发一次。onShow:应用启动或从后台进…...

Vulnhub实战-DC9
前言 本次的实验靶场是Vulnhub上面的DC-9,其中的渗透测试过程比较多,最终的目的是要找到其中的flag。 一、信息收集 对目标网络进行扫描 arp-scan -l 对目标进行端口扫描 nmap -sC -sV -oA dc-9 192.168.1.131 扫描出目标开放了22和80两个端口&a…...

软件设计模式系列之七——原型模式
1 模式的定义 原型模式(Prototype Pattern)是一种创建型设计模式,其主要目的是通过复制现有对象来创建新对象,而不是使用构造函数。原型模式将对象的创建委托给原型对象,通过克隆(复制)来生成新…...

PMP考试注意事项有哪些?
1. PMI明确规定:不允许考生使用自带文具,包括自带的笔、削笔刀、橡皮、笔袋、计算器和草稿纸等。 2. 本次考试考场内为每位考生配备2B铅笔、橡皮、计算器(若有需要)和草稿纸。如文具有缺损或考试过程中如需更换铅芯等,请向监考老师举手示意。…...
chartgpt+midjourney
chatGPT程序化生成故事 英文版脚本步骤 步骤一:在chatgpt中输入以下脚本,,标红为可变的文字,输入你想要的,目前是科幻,即科幻故事,你可以改为 fairy-tale,则写的是童话故事&#x…...

【SpringMVC】自定义注解
【SpringMVC】自定义注解 前言1. 什么是注解?2. 注解的用处3. 注解的原理1.1. Override1.2. SuppressWarnings 2. JDK元注解2.1. Retention2.2. Target2.3. Inherited2.4. Documented 3. 自定义注解3.1. 自定义注解的分类注解类 结语 自定义注解及其应用 前言 在J…...

【李沐深度学习笔记】数据操作实现
课程地址 数据操作实现p2 数据操作 首先导入PyTorch包(import torch),虽然叫PyTorch,但实际上要导入torch。 import torch张量 张量表示的是一个数值组成的数组,这个数组可以有很多个维度。 # 生成0-11的顺序序列构成的一维…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...

宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...