(澳门正规博彩十大网站) CodeWars算法 Twice linear 问题

折腾了两天了,一直只是通过测试,但是提交的时候会出错,代码效率太差。求大神指点…
算法如下:
*”Consider a sequence u where u is defined as follows:
The number u0 = 1 is the first one in u.
For each x in u, then y = 2 x + 1 and z = 3 x + 1 must be in u too.
There are no other numbers in u.
Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, …]
1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on…”*

我的代码如下`

public static int dblLinearint n
{ ArrayList<Long> arrayresult = new ArrayList<Long>; arrayresult.addlong 1; //循环,生成这样的u[]数组。但是i太大的话,会超时 for int i = 1; i <= 15; i++ { arrayresult = CreateArrayListarrayresult; } System.out.printlnarrayresult.toString; long location = arrayresult.getn; return intlocation;
} public static ArrayList<Long> CreateArrayListArrayList<Long> resultArray
{ ArrayList<Long> tmp = ArrayList<Long>resultArray.clone; for long single : resultArray { //按照规则,生成y和z。 long y = single * 2 + 1; long z = single * 3 + 1; //看看y和z在不在数组里面,不在的话,添加进去。 if resultArray.indexOfy == -1 { tmp.addy; } if resultArray.indexOfz == -1 { tmp.addz; } } Collections.sorttmp; return tmp;
} public static void mainString[] args
{ System.out.printlnDoubleLinear.dblLinear100;
}`

提示错误:”Process was terminated. It took longer than 10000ms to complete
0 Passed”

如果循环的i设置的小,那么数组里面的数字也不完整。归根到底,还是代码效率太差…求指导啊

我今天也遇到了同样的问题;我们俩的算法思路是一样的(同样都超时),所以这可能是算法不够好,我现在仍在想有没有更好的算法,最后百度了下。。。(ps:好重的罪恶感)

  • 下面这两个算法思路不对,都超时(后一个是前一个算法的改进,但依然超时)

function dblLinearn { let i = 0, arr = [1]; whilei<=n{ let x = arr[i], y = 2 * x + 1, z = 3 * x + 1; // 写入数组(跳过重复值) if!arr.includesy{ arr.pushy; } if!arr.includesz{ arr.pushz; } // 排序 arr.sortfunctiona, b{ return a - b; }; i += 1; } return arr[n];
} function dblLinearn { let temp = [1], y = 0, z = 0, i = 0, j = 0, k = 0; while i < n { y = temp[i] * 2 + 1; z = temp[i] * 3 + 1; // 按顺序插入 y z(避免排序) for j=temp.length-1; j>-1; j-=1 { if y == temp[j] {// 避免重复 break; } if y > temp[j] {// 冒泡插入 y temp.splicej + 1, 0, y; break; } } for k=temp.length-1; k>-1; k-=1 { if z == temp[k] { break; } if z > temp[k] { temp.splicek + 1, 0, z; break; } } i += 1; } return temp[n];
}

  • 正确算法

function dblLinearn { let ai = 0, bi = 0, eq = 0, sequence = [1]; while ai + bi < n + eq {// ai + bi - eq 是 push 进数组的数的个数 let y = 2 * sequence[ai] + 1, z = 3 * sequence[bi] + 1; if y < z {// 先把 x y 中较小的压入 sequence sequence.pushy; ai++; } else if y > z { sequence.pushz; bi++; } else { sequence.pushy; ai++; bi++; eq++; } } return sequence.pop;
}

正确算法出处:http://www.cnblogs.com/qingmingsang/articles/5355167.html

该答案已被忽略,原因:

发表评论

电子邮件地址不会被公开。 必填项已用*标注