Для целого числа n, return 1 - n в лексикографическом порядке

Question

Например. 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.

Answer 1

Это очень просто. У вас есть как рекурсия, так и цикл. Таким образом, первый вызов ДФС (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). 

Только вызов ДФС (10,19,13) на самом деле ничего не делает, потому что во всех других случаях, первые два параметра больше чем 3-й.

Вызов ДФС (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, являются просто результатом этого второго набора рекурсивных вызовов, заканчивающихся и возвращающихся в замкнутый цикл.

Answer 2

В основном, это то, что нужно сделать, это перейти к некоторому числу и добавить цифры от 0 до 9, а затем перейти к этим цифрам и добавить от 0 до 9, пропуская числа, большие N (13 в этом случае).

Вот шаг пара прошлифованного

Это может быть проще, чтобы посмотреть, что происходит, посмотрев на «я» по центру слева.

"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}