java - 递归字符串连接

Question

我正在研究一个需要递归连接字符串的问题，但遇到了问题。

问题指出 s(0) = 0, s(1) = 1, s(n) = s(n-1)s(n-2) for n >= 2 ，其中s(n)是前两个字符串的连接字符串。

输入将指示 (n, k) 有多少个实例对将作为第一个整数输入，后面是包含非负整数的每一行 n (0 <= n <= 60)和一个正整数 k .

输出应该打印出连接字符串的第 k 个字符 s(n) ，其中k小于或等于字符串 s(n) 中的字符数.

s(0) = 0
s(1) = 1
s(2) = 10
s(3) = 101
s(4) = 10110
s(5) = 10110101
and so on.

示例输入:

3
5 2
0 1
4 3

输出:

0
0
1

我的代码:

import java.util.*;

public class recursivestring {

    public static String recursive(int n, int i, String str1, String str2){

        if (i == n - 1) 
            return str1 + str2; 

        return recursive(n, i + 1 , str1 + str2, str1);

    }
    public static void main(String[] args) {

        int lines, i, n, k;
        String result;
        Scanner input = new Scanner(System.in);

        lines = input.nextInt();

        for (i = 0; i < lines; i++) {
            n = input.nextInt();
            k = input.nextInt();
            if (n == 0) {
                result = "0";
            } else if (n == 1) {
                result = "1";
            } else if (n == 2) {
                result = "10";
            } else  {
                result = recursive(n, 2, "10", "1");
            }
            System.out.println(result.charAt(k-1));
        }
    }
}

这是我到目前为止所拥有的，它适用于给定的示例测试用例。它适用于大多数情况，但一旦 n 变大，我就会收到此错误

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

为什么会发生这种情况？我的代码有问题吗？

谢谢!

Answer 1

您的方法的问题在于它创建了太多的废弃字符串。每次写的时候

return str1 + str2;

创建了一个新的String对象。此类一次性对象的数量随 n 线性增长，而它们的总长度则以 O(n²) 增长。

解决这个问题有两种方法:

• 保持程序的线性，并在顶层传递StringBuilder。每个递归调用都会调用 append，而不是使用运算符 + 进行连接。
• 使用Memoization - 由于您需要计算的字符串数量很少，因此存储到目前为止计算的字符串并重新使用它们应该可以解决问题。

与您的问题限制相比，一个更大的问题是它的输出无法容纳在 String 中:Java 允许长度最大为 2³¹ 的字符串，而您的输出60 的代码相当长 - 即 1,548,008,755,920 个字符。虽然您应该能够将此输出保存在文件中，但无法将其存储为 String，无论是否具有内存功能。