js面试算法

验证一个数是否是质数

质数只能被1和它自己整除，因此令被除数从2开始，若能整除则不是质数，若不能整除则加一，直到被除数到达根号n，此时n则是质数。

var isPrime = function(n){ var divider = 2; var limit = Math.sqrt(n); while(divider<=limit){ if(n%divider == 0){ return false; } divider++; } return true; }

能否改进？ 除数每次增加1。当到达3后可以增加2。因为如果一个数字可被任何偶数除尽，它将被2整除。

查找数字的所有质数因子？

divider从2开始如果n能整除divider，则将divider加入到结果中，n为此次计算后的商如果n不能整除divider，则divider++ var primeFactors = function(n){ var factors = []; var divider = 2; while(n>2){ if(n%divider == 0){ factors.push(divider); n /= divider; }else{ divider++; } } return factors; }

时间复杂度为O(n)，改进方法和上面的差不多：divider=3之后每次加2。 因为，如果一个数字可被任何偶数除尽，它将被2整除。因此，你不需要除以偶数。

获得第n个斐波那契数字

解法一：迭代 var fibonacci = function(n){ var fibo = [0,1]; for(var i=2;i<=n;i++){ fibo[i] = fibo[i-1]+fibo[i-2]; } return fibo[n]; }

O(n)

解法二：递归 var fibonacci = function(n){ if(n>=2){ return fibonacci(n-1)+fibonacci(n-2); }else{ return n; } }

O(2的n次方)

找到两个数的最大公约数？

解法一：遍历 var greatestCommonDivisor= function(a,b){ if(a<2 || b<2) return 1; var divider = 2; var greatestDivisor = 1; while(divider<=a && divider<=b){ if(a%divider == 0 && b%divider == 0){ greatestDivisor = divider; } divider++; } return greatestDivisor; }

解法二：辗转相除法

又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法……

有解释的，但我选择不去理解……

function greatestCommonDivisor(a, b){ if(b == 0) return a; else return greatestCommonDivisor(b, a%b); }

合并两个排序数组？

var mergeSortedArray = function(a,b){ var merge = []; var i = 0,j = 0; var k = 0; while(i<a.length || j<b.length){ if(i == a.length || (j!=b.length && a[i]>b[j])){ merge[k++] = b[j++]; }else{ merge[k++] = a[i++]; } } return merge; }

另一种思路是都合并到第一个数组中,in-place解法：

var mergeSortedArray = function(a,b){ var m = a.length; var n = b.length; var i = m-1,j = n-1; for(var k=n+m-1;k>=0;k--){ if(j<0 || a[i]>b[j]){ a[k] = a[i--]; }else{ a[k] = b[j--]; } } return a; }

在不使用临时变量的情况下交换两个数字？

解法一： function swap(a,b){ b = b-a; a = a+b; b = a-b; } 解法二：位操作 function swap(a,b){ a = a^b; b = a^b; a = a^b; }

在JavaScript中反转字符串？

解法一： function reverse(str){ var result = []; if(!str || typeof str != 'string' || str.length < 2 ) return str; for(var i=str.length;i>=0;i--){ result.push(str[i]); } return result.join(''); } 解法二：遍历一半，头尾交换 function reverse(str){ str = str.split(''); var temp; for(var i=0;i<str.length/2;i++){ temp = str[i]; str[i] = str[str.length-i-1]; str[str.length-i-1] = temp } return str.join(''); } 解法三：递归 function reverse (str) { if (str === "") { return ""; } else { return reverse(str.substr(1)) + str.charAt(0); } } 解法四：使用build in方法 function reverse(str){ return str.split('').reverse().join(''); }

在句子中反转词？

如fix this one 变为 one this fix。重点是检测到空格时进行处理。

解法一： function reverseWords(str){ var result = []; var wordLen = 0; for(var i = str.length-1;i>=0;i--){ if(str[i] === " " ){ result.push(str.substr(i+1,wordLen)); wordLen = 0; }else if(i===0){ result.push(str.substr(i,wordLen+1)); wordLen = 0; }else{ wordLen++; } } return result.join(' '); } 解法二：使用build in方法 function reverseWord(str){ return str.split(' ').reverse().join(' ') }

reverse in place

If you have a string like “I am the good boy”. How can you generate “I ma eht doog yob”? 反转每个单词中字符的顺序

function reverse(str){ return str.split(' ').reverse().join(' ').split('').reverse().join(''); }

找到字符串中的第一个非重复的字符？

遍历字符串，用一个对象当做hash表来存储重复字符。

function firstNonRepeatChar(str){ var count = {}; for(var i=0;i<str.length;i++){ if(count[str[i]]){ count[str[i]]++; }else{ count[str[i]] = 1; } } for(var prop in count){ if(count[prop] === 1){ return prop; } } }

删除字符串中重复的字符

其实是在上一个问题的基础上再进行操作：

function firstNonRepeatChar(str){ var count = {}; var result = []; for(var i=0;i<str.length;i++){ if(count[str[i]]){ count[str[i]]++; }else{ count[str[i]] = 1; } } for(var prop in count){ if(count[prop] === 1){ result.push(prop); } } return result.join(''); }

检查回文

解法一 function isPalindrome(str){ for(var i=0;i<str.length/2;i++){ if(str[i] !== str[str.length-1-i]){ return false; } } return true; } 解法二：使用build in 方法 function isPalindrome(str){ return str===str.split('').reverse().join(''); }

在n和m之间生成随机整数

Math.floor(Math.random()*(m-n))+n

如果你有一个函数生成1到5之间的随机数，怎么可以通过使用该函数生成5到7的随机数？

//function rand5() function rand7(){ return 5 + rand5() / 5 * 2; }

从未排序的整数数组中找出缺失的数字?

比如你有1到100的整数，而其中缺了一个，怎么找出这个数字？

利用等差数列公式计算这些数应得的和，再计算当前数组所有数字的和，二者的差即为缺少的数。

function missingNumber(arr){ var n = arr.length+1; var expectedSum = (1+n)*n/2; var sum = 0; for(var i=0;i<arr.length;i++){ sum+=arr[i]; } return expectedSum - sum; }

two sum

未排序的数组，检查是否有任何两个数字的和是给定的数字。 最暴力的方法就是两层循环，是O(n2).

改进方法使用一个对象作为哈希表，用于存储数，这样在每次搜寻是否有另一个数与当前数的和为sum时就可以在O(1)的时间内找到。

function twoSum(arr,sum){ var obj = {}; var num; for(var i=0;i<arr.length;i++){ num = sum - arr[i]; if(obj[num]){ return true; }else{ //若没有的话为当前数字建立索引 obj[arr[i]] = true; } } return false; }

找到任意两个数字的最大和

思路就是找到两个最大的数并返回它们的和。

function topSum(arr){ if(arr.length<2) return null; var first,second; if(arr[0]>arr[1]){ first = arr[0]; second=arr[1]; }else{ first = arr[1]; second=arr[0]; } for(var i=2;i<arr.length;i++){ if(arr[i]>first){ second = first; first = arr[i]; }else if(arr[i]>second){ second = arr[i]; } } return first+second; }

从1到n中0的总个数

n=50的话，有5个0，分别是10，20，30，40，50。 n = 120的话，分别是10到90，共九个，110到120，共2个，以及100的两个，一共13个。 也就是说10的整数次方会有多个零，如100，1000，那么就要利用现有的数计算包含了多少个10的平方数。

如2014，2014/10=201; 201/10 = 20; 20/10 = 2; 最后表明出现了两次10的三次方，即1000和2000。

由此也能整理出整个过程了：

function countZero(n){ var count = 0; while(n>0){ count+=Math.floor(n/10); n/=10; } return count; }

一定要记得给除数向下取整！！

如何匹配字符串的子字符串？

function substr(str,subStr){ for(var i=0;i<str.length;i++){ for(var j=0;j<subStr.length;j++){ if(str[i+j] != subStr[j]){ break; } } if(j == subStr.length){ return i; } } return -1; }

字符串的全排列

var result = []; function permutations(str){ var arr= str.split(''); helper(arr,0,[]); return result; } function helper(arr,index,list){ if(index === arr.length){ result.push(list.join('')); return; } for(var i = 0;i<arr.length;i++){ if(list.indexOf(arr[i]) != -1){ continue; } list.push(arr[i]); helper(arr,index+1,list) list.pop(); } }