java - java.lang.OutOfMemoryError:Java堆空间查找长度为n的所有字符串

我想生成所有可能的长度为n的字母a，b和c的字符串。我收到此错误java.lang.OutOfMemoryError：Java堆空间。我的堆大小是512m。你能建议我替代吗..

最佳答案

不包含子字符串“ ABC”的字符串计数可以通过动态编程解决。

首先，让所有长度为n的字符串的名称命名为S(n)。请注意，S(n)易于计算。 S(n) = pow(size_of_the_alphabet,n)

让我们将所有包含长度为n的“ ABC”的字符串的编号命名为A(n)，并且将在第k位首次出现“ ABC”的所有字符串的编号命名为A(n,k)

现在注意：
A(n,k) = (S(k-1) - A(k-1)) * S(n - k - 3)（因为k是出现“ ABC”的第一个位置，所以每个字符串在此位置前都有一个不含“ ABC”的子字​​符串，而在第一个“ ABC”之后有一个子字符串）。

请注意，A(n) = sum A(n,k) for k in [0..n-3]

因此，现在我们可以计算A(n)，计算从0开始的每个A(n)值。

基本情况很简单，如A(n) = 0 for n = 0,1,2

A(3) = (S(0) - A(0))*S(0) = 1（即“ ABC”）

等等..

一旦有了A(n)，就可以使用公式S(n) - A(n)获得所需的号码。

伪java伪代码：

public class Counter {


    public int count(int aSize, int n) {
        long[] a = new long[n+1]; // n + 1 elements since a[i] contains # of strings containing "ABC"
        a[0] = 0;
        a[1] = 0;
        a[2] = 0;


        for (int i = 3; i <= n; ++i){
            long sum = 0;
            for (int k = 0; k <= i-3; ++k) {
                sum += (pow(aSize, k) - a[k]) * pow(aSize, i - k - 3);
            }
            a[i] = sum;
        }
        return a[n];

    }

    public static void main(String... args) {
        int aSize = 3; //size of the alphabet
        int n = 30; // length of the strings

        //final result
        long result = pow(aSize, n) - count(aSize, n);


    }
}

假设pow为O（1），运行时间为O(n^2)。如果不是，则可以节省一些时间来预先计算S（i）。

空间要求为O(n)。

请注意，这将计算长度为== n的所有字符串的数量。如果您希望长度

关于java - java.lang.OutOfMemoryError:Java堆空间查找长度为n的所有字符串，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8579575/