。

一开始#xff0c;美团外卖员在第0号小区#xff0c;目标为位于第

n-1

的字符串。

求到达小区n-1的方案中字典序最小的字符串。

如果做出某个选择时你跳出了这n个小区的范围则这个选择不合法。

“No

简述现有一个整数n及两个长度为n的数组num1和num2每个数组中的元素i表示能够在当前位置移动的距离(正/负)每次在位置i移动时可以选择num1[i]或num2[i]要求通过选择num1和num2来移动最终到达n-1的位置其中使用a和b分别表示选择的数组最终得到一个字符串s返回最小字典序的s其他情况若最小字典序无限长则返回Infinity!若不能到达n-1位置则返回No

solution!

solution!当能到达n-1位置并返回最小字典序s不能到达返回No

Infinity!需要能够到达n-1的位置同时s为最小字典序且路径中有环(本题难点刚开始没理解为什么有环还能到终点不应该在环里循环出不去吗画了个图才理解)

简单讲就是由于每个位置有两个选择所以即使其中一个选择遇到环最终也能在该位置通过选择另一个选择来跳出环如果两个选择都是环那就是不可达No

1、选择DFS算法求解

2、设定一个全局数组来记录当前位置选择过几遍来解决是否存在环的问题

3、对于最小字典序在DFS里将选择a的数组放在选择b的数组上面就可以保证最终得到的是最小字典序可以这样理解由于有两个数组所以可以看做成一个二叉树遍历把a放在上面表示先序遍历而先序遍历先遍历根a然后左子树a最后右子树b可能理解有误欢迎交流讨论

import

能到达存在环System.out.println(Infinity!);}else{

能到达不存在环System.out.println(ans);}}else{

solution!);}}//

记录当前位置访问次数/*选择a的过程先添加字符然后判断当前位置能否到达终点如果能到达返回true能到达的同时如果当前位置访问次数大于1说明该位置存在环。

如果不能到达则删除a去判断b*/ans.append(a);if(dfs(cura[cur],

1){loop

true;}ans.deleteCharAt(ans.length()-1);ans.append(b);if(dfs(curb[cur],

1){loop

true;}ans.deleteCharAt(ans.length()-1);//

false;}}