Java 实现打印字符串 n 次

Question

为什么前两个 Java 实现打印字符串“n”次会在“n”较大时导致

stack overflow

错误

(e.g., 10^4)

，而第三个实现不会遇到此问题？

第一个片段 -

import java.util.ArrayList;
import java.util.List;
public class Solution {

    static void print(int count, ArrayList<String> list){
        if(count < 1){
            return;
        }
        list.add("Coding Ninjas" + " ");
        count--;
        print(count, list);
    }
    public static List<String> printNtimes(int n){
        // Write your code here.
        ArrayList<String> list = new ArrayList<String>();
        print(n, list);
        return list;
    }
}

第二个片段 -

import java.util.ArrayList;
import java.util.List;
public class Solution {

    static List<String> print(int count, ArrayList<String> list){
        if(count == 0){
            return list;
        }
        list.add("Coding Ninjas" + " ");
        count--;
        return print(count, list);
    }
    public static List<String> printNtimes(int n){
        // Write your code here.
        ArrayList<String> list = new ArrayList<String>();
        return print(n, list);
    }
}

第三个片段 -

import java.util.ArrayList;
import java.util.List;
public class Solution {

    static List<String> print(List<String> list, String str, int n){
        if(n == 0){
            return list;
        }
        list.add(str);
        return print(list, str, n - 1);
    }
    public static List<String> printNtimes(int n){
        // Write your code here.
        ArrayList<String> list = new ArrayList<>();
        String str = "Coding Ninjas ";
        return print(list, str, n);
    }
}   

我无法弄清楚为什么会发生这种情况，因为所有三个不同的代码都在做同样的事情。我正在尝试以 O(n) 时间复杂度解决这个问题。任何人都可以帮我找出为什么第三个片段没有给出 stackoverflow 错误？

Answer 1

这里我重构了解决方案 3 和 1，以使我的解释更容易理解：

重构解决方案1

public class Solution1 {

    public static void main(String[] args) {
        List<String> list = printNtimes(100000);
    }

    public static List<String> printNtimes(int n) {
        ArrayList<String> list = new ArrayList<String>();
        print(list, n);
        return list;
    }

    static void print(ArrayList<String> list, int n) {
        if (n == 0) {
            return;
        }
        list.add("Coding Ninjas" + " ");
        n--;
        System.out.println(n + "-)List : " + list.size());
        print(list, n);
    }

}

解决方案 1 的输出

99999-)List : 1
99998-)List : 2
...
98337-)List : 1663
    at _2_print_string.Solution1.print(Solution1.java:25)
    at _2_print_string.Solution1.print(Solution1.java:25)
...
    at _2_print_string.Solution1.print(Solution1.java:25)
    at _2_print_string.Solution1.print(Solution1.java:25)
98336-)List : 1664
98335-)List : 1665
    ...
    

重构解决方案3

 public class Solution3 {

    public static void main(String[] args) {
        List<String> list = printNtimes(10000);
    }

    public static List<String> printNtimes(int n) {
        ArrayList<String> list = new ArrayList<>();
        print(list, n);
        return list;
    }

    static List<String> print(List<String> list, int n) {
        if (n == 0) {
            return list;
        }
        list.add("Coding Ninjas" + " ");
        n--;
        print(list, n);
        System.out.println(n + "-)List : " + list.size());
        return list;
    }

}

解决方案 3 的输出

0-)List : 10000
1-)List : 10000
2-)List : 10000
3-)List : 10000
    ...
9998-)List : 10000
9999-)List : 10000

• 说明

我无法给你任何文档，但我可以根据我的经验说，如果你调用相同的函数

repeatedly

而不执行其他过程，则会发生错误以停止程序以防止不定式工作。因为这意味着如果任何函数重复地为一个小进程工作，那么可能已经发生了最有可能的错误。你可以认为这是一种让计算机免于永远无意义工作的方法。这种数据保存在队列中。并且这个队列有一个限制。如果达到限制，则程序会给出错误。

（

repeatedly

：我不知道限制，但它可以是任何数字，例如 10^3 或 10^7 可能是可变的）

• 什么是队列（在这个问题的对话中）？

队列保存同一函数被调用的次数。通常递归函数都会有这个队列问题。如果你只是一遍又一遍地实现相同的功能，那么队列就会变得更大。但是当您执行另一个过程时，队列就会重置。如果队列达到最大限制，那么将会发生您提到的错误。为了防止这个问题，您应该通过在递归函数中执行另一个处理来重置队列。

• 解决方案1和解决方案2的问题

这些只是调用 print() 函数，除了到达最后一个索引之外什么都不做。这意味着在这些解决方案中调用相同的 print() 函数会使队列变得更大并达到最大限制。然后就出现错误了。

• 解决方案3

这看起来和其他人几乎一样，但确实有很大的不同。 print() 函数不仅调用另一个 print() 函数，有时还返回列表。所以队列被重置。让我在下一个例子中解释一下。

• 示例

假设您为解决方案 1 和 2 调用 print() 函数。将调用 10^4 次函数。对于添加相同进度的队列来说，这已经很多了。

假设您为解决方案 3 调用相同的函数。重复调用 print 函数后，它将返回列表。哎呀。当另一个进程完成时，队列被重置。

解决方案 1 和 2 仅在 print() 函数调用 1000 + 999+ 998 时重置队列... 总共调用打印函数重置查询：1000+999+...+2+1=500500

解决方案3在调用print()函数1000次时重置队列。然后当 print() 函数被调用 999 次时将重置队列。

重置队列的调用打印函数总数：1000，

重置队列的打印函数调用总数：999，

...

• 很快

当解决方案 3 调用 print() 函数时，有时它会返回一个列表。所以功能限制查询重置。但对于其他解决方案，它们仅调用 print() 函数。所以他们达到了队列的限制。

• 额外

顺便说一句，如果将

n

限制从 10^4 增加到 10^5 或更多，则可能会出现错误。因为在某些值中，它会在重置查询之前调用很多 print() 函数。