js除了基础知识以外，算法也是挺重要的。因此特意整理了一些常见的算法题，希望大家有帮助。

 

1.验证一个数是否是素数

 

1、如果这个数是 2 或 3，一定是素数；

 

2、如果是偶数，一定不是素数；

 

3、如果这个数不能被3——它的平方根中的任一数整除，m必定是素数。而且除数可以每次递增（排除偶数）

 

function isPrime(num){

 

 if (num === 2 || num === 3) {

 

 return true;

 

 };

 

 if (num % 2 === 0) {

 

 return false;

 

 };

 

 let divisor = 3,limit = Math.sqrt(num);

 

 while(limit >= divisor){

 

 if (num % divisor === 0) {

 

 return false;

 

 }

 

 else {

 

 divisor += 2;

 

 }

 

 }

 

 return true;

 

}

 

console.log(isPrime(30)); // false

 

2.斐波那契

 

最简单的做法：递归。

 

function fibonacci(n){

 

 if (n <= 0) {

 

 return 0;

 

 }

 

 if (n == 0) {

 

 return 1;

 

 }

 

 return fibonacci(n-1) + fibonacci(n-2);

 

}

 

但是递归会有严重的效率问题。比如想要求得f(10)，首先需要求f(9)和f(8)。同样，想求f(9)，首先需要f(8)和f(7)…这样就有很多重复值，计算量也很大。

 

我自己是一名从事了多年开发的web前端老程序员，目前辞职在做自己的web前端私人定制课程，今年年初我花了一个月整理了一份最适合2019年学习的web前端学习干货，各种框架都有整理，送给每一位前端小伙伴，想要获取的可以在后台私信我：前端，即可免费获取。

 

改进：从下往上计算，首先根据f(0)和f(1)计算出f(2)，再根据f(1)和f(2)计算出f(3)……以此类推就可以计算出第n项。时间复杂度O(n)。

 

function fibonacci(n){

 

 let ori = [0,1];

 

 if (n < 2) {

 

 return ori[n];

 

 };

 

 let fiboOne = 1,fiboTwo = 0,fiboSum = 0;

 

 for (let i = 2; i <= n; i++) {

 

 fiboSum = fiboOne + fiboTwo;

 

 fiboTwo = fiboOne;

 

 fiboOne = fiboSum;

 

 }

 

 return fiboSum;

 

}

 

console.log(fibonacci(5));

 

3、求最大公约数

 

除数 在a和b的范围内，如果同时a和b处以除数的余等于0，就将此时的除数赋值给res；除数自增，不断循环上面的计算，更新res。

 

function greatestCommonDivisor(a, b){

 

 let divisor = 2,res = 1;

 

 if (a < 2 || b < 2) {

 

 return 1;

 

 };

 

 while(a >= divisor && b >= divisor){

 

 if (a%divisor === 0 && b%divisor === 0) {

 

 res = divisor;

 

 }

 

 divisor++;

 

 }

 

 return res;

 

};

 

console.log(greatestCommonDivisor(8, 4)); // 4

 

console.log(greatestCommonDivisor(69, 169)); // 1

 

解法2：

 

function greatestCommonDivisor(a,b){

 

 if (b === 0) {

 

 return a;

 

 } else {

 

 return greatestCommonDivisor(b,a%b);

 

 }

 

};

 

4、数组去重

 

对原数组进行遍历

 

获取arr[i]的值 j；

 

对应到辅助数组 exits 的位置 j 的值，如果没有，则证明arr[i] 的值没有重复，

 

此时将 值j 存入res数组，并将辅助数组 j 位置的值置为 true。

 

最后返回res数组。