给定一个整数n，return 1 - n 按字典序排列
Given an integer n, return 1 - n in lexicographical order
例如。 For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
下面的解决方案有效，实际上非常好。经过一番努力后我找到了它，但我不明白它实际上是如何工作的。这似乎是纯粹的魔法。当我们进行递归调用时，世界上的start参数在第二次递归
后仍然是10
public static ArrayList<Integer> lexicalOrder(int n) {
ArrayList<Integer> result = new ArrayList<>();
dfs(1, 9, n, result);
return result;
}
private static void dfs(int start, int end, int n, ArrayList<Integer> result){
for (int i = start; i <= end && i <= n; i++){
result.add(i);
//Just printing out the end and start to try to understand
System.out.println("Start : " + start + " End : " + end);
//If i is 10, how does 10 * 10 end up as 10 again for several iterations???
dfs(i * 10, i * 10 + 9, n, result);
}
}
我不相信魔法，有人能解释一下这是怎么回事吗？第一次迭代 start 是 1， end 是预期的 9。然后开始是 10 和 19，正如我在第二次迭代中预期的那样。然后，我希望在我们进行下一次递归调用后开始为 100，结束为 109；但是，它们与之前的递归一样：10 和 19。
很简单。你有递归和循环。因此第一次调用 dfs(1,9,13) 实际上是这样做的：
add 1 to result and call dfs (10,19,13),
add 2 to result and call dfs (20,29,13)
...
add 9 to result and call dfs (90,99,13).
只有对 dfs (10,19,13) 的调用才真正起作用，因为在所有其他情况下，前两个参数都大于第三个。
调用 dfs (10,19,13) 是这样做的：
add 10 to result and call dfs (100, 109, 13)
add 11 to result and call dfs (110, 119, 13)
add 12 to result and call dfs (120, 129, 13)
add 13 to result and call dfs (130, 139, 13)
然后终止，因为 14 大于 13。
您看到的开始和结束回到 10 和 13 的行为只是第二组递归调用终止并返回到封闭循环的结果。
基本上它所做的是转到某个数字，并将数字 0 到 9 附加到它上面，然后转到这些数字，并将 0 到 9 附加到它上面，跳过大于 N 的数字（本例中的 13例）。
这里有几个步骤
查看居中左侧的 "i" 可能更容易看出发生了什么。
"i" return
1 //Add to list {1}
10 //Add to list {1,10}
100 //Bigger than n! (n = 13) {1,10}
11 //Add to list {1,10,11}
110 //Bigger than n! (n = 13) {1,10,11}
12 //Add to list {1,10,11,12}
120 //Bigger than n! (n = 13) {1,10,11,12}
13 //Add to list {1,10,11,12,13}
130 //Bigger than n! (n = 13) {1,10,11,12,13}
14 //Bigger than n! (n = 13) {1,10,11,12,13}
2 //Add to list {1,10,11,12,13,2}
20 //Bigger than n! (n = 13) {1,10,11,12,13,2}
3 //Add to list {1,10,11,12,13,2,3}
30 //Bigger than n! (n = 13) {1,10,11,12,13,2,3}
4 //Add to list {1,10,11,12,13,2,3,4}
40 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4}
5 //Add to list {1,10,11,12,13,2,3,4,5}
50 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5}
6 //Add to list {1,10,11,12,13,2,3,4,5,6}
60 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6}
7 //Add to list {1,10,11,12,13,2,3,4,5,6,7}
70 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6,7}
8 //Add to list {1,10,11,12,13,2,3,4,5,6,7,8}
80 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6,7,8}
9 //Add to list {1,10,11,12,13,2,3,4,5,6,7,8,9}
90 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6,7,8,9}
10 //Bigger than end! (end = 9) {1,10,11,12,13,2,3,4,5,6,7,8,9}
正在发生的事情的更完整版本：
lexicalOrder(13)
result = {}
dfs(1,9,13,result) //1 is the smallest digit, 9 is the largest digit,
//13 is the largest possible value,
//Passed in "result" array to be edited.
i = start
//i = 1
Enter Loop
result.add(1)
//result = {1}
dfs(10,19,13,result)
i = start
//i = 10
Enter Loop
result.add(10)
//result = {1,10}
dfs(100,109,13,result)
i = start
//i = 100
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 11
result.add(11)
//result = {1,10,11}
dfs(110,119,13,result)
i = start
//i = 110
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 12
result.add(12)
//result = {1,10,11,12}
dfs(120,129,13,result)
i = start
//i = 120
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 13
result.add(13)
//result = {1,10,11,12,13}
dfs(130,139,13,result)
i = start
//i = 130
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 14
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 2
result.add(i)
//result = {1,10,11,12,13,2}
dfs(20,29,13,result)
i = start
//i = 20
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 3
result.add(i)
//result = {1,10,11,12,13,2,3}
dfs(30,39,13,result)
i = start
//i = 30
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 4
result.add(i)
//result = {1,10,11,12,13,2,3,4}
dfs(40,49,13,result)
i = start
//i = 40
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 5
result.add(i)
//result = {1,10,11,12,13,2,3,4,5}
dfs(50,59,13,result)
i = start
//i = 50
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 6
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6}
dfs(60,69,13,result)
i = start
//i = 60
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 7
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6,7}
dfs(70,79,13,result)
i = start
//i = 70
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 8
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6,7,8}
dfs(80,89,13,result)
i = start
//i = 80
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 9
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6,7,8,9}
dfs(90,99,13,result)
i = start
//i = 90
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 10
Whoops! "i" is greater than "end"! //end = 9
return result // result = {1,10,11,12,13,2,3,4,5,6,7,8,9}
例如。 For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
下面的解决方案有效，实际上非常好。经过一番努力后我找到了它，但我不明白它实际上是如何工作的。这似乎是纯粹的魔法。当我们进行递归调用时，世界上的start参数在第二次递归
public static ArrayList<Integer> lexicalOrder(int n) {
ArrayList<Integer> result = new ArrayList<>();
dfs(1, 9, n, result);
return result;
}
private static void dfs(int start, int end, int n, ArrayList<Integer> result){
for (int i = start; i <= end && i <= n; i++){
result.add(i);
//Just printing out the end and start to try to understand
System.out.println("Start : " + start + " End : " + end);
//If i is 10, how does 10 * 10 end up as 10 again for several iterations???
dfs(i * 10, i * 10 + 9, n, result);
}
}
我不相信魔法，有人能解释一下这是怎么回事吗？第一次迭代 start 是 1， end 是预期的 9。然后开始是 10 和 19，正如我在第二次迭代中预期的那样。然后，我希望在我们进行下一次递归调用后开始为 100，结束为 109；但是，它们与之前的递归一样：10 和 19。
很简单。你有递归和循环。因此第一次调用 dfs(1,9,13) 实际上是这样做的：
add 1 to result and call dfs (10,19,13),
add 2 to result and call dfs (20,29,13)
...
add 9 to result and call dfs (90,99,13).
只有对 dfs (10,19,13) 的调用才真正起作用，因为在所有其他情况下，前两个参数都大于第三个。
调用 dfs (10,19,13) 是这样做的：
add 10 to result and call dfs (100, 109, 13)
add 11 to result and call dfs (110, 119, 13)
add 12 to result and call dfs (120, 129, 13)
add 13 to result and call dfs (130, 139, 13)
然后终止，因为 14 大于 13。
您看到的开始和结束回到 10 和 13 的行为只是第二组递归调用终止并返回到封闭循环的结果。
基本上它所做的是转到某个数字，并将数字 0 到 9 附加到它上面，然后转到这些数字，并将 0 到 9 附加到它上面，跳过大于 N 的数字（本例中的 13例）。
这里有几个步骤
查看居中左侧的 "i" 可能更容易看出发生了什么。
"i" return
1 //Add to list {1}
10 //Add to list {1,10}
100 //Bigger than n! (n = 13) {1,10}
11 //Add to list {1,10,11}
110 //Bigger than n! (n = 13) {1,10,11}
12 //Add to list {1,10,11,12}
120 //Bigger than n! (n = 13) {1,10,11,12}
13 //Add to list {1,10,11,12,13}
130 //Bigger than n! (n = 13) {1,10,11,12,13}
14 //Bigger than n! (n = 13) {1,10,11,12,13}
2 //Add to list {1,10,11,12,13,2}
20 //Bigger than n! (n = 13) {1,10,11,12,13,2}
3 //Add to list {1,10,11,12,13,2,3}
30 //Bigger than n! (n = 13) {1,10,11,12,13,2,3}
4 //Add to list {1,10,11,12,13,2,3,4}
40 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4}
5 //Add to list {1,10,11,12,13,2,3,4,5}
50 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5}
6 //Add to list {1,10,11,12,13,2,3,4,5,6}
60 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6}
7 //Add to list {1,10,11,12,13,2,3,4,5,6,7}
70 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6,7}
8 //Add to list {1,10,11,12,13,2,3,4,5,6,7,8}
80 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6,7,8}
9 //Add to list {1,10,11,12,13,2,3,4,5,6,7,8,9}
90 //Bigger than n! (n = 13) {1,10,11,12,13,2,3,4,5,6,7,8,9}
10 //Bigger than end! (end = 9) {1,10,11,12,13,2,3,4,5,6,7,8,9}
正在发生的事情的更完整版本：
lexicalOrder(13)
result = {}
dfs(1,9,13,result) //1 is the smallest digit, 9 is the largest digit,
//13 is the largest possible value,
//Passed in "result" array to be edited.
i = start
//i = 1
Enter Loop
result.add(1)
//result = {1}
dfs(10,19,13,result)
i = start
//i = 10
Enter Loop
result.add(10)
//result = {1,10}
dfs(100,109,13,result)
i = start
//i = 100
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 11
result.add(11)
//result = {1,10,11}
dfs(110,119,13,result)
i = start
//i = 110
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 12
result.add(12)
//result = {1,10,11,12}
dfs(120,129,13,result)
i = start
//i = 120
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 13
result.add(13)
//result = {1,10,11,12,13}
dfs(130,139,13,result)
i = start
//i = 130
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 14
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 2
result.add(i)
//result = {1,10,11,12,13,2}
dfs(20,29,13,result)
i = start
//i = 20
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 3
result.add(i)
//result = {1,10,11,12,13,2,3}
dfs(30,39,13,result)
i = start
//i = 30
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 4
result.add(i)
//result = {1,10,11,12,13,2,3,4}
dfs(40,49,13,result)
i = start
//i = 40
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 5
result.add(i)
//result = {1,10,11,12,13,2,3,4,5}
dfs(50,59,13,result)
i = start
//i = 50
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 6
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6}
dfs(60,69,13,result)
i = start
//i = 60
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 7
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6,7}
dfs(70,79,13,result)
i = start
//i = 70
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 8
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6,7,8}
dfs(80,89,13,result)
i = start
//i = 80
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 9
result.add(i)
//result = {1,10,11,12,13,2,3,4,5,6,7,8,9}
dfs(90,99,13,result)
i = start
//i = 90
Enter Loop
Whoops! "i" is greater than "n"! //n = 13
Exit Loop
i++
//i = 10
Whoops! "i" is greater than "end"! //end = 9
return result // result = {1,10,11,12,13,2,3,4,5,6,7,8,9}