为什么前两个 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 错误?
这里我重构了解决方案 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 可能是可变的)
队列保存同一函数被调用的次数。通常递归函数都会有这个队列问题。如果你只是一遍又一遍地实现相同的功能,那么队列就会变得更大。但是当您执行另一个过程时,队列就会重置。如果队列达到最大限制,那么将会发生您提到的错误。为了防止这个问题,您应该通过在递归函数中执行另一个处理来重置队列。
这些只是调用 print() 函数,除了到达最后一个索引之外什么都不做。这意味着在这些解决方案中调用相同的 print() 函数会使队列变得更大并达到最大限制。然后就出现错误了。
这看起来和其他人几乎一样,但确实有很大的不同。 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() 函数。