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

【华为OD题库-068】找出经过特定点的路径长度-java

题目

输入一个字符串,都是以大写字母组成,每个相邻的距离是1,第二行输入一个字符串,表示必过的点。
说明
每个点可过多次。求解经过这些必过点的最小距离是多少?
示例1
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
ANTSEDXQOKPUVGIFWHJLYMCRZB
ABC
输出
28

思路

本题不好理解,以示例数据为例,要经过ABC,必须走的路径是A->B->C,其中A->B的距离为25,b->c的距离为3,所以最后结果为28
题目描述太过简略,本文按照以下细节实现:

  1. 第一行和第二行均有可能含重复字符串
  2. 出发点并非起点
  3. 运动方向可随意变更,不能重复走原点。比如第二行输入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

题目 输入一个字符串&#xff0c;都是以大写字母组成&#xff0c;每个相邻的距离是1&#xff0c;第二行输入一个字符串&#xff0c;表示必过的点。 说明 每个点可过多次。求解经过这些必过点的最小距离是多少? 示例1 输入输出示例仅供调试&#xff0c;后台判题数据一般不包含示…...

高性能队列框架-Disruptor使用、Netty结合Disruptor大幅提高数据处理性能

高性能队列框架-Disruptor 首先介绍一下 Disruptor 框架&#xff0c;Disruptor是一个通用解决方案&#xff0c;用于解决并发编程中的难题&#xff08;低延迟与高吞吐量&#xff09;&#xff0c;Disruptor 在高并发场景下性能表现很好&#xff0c;如果有这方面需要&#xff0c;…...

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的网站&#xff0c;每日有免费的使用额度&#xff0c;响应速度&#xff0c;注册时不用使用手机号&#xff0c;等个人信息&#xff0c;注重用户隐私&#xff0c;好评&#xff01; 一个好用的ChatGPT系统 &#xff0c;可以免费使用3.5 和 4.0https://…...

一篇文章带你快速入门 Nuxt.js 服务端渲染

1. Nuxt.js 概述 1.1 我们一起做过的SPA SPA&#xff08;single page web application&#xff09;单页 Web 应用&#xff0c;Web 不再是一张张页面&#xff0c;而是一个整体的应用&#xff0c;一个由路由系统、数据系统、页面&#xff08;组件&#xff09;系统等等&#xff0…...

导入JDBC元数据到Apache Atlas

前言 前期实现了导入MySQL元数据到Apache Atlas, 由于是初步版本&#xff0c;且功能参照Atlas Hive Hook&#xff0c;实现的不够完美 本期对功能进行改进&#xff0c;实现了导入多种关系型数据库元数据到Apache Atlas 数据库schema与catalog 按照SQL标准的解释&#xff0c;…...

大数据项目——基于Django/协同过滤算法的房源可视化分析推荐系统的设计与实现

大数据项目——基于Django/协同过滤算法的房源可视化分析推荐系统的设计与实现 技术栈&#xff1a;大数据爬虫/机器学习学习算法/数据分析与挖掘/大数据可视化/Django框架/Mysql数据库 本项目基于 Django框架开发的房屋可视化分析推荐系统。这个系统结合了大数据爬虫、机器学…...

[网鼎杯 2020 朱雀组]phpweb1

提示 call_user_func()函数先通过php内置函数来进行代码审计绕过system&#xff08;##不止一种方法&#xff09; 拿到题目养成一个好的习惯先抓个包 从抓到的包以及它首页的报错来看&#xff0c;这里死活会post传输两个参数func以及p func传输函数&#xff0c;而p则是传输参数的…...

深度学习之注意力机制

注意力机制与外部记忆 注意力机制与记忆增强网络是相辅相成的&#xff0c;神经网络去从内存中或者外部记忆中选出与当前输入相关的内容时需要注意力机制&#xff0c;而在注意力机制的很多应用场景中&#xff0c;我们的外部信息也可以看作是一个外部的记忆 这是一个阅读理解任务…...

WordPress:解决xmlrpc.php被扫描爆破的风险

使用WordPress的朋友都知道&#xff0c;一些【垃圾渣渣】会利用xmlrpc.php文件来进行攻击&#xff0c;绕过WP后台错误登录次数限制进行爆破。虽然密码复杂的极难爆破&#xff0c;但及其占用服务器资源。 方法一、利用宝塔防火墙&#xff08;收费版&#xff09; 一般可以直接使…...

Fiddler抓包模拟器(雷电模拟器)

Fiddler设置 List item 打开fiddler,的options 点击OK,重启fiddler 模拟器 更改网络设置 IP可以在电脑上终端上查看 然后在模拟器浏览器中输入IP:端口 安装证书...

RepidJson将内容写入文件

使用 RapidJSON 将内容写入文件的步骤如下&#xff1a; 创建一个 rapidjson::Document 对象&#xff0c;将需要写入文件的内容存储到其中。创建一个 rapidjson::StringBuffer 对象来保存 JSON 字符串。将 rapidjson::Document 对象转换为 JSON 字符串&#xff0c;并将其放入 r…...

Endnote使用教程

原由 最近要进行开题报告&#xff0c;要求不低于60文献的阅读与引用&#xff0c;单独插入引入我觉得是非常繁琐的事情&#xff0c;所以就借助Endnote这个工具&#xff0c;减少我们的工作量。 使用方法 第一步&#xff1a;先新建一个数据库&#xff0c;这样子可以在这个数据库…...

java中用Thead创建线程和用Runnable创建线程的区别是什么?

在 Java 中&#xff0c;创建线程的两种主要方式是通过继承 Thread 类和通过实现 Runnable 接口。下面是它们之间的主要区别&#xff1a; 1. 继承 Thread 类&#xff1a; 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.修改字段名 有时&#xff0c;在我们建好一张表后会突然发现&#xff0c;哎呀&#xff01;字段名貌似写错了&#xff01;怎么办&#xff1f;要删了表再重新建一个新表吗&#xff1f;还是要删了这个字段再新建一个新的字段&#xff1f; 都不用&…...

[Firefly-Linux] RK3568 Ubuntu固件分区详解

RK为了方便开发与产品定制&#xff0c;自己定义了一套固件的分区&#xff0c;这些分区信息存放在parameter.txt文件中&#xff0c;Firefly参考这个文件定义了自己的Ubuntu分区&#xff0c;文件为parameter-ubuntu.txt&#xff0c;存放于Linux_SDK的device/rockchip/rk356x目录下…...

SpringBoot项目访问resources下的静态资源

1.新建一个配置文件夹&#xff0c;放配置类 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.恒生芸擎网络 技术没怎么问&#xff0c;一面问对方工作日常会涉及的一些东西&#xff08;自动发布&#xff09;&#xff0c;二面公司流程&#xff0c;三面其他&#xff08;没发offer&#xff09; 2.光珀智能科技 涉及AI算法落地&#xff0c;问了点基础问题&#xff0c;比如…...

数据库基础概念与范式反范式总结

文章目录 一、基本概念1、属性2、元组3、关系4、超键5、候选键6、主键7、主属性8、外键9、函数依赖完全依赖 二、数据库范式1、第一范式&#xff08;1NF&#xff09;2、第二范式&#xff08;2NF&#xff09;3、第三范式&#xff08;3NF&#xff09;4、巴斯-科德范式&#xff08…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...