0

例如。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。

4

2 回答 2

1

这很简单。你既有递归又有循环。因此，对 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。

您看到的 start 和 end 回到 10 和 13 的行为仅仅是这第二组递归调用终止并返回到封闭循环的结果。

于 2017-01-21T05:57:31.927 回答
1

基本上它所做的是转到某个数字，并将数字 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}
于 2017-01-21T07:40:02.317 回答