企业网站怎么做推广,前端框架有哪些,app导航网站建设多少钱,乐享视频在线下载免费目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;A卷B卷#… 目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
输入一个字符串都是以大写字母组成每个相邻的距离是 1第二行输入一个字符串表示必过的点。
说明每个点可过多次。
二、输入描述
输入一个字符串都是以大写字母组成每个相邻的距离是 1第二行输入一个字符串表示必过的点。
说明每个点可过多次。
三、输出描述
经过这些必过点的最小距离是多少。
四、解题思路
利用深度优先搜索来找到所有能够到达的距离并更新最小距离。
目标的点到达最后一个点更新最小距离当搜索到的距离大于之前搜索的距离就不用再搜下去了拿到当前要去的字符与所有字符进行比对如果是相同的就进入下一层递归 选第一个点的时候距离为0选的点不为第一个点时加上到达这个点的距离 输出最小距离。
五、Java算法源码
package com.guor.od;import java.util.*;public class OdTest {public static char[] allPoint;public static char[] movePoint;public static int ans;public static int[][] minPointDistance;public static void main(String[] args) {Scanner sc new Scanner(System.in);String str sc.nextLine();allPoint str.toCharArray();str sc.nextLine();movePoint str.toCharArray();ans Integer.MAX_VALUE;minPointDistance new int[movePoint.length][allPoint.length];for(int i 0; i minPointDistance.length; i) {for(int j 0; j allPoint.length; j) {minPointDistance[i][j] Integer.MAX_VALUE;}}dfs(0, 0, 0);System.out.println(ans);}/*** 利用深度优先搜索来找到所有能够到达的距离并更新最小距离* param index 目标点下标* param nowDistance 当前已经走过的距离* param nowPointIndex 当前出发的点下标*/public static void dfs(int index, int nowDistance, int nowPointIndex){if(index movePoint.length) {// 目标的点到达最后一个点更新最小距离ans Math.min(ans, nowDistance);return ;}// 优化:minPointDistance中存的是到达目标点的最小距离// 例如minPointDistance[3][2]:当前到第3个点位置在2的最小距离// 当搜索到的距离大于之前搜索的距离就不用再搜下去了if(minPointDistance[index][nowPointIndex] nowDistance) {return ;}minPointDistance[index][nowPointIndex] nowDistance;// 拿到当前要去的字符与所有字符进行比对如果是相同的就进入下一层递归char tarPoint movePoint[index];for(int i 0; i allPoint.length; i) {if(allPoint[i] tarPoint) {if(index 0) {// 选第一个点的时候距离为0dfs(index 1, 0, i);}else {// 选的点不为第一个点时加上到达这个点的距离dfs(index 1, nowDistance Math.abs(i - nowPointIndex), i);}}}}
}六、效果展示
1、输入
NEZHALOVESTUDYJAVA SAZL
2、输出
10
3、说明 下一篇华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
