【华为OD题库-068】找出经过特定点的路径长度-java
题目
输入一个字符串,都是以大写字母组成,每个相邻的距离是1,第二行输入一个字符串,表示必过的点。
说明
每个点可过多次。求解经过这些必过点的最小距离是多少?
示例1
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
ANTSEDXQOKPUVGIFWHJLYMCRZB
ABC
输出
28
思路
本题不好理解,以示例数据为例,要经过ABC,必须走的路径是A->B->C,其中A->B的距离为25,b->c的距离为3,所以最后结果为28
题目描述太过简略,本文按照以下细节实现:
- 第一行和第二行均有可能含重复字符串
- 出发点并非起点
- 运动方向可随意变更,不能重复走原点。比如第二行输入ABBG,已经在第一个B了,需要找下一个B,而非自己
穷举所有可能性的组合,然后计算最短距离即可
题解
package hwod;import java.util.*;public class CrossSpecDotPath {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str1 = sc.nextLine();String targetStr = sc.nextLine();System.out.println(crossSpecDotPath(str1, targetStr));}private static Map<Character, List<Integer>> map = new HashMap<>(); //存放每个字符所有的索引位置private static int res = Integer.MAX_VALUE;private static int crossSpecDotPath(String originStr, String targetStr) {for (int i = 0; i < originStr.length(); i++) {List<Integer> oldList = map.getOrDefault(originStr.charAt(i), new ArrayList<>());oldList.add(i);map.put(originStr.charAt(i), oldList);}LinkedList<Integer> path = new LinkedList<>();//存放选择的路径dfs(path, targetStr, 0);return res;}private static void dfs(LinkedList<Integer> path, String targetStr, int distance) {if (targetStr.length() < 1) {//路径走完了if (distance < res) {res = distance;}return;}List<Integer> list = map.get(targetStr.charAt(0));//本次寻找的目标字符,可能出现在哪些位置for (int item : list) {if (!path.isEmpty() && path.peekLast() == item) continue;//不允许走原点if (!path.isEmpty()) distance += Math.abs(item - path.peekLast());//累加距离path.addLast(item);dfs(path, targetStr.substring(1), distance);//找下一个目标int lst = path.peekLast();path.removeLast();if (!path.isEmpty()) distance -= Math.abs(lst - path.peekLast());}}}
推荐
如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。
相关文章:
【华为OD题库-068】找出经过特定点的路径长度-java
题目 输入一个字符串,都是以大写字母组成,每个相邻的距离是1,第二行输入一个字符串,表示必过的点。 说明 每个点可过多次。求解经过这些必过点的最小距离是多少? 示例1 输入输出示例仅供调试,后台判题数据一般不包含示…...
高性能队列框架-Disruptor使用、Netty结合Disruptor大幅提高数据处理性能
高性能队列框架-Disruptor 首先介绍一下 Disruptor 框架,Disruptor是一个通用解决方案,用于解决并发编程中的难题(低延迟与高吞吐量),Disruptor 在高并发场景下性能表现很好,如果有这方面需要,…...
Linux学习笔记3 xshell(lnmp)
xshell能连接虚拟机的前提是真机能够ping通虚拟机网址 装OpenSSL依赖文件 [rootlocalhost nginx-1.12.2]# yum -y install openssl pcre-devel 依赖检测[rootlocalhost nginx-1.12.2]# ./configure [rootlocalhost nginx-1.12.2]# yum -y install zlib [rootlocalhost n…...
分享几个可以免费使用GPT工具
1. 国产可以使用GPT3.5和4.0的网站,每日有免费的使用额度,响应速度,注册时不用使用手机号,等个人信息,注重用户隐私,好评! 一个好用的ChatGPT系统 ,可以免费使用3.5 和 4.0https://…...
一篇文章带你快速入门 Nuxt.js 服务端渲染
1. Nuxt.js 概述 1.1 我们一起做过的SPA SPA(single page web application)单页 Web 应用,Web 不再是一张张页面,而是一个整体的应用,一个由路由系统、数据系统、页面(组件)系统等等࿰…...
导入JDBC元数据到Apache Atlas
前言 前期实现了导入MySQL元数据到Apache Atlas, 由于是初步版本,且功能参照Atlas Hive Hook,实现的不够完美 本期对功能进行改进,实现了导入多种关系型数据库元数据到Apache Atlas 数据库schema与catalog 按照SQL标准的解释,…...
大数据项目——基于Django/协同过滤算法的房源可视化分析推荐系统的设计与实现
大数据项目——基于Django/协同过滤算法的房源可视化分析推荐系统的设计与实现 技术栈:大数据爬虫/机器学习学习算法/数据分析与挖掘/大数据可视化/Django框架/Mysql数据库 本项目基于 Django框架开发的房屋可视化分析推荐系统。这个系统结合了大数据爬虫、机器学…...
[网鼎杯 2020 朱雀组]phpweb1
提示 call_user_func()函数先通过php内置函数来进行代码审计绕过system(##不止一种方法) 拿到题目养成一个好的习惯先抓个包 从抓到的包以及它首页的报错来看,这里死活会post传输两个参数func以及p func传输函数,而p则是传输参数的…...
深度学习之注意力机制
注意力机制与外部记忆 注意力机制与记忆增强网络是相辅相成的,神经网络去从内存中或者外部记忆中选出与当前输入相关的内容时需要注意力机制,而在注意力机制的很多应用场景中,我们的外部信息也可以看作是一个外部的记忆 这是一个阅读理解任务…...
WordPress:解决xmlrpc.php被扫描爆破的风险
使用WordPress的朋友都知道,一些【垃圾渣渣】会利用xmlrpc.php文件来进行攻击,绕过WP后台错误登录次数限制进行爆破。虽然密码复杂的极难爆破,但及其占用服务器资源。 方法一、利用宝塔防火墙(收费版) 一般可以直接使…...
Fiddler抓包模拟器(雷电模拟器)
Fiddler设置 List item 打开fiddler,的options 点击OK,重启fiddler 模拟器 更改网络设置 IP可以在电脑上终端上查看 然后在模拟器浏览器中输入IP:端口 安装证书...
RepidJson将内容写入文件
使用 RapidJSON 将内容写入文件的步骤如下: 创建一个 rapidjson::Document 对象,将需要写入文件的内容存储到其中。创建一个 rapidjson::StringBuffer 对象来保存 JSON 字符串。将 rapidjson::Document 对象转换为 JSON 字符串,并将其放入 r…...
Endnote使用教程
原由 最近要进行开题报告,要求不低于60文献的阅读与引用,单独插入引入我觉得是非常繁琐的事情,所以就借助Endnote这个工具,减少我们的工作量。 使用方法 第一步:先新建一个数据库,这样子可以在这个数据库…...
java中用Thead创建线程和用Runnable创建线程的区别是什么?
在 Java 中,创建线程的两种主要方式是通过继承 Thread 类和通过实现 Runnable 接口。下面是它们之间的主要区别: 1. 继承 Thread 类: class MyThread extends Thread {public void run() {// 线程执行的代码} }// 创建并启动线程 MyThread …...
0013Java程序设计-基于Vue的上课签到系统的设计与实现
文章目录 **摘 要**目录系统设计4.2学生签到4.3 签到信息列表4.4 用户信息管理5.1系统登录5.1.1 登录5.1.2 清除用户登记记录5.1.3 登录拦截 5.2用户管理5.2.2 用户添加5.2.3 用户编辑5.2.4 用户删除5.2.5 用户分页 5.3签到信息5.3.1签到信息列表 5.4学生签到5.4.1学生签到 开发…...
2.修改列名与列的数据类型
修改字段名与字段数据类型 1.修改字段名 有时,在我们建好一张表后会突然发现,哎呀!字段名貌似写错了!怎么办?要删了表再重新建一个新表吗?还是要删了这个字段再新建一个新的字段? 都不用&…...
[Firefly-Linux] RK3568 Ubuntu固件分区详解
RK为了方便开发与产品定制,自己定义了一套固件的分区,这些分区信息存放在parameter.txt文件中,Firefly参考这个文件定义了自己的Ubuntu分区,文件为parameter-ubuntu.txt,存放于Linux_SDK的device/rockchip/rk356x目录下…...
SpringBoot项目访问resources下的静态资源
1.新建一个配置文件夹,放配置类 2.编辑 WebMvcConfig.java package com.southwind.configuration;import org.springframework.context.annotation.Configuration; import org.springframework.web.servlet.config.annotation.ResourceHandlerRegistry; import or…...
Qt之面试经验
1.恒生芸擎网络 技术没怎么问,一面问对方工作日常会涉及的一些东西(自动发布),二面公司流程,三面其他(没发offer) 2.光珀智能科技 涉及AI算法落地,问了点基础问题,比如…...
数据库基础概念与范式反范式总结
文章目录 一、基本概念1、属性2、元组3、关系4、超键5、候选键6、主键7、主属性8、外键9、函数依赖完全依赖 二、数据库范式1、第一范式(1NF)2、第二范式(2NF)3、第三范式(3NF)4、巴斯-科德范式(…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
