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

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...