我想知道如何把非连续的问题转化为声明逻辑。
我已经实现并测试了一个函数的命令式实现,该函数输入一个int参数并返回所有没有连续1s的二进制字符串的arraylist。我已经测试了它,但是函数的tc使它在15之后变得不实际。我想知道是否有一种方法可以使用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的空值。
最佳答案
如果我理解正确,则要求您输出所有小于2^n且不包含2个连续1的数字的二进制表示。
您可以将其重新表述为长度n为1和0的所有字符串,其中没有“11”。
基本上,你可以把它看作一棵树,在那里你一个符号一个符号地输出它,在0之后分支(尝试0和1),但是不要在1之后分支。
不确定java lambdas中的lambdas是否有助于加快速度。
但是您可以考虑尝试递归地解决这个问题,这将使您接近于函数实现。
例如(没有要求它是最优的):
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);
}
}
}
}