【摘自《程序员面试宝典》】几个有趣的算法技巧
作者:zhanhailiang 日期:2012-12-10
1.如何计算一个自然数转成二进制表示后包含1的数量
function f(n) { var count = 0; while(n) { count ++; n = n & (n-1); } return count;} console.log(f(1024));
2.用一个表达式判断一个数N是否是2的M次幂(M>1),限制:不可使用循环。
2的M次幂这样的数转化成二进制是10,100,1000。若M减1后与X做与运算,答案若为0,则N是2的M次幂。
!(N&(N-1))
3.交换a与b,即如何将a,b的值交换,并且不使用任何中间变量。 1)
var a = 1, b = 2;a = a + b; b = a - b; a = a - b;console.log(a);console.log(b);
2). 1)方法的缺点是若a,b都是比较大的数,则a = a + b时可能会超界。故采用
var a = 1, b = 2;a = a^b; b = a^b; a = a^b;console.log(a);console.log(b);
这样便无须担心超界的问题。
4.输入一行字符串,找出其中出现的相同且长度最长的字符串,输出它及其首字符的位置,如“yyabcdabjcabceg”,输出结果应该为abc和3.
原理:可以将字符串“yyabcdabjcabceg”分解成:
yyabcdabjcabcegyabcdabjcabcegabcdabjcabcegbcdabjcabcegcdabjcabcegdabjcabcegabjcabcegbjcabcegjcabcegcabcegabcegbcegcegegg
对这几个字符串排序,然后比较相邻字符串的前驱即可,很容易求出最长的公共前前驱。
function getLongestSubstring(str) { for(var i = str.length - 1; i > 1; i--) { for(var j = 0; j < str.length; j++) { var t = 0; var num = 0; temp = str.substr(j, i); // 从大到小取子串 t = str.indexOf(temp); // 正序查找 num = str.lastIndexOf(temp); // 逆序查找 if(t !== num) { // 若两次查找位置不一致说明存在重复子串 return [temp, t + 1]; // 记录子串及位置 } } } return 0;} console.log(getLongestSubstring("yyabcdabjcabceg"));