java - 将命令式代码转换为非连续一个实现的声明式代码

Question

我想知道如何将我的非连续 ones 问题转换为声明逻辑。

我已经实现并测试了一个函数的命令式实现，该函数输入单个 int 参数并返回没有连续 1 的所有二进制字符串的字符串 ArrayList。我已经对其进行了测试，但是该函数的 TC 使其在 15 之后变得不切实际。我想知道是否有一种方法可以使用 lambda 来加快速度。这一切都基于这样的理解，即问题本质上是指数级的，而 lambda 可能不是值得关注的地方。从某种意义上说，我问这个问题只是为了更熟悉 lambda。

public ArrayList<String> nonconsecutiveOnes(int n){

    ArrayList<String> results = new ArrayList<String>();

        for(int i = 0; i < (int)Math.pow(2,n); i++ ){
            String a= Integer.toBinaryString(i); 
            if (a.contains("11")){
                continue;
            }
            if (a.length() < n)
            {
                char[] c = new char[n- a.length()];

                Arrays.fill(c, '0');
                String zeros = new String(c);

                a = zeros + a;
            }
                results.add(a);
        }
            return results; 
     }     
}

我已经测试过了。不过，还没有尝试过边缘情况。如果长度小于 1，仍然需要它只返回 null。

Answer 1

如果我没理解错的话，你需要输出所有小于 2^n 且不包含 2 个连续 1 的数字的二进制表示。 您可以将其改写为所有长度为 n 的 1 和 0 字符串，其中没有“11”。

你基本上可以将其视为一棵树，你可以逐个符号地输出它，你可以在 0 之后分支(尝试 0 和 1)，但不要在 1 之后分支。

不确定 java lambda 中的 lambda 是否有助于加快速度。

但是您可能会考虑尝试递归地解决这个问题，这应该会让您接近功能实现。

例如(没有声称它是最佳的):

public class Ex {

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

    public static void printAllStrings(int length) {
        printAllStrings("0", length);
        printAllStrings("1", length);
    }

    public static void printAllStrings(String prefix, int length) {
        if (prefix.length() == length) {
            System.out.println(prefix);
        } else {
            printAllStrings(prefix + "0", length);
            if (prefix.endsWith("0")) {
                printAllStrings(prefix + "1", length);
            }
        }
    }
}