当前位置: 首页 > 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…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

【Ftrace 专栏】Ftrace 参考博文

ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...