门户网站建设工作领导小组,网络编程技术实验报告,wordpress文件核对,信息服务平台有哪些网站n 个小区排成一列#xff0c;编号为从 0 到 n-1 。一开始#xff0c;美团外卖员在第0号小区#xff0c;目标为位于第 n-1 个小区的配送站。 给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] #xff0c;在每个小区 i 里你有两种选择#xff1a; 1) 选择a#xff1a;向前 a[…n 个小区排成一列编号为从 0 到 n-1 。一开始美团外卖员在第0号小区目标为位于第 n-1 个小区的配送站。 给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] 在每个小区 i 里你有两种选择 1) 选择a向前 a[i] 个小区。 2) 选择b向前 b[i] 个小区。 把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中字典序最小的字符串。如果做出某个选择时你跳出了这n个小区的范围则这个选择不合法。 • 当没有合法的选择序列时输出 “No solution!”。 • 当字典序最小的字符串无限长时输出 “Infinity!”。 • 否则输出这个选择字符串。 字典序定义如下串s和串t如果串 s 字典序比串 t 小则 • 存在整数 i ≥ -1使得∀j0 ≤ j ≤ i满足s[j] t[j] 且 s[i1] t[i1]。 • 其中空字符 ‘a’ ‘b’。 简述现有一个整数n及两个长度为n的数组num1和num2每个数组中的元素i表示能够在当前位置移动的距离(正/负)每次在位置i移动时可以选择num1[i]或num2[i]要求通过选择num1和num2来移动最终到达n-1的位置其中使用a和b分别表示选择的数组最终得到一个字符串s返回最小字典序的s其他情况若最小字典序无限长则返回Infinity!若不能到达n-1位置则返回No solution!
思路
首先理解题意现在需要返回三种值sInfinity!和No solution!
① s和No solution!当能到达n-1位置并返回最小字典序s不能到达返回No solution!解决能过90%样例
② Infinity!需要能够到达n-1的位置同时s为最小字典序且路径中有环(本题难点刚开始没理解为什么有环还能到终点不应该在环里循环出不去吗画了个图才理解) 简单讲就是由于每个位置有两个选择所以即使其中一个选择遇到环最终也能在该位置通过选择另一个选择来跳出环如果两个选择都是环那就是不可达No solution!。
1、选择DFS算法求解
2、设定一个全局数组来记录当前位置选择过几遍来解决是否存在环的问题
3、对于最小字典序在DFS里将选择a的数组放在选择b的数组上面就可以保证最终得到的是最小字典序可以这样理解由于有两个数组所以可以看做成一个二叉树遍历把a放在上面表示先序遍历而先序遍历先遍历根a然后左子树a最后右子树b可能理解有误欢迎交流讨论
代码
import java.util.*;public class Main {private static StringBuilder ans new StringBuilder(); // 记录字典序最小字符串private static int[] a; // 数组aprivate static int[] b; // 数组bprivate static int[] visit; // 记录是否经过当前位置private static boolean loop false; // 判断是否有环public static void main(String[] args){Scanner in new Scanner(System.in);int len in.nextInt();a new int[len];b new int[len];visit new int[len];for(int i 0; i len; i){a[i] in.nextInt();}for(int i 0; i len; i){b[i] in.nextInt();}if(dfs(0, len-1)){if(loop){ // 能到达存在环System.out.println(Infinity!);}else{ // 能到达不存在环System.out.println(ans);}}else{ // 不能到达System.out.println(No solution!);}}// 输入当前位置及最终位置返回是否到达终点public static boolean dfs(int cur, int target){// 边界判断if(cur 0 || cur target){return false;}// 条件判断if(cur target){return true;}// 是否存在环if(visit[cur] 0){visit[cur];return false;}visit[cur]; // 记录当前位置访问次数/*选择a的过程先添加字符然后判断当前位置能否到达终点如果能到达返回true能到达的同时如果当前位置访问次数大于1说明该位置存在环。如果不能到达则删除a去判断b*/ans.append(a);if(dfs(cura[cur], target)){if(visit[cur] 1){loop true;}return true;}ans.deleteCharAt(ans.length()-1);ans.append(b);if(dfs(curb[cur], target)){if(visit[cur] 1){loop true;}return true;}ans.deleteCharAt(ans.length()-1);// a和b都不能到达返回falsereturn false;}}
