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

华为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机考算法题:最远足迹

目录 题目部分 解读与分析 代码实现 题目部分 题目最远足迹难度易题目说明某探险队负责对地下洞穴进行探险。 探险队成员在进行探险任务时&#xff0c;随身携带的记录器会不定期地记录自身的坐标&#xff0c;但在记录的间隙中也会记录其他数据。探索工作结束后&#xff0c;…...

QScrollBar滚动条、QSlider滑块、 QDial表盘

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

Prometheus+Grafana可视化监控【MySQL状态】

文章目录 一、安装Docker二、安装MySQL数据库(Docker容器方式)三、安装Prometheus四、安装Grafana五、Pronetheus和Grafana相关联六、安装mysqld_exporter七、Grafana添加MySQL监控模板 一、安装Docker 注意&#xff1a;我这里使用之前写好脚本进行安装Docker&#xff0c;如果…...

五,编译定制rom并刷机实现硬改(二)

系列文章目录 第一章 安卓aosp源码编译环境搭建 第二章 手机硬件参数介绍和校验算法 第三章 修改安卓aosp代码更改硬件参数 第四章 编译定制rom并刷机实现硬改(一) 第五章 编译定制rom并刷机实现硬改(二) 第六章 不root不magisk不xposed lsposed frida原生修改定位 第七章 安卓…...

Modbus协议详解3:数据帧格式 - RTU帧 ASCII帧的区别

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

认识数据分析

文章目录 1. 认识数据分析1.1 数据自身的三大属性1.2 建数仓 数据分析的工程技术1.3 数据分析解决问题的原理1.4 数据分析的具体流程1.5 数据的中心化和智能化1.6 数据分析的四种类型和六个方向 1. 认识数据分析 1.1 数据自身的三大属性 客观&#xff1a;用数字衡量和表现一件…...

Learn Prompt-ChatGPT 精选案例:写作博客

在 ChatGPT 的帮助下&#xff0c;文本内容的产出&#xff0c;尤其是撰写博客文章的过程得到了进一步的简化。你可以让 ChatGPT 激发你的灵感&#xff0c;也可以让它美化你的文章内容。 这里我们希望能通过prompt写出一篇以“ChatGPT对社会各行各业的影响”为主题的博客。 本页…...

《确保安全:PostgreSQL安全配置与最佳实践》

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f405;&#x1f43e;猫头虎建议程序员必备技术栈一览表&#x1f4d6;&#xff1a; &#x1f6e0;️ 全栈技术 Full Stack: &#x1f4da…...

Unity中Shader抓取屏幕并实现扭曲效果

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

深浅拷贝详解

深浅拷贝 经典真题 深拷贝和浅拷贝的区别&#xff1f;如何实现 深拷贝和浅拷贝概念 首先&#xff0c;我们需要明确深拷贝和浅拷贝的概念。 浅拷贝&#xff1a;只是拷贝了基本类型的数据&#xff0c;而引用类型数据&#xff0c;复制后也是会发生引用&#xff0c;我们把这种拷…...

@Scheduled 定时任务

Scheduled(cron"30 * * * * ?") 1.cron表达式格式&#xff1a; {秒数} {分钟} {小时} {日期} {月份} {星期} {年份(可为空)} 2.cron表达式各占位符解释&#xff1a; {秒数}{分钟} > 允许值范围: 0~59 ,不允许为空值&#xff0c;若值不合法&#xff0c;调度器将…...

丙烯酸共聚聚氯乙烯树脂

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

Navicat导入Excel数据顺序变了

项目场景&#xff1a; Navicat导入Excel数据 问题描述 从Excel表格中导入数据到数据库中。但是&#xff0c;在导入的过程中&#xff0c;我们常会发现数据顺序出现了问题&#xff0c;导致数据错位&#xff0c;给数据的处理带来了极大的麻烦。 原因分析&#xff1a; 这个问题的…...

uni-app的生命周期

uni-app的生命周期包括应用生命周期和页面生命周期。 应用生命周期涵盖了整个uni-app应用的启动、运行和销毁过程&#xff0c;主要包括以下几个生命周期函数&#xff1a; onLaunch&#xff1a;应用初始化时触发&#xff0c;只触发一次。onShow&#xff1a;应用启动或从后台进…...

Vulnhub实战-DC9

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

软件设计模式系列之七——原型模式

1 模式的定义 原型模式&#xff08;Prototype Pattern&#xff09;是一种创建型设计模式&#xff0c;其主要目的是通过复制现有对象来创建新对象&#xff0c;而不是使用构造函数。原型模式将对象的创建委托给原型对象&#xff0c;通过克隆&#xff08;复制&#xff09;来生成新…...

PMP考试注意事项有哪些?

1. PMI明确规定&#xff1a;不允许考生使用自带文具&#xff0c;包括自带的笔、削笔刀、橡皮、笔袋、计算器和草稿纸等。 2. 本次考试考场内为每位考生配备2B铅笔、橡皮、计算器(若有需要)和草稿纸。如文具有缺损或考试过程中如需更换铅芯等&#xff0c;请向监考老师举手示意。…...

chartgpt+midjourney

chatGPT程序化生成故事 英文版脚本步骤 步骤一&#xff1a;在chatgpt中输入以下脚本&#xff0c;&#xff0c;标红为可变的文字&#xff0c;输入你想要的&#xff0c;目前是科幻&#xff0c;即科幻故事&#xff0c;你可以改为 fairy-tale&#xff0c;则写的是童话故事&#x…...

【SpringMVC】自定义注解

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

【李沐深度学习笔记】数据操作实现

课程地址 数据操作实现p2 数据操作 首先导入PyTorch包&#xff08;import torch)&#xff0c;虽然叫PyTorch&#xff0c;但实际上要导入torch。 import torch张量 张量表示的是一个数值组成的数组&#xff0c;这个数组可以有很多个维度。 # 生成0-11的顺序序列构成的一维…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...