做网站背景的图,wordpress侧边栏颜色,中文网站开发工具,东莞网站开发网站建设制作费用题目 输入一个字符串#xff0c;都是以大写字母组成#xff0c;每个相邻的距离是1#xff0c;第二行输入一个字符串#xff0c;表示必过的点。 说明 每个点可过多次。求解经过这些必过点的最小距离是多少? 示例1 输入输出示例仅供调试#xff0c;后台判题数据一般不包含示…题目 输入一个字符串都是以大写字母组成每个相邻的距离是1第二行输入一个字符串表示必过的点。 说明 每个点可过多次。求解经过这些必过点的最小距离是多少? 示例1 输入输出示例仅供调试后台判题数据一般不包含示例 输入 ANTSEDXQOKPUVGIFWHJLYMCRZB ABC 输出 28 思路 本题不好理解以示例数据为例要经过ABC必须走的路径是A-B-C其中A-B的距离为25b-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 MapCharacter, ListInteger 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) {ListInteger oldList map.getOrDefault(originStr.charAt(i), new ArrayList());oldList.add(i);map.put(originStr.charAt(i), oldList);}LinkedListInteger path new LinkedList();//存放选择的路径dfs(path, targetStr, 0);return res;}private static void dfs(LinkedListInteger path, String targetStr, int distance) {if (targetStr.length() 1) {//路径走完了if (distance res) {res distance;}return;}ListInteger 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查看当前专栏更新的所有题目。
