将命令式代码转换为声明性代码以进行非连续一个实现

Question

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

我已经实现并测试了一个函数的命令式实现，该函数输入单个 int 参数并返回没有连续 1 的所有二进制字符串的字符串的 ArrayList。我已经测试过它，但该函数的 TC 使其超过 15 不切实际。我想知道是否有办法使用 lambda 来加快速度。这一切都是在理解下，问题本质上是指数级的，lambdas可能不是寻找的地方。从某种意义上说，我问这个问题只是为了更适应 lambdas。

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 之后分支。

不确定 lambdas 像 java 中那样有助于加快速度。

但是你可以考虑尝试递归地解决这个问题，这应该让你处于功能实现的附近。

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

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);
}
}
}
}