这次给大家带来Js面试中容易遇到的算法,下面就是实战案例,一起来看一下。

素数

Q:你将如何验证一个素数?

A:一个素数只能被它自己和1整除。所以,我将运行一个while循环并加1。(看代码示例,如果你无法理解,那这不是你的菜。先回去学习javaScript基础知识然后再回来吧。)

方法1

function isPrime(n){ var pisor = 2; while (n > pisor){ if(n % pisor == 0){ return false; } else pisor++; } return true; } isPrime(137); // = true isPrime(237); // = false

Q:你能做得更好吗?

A:可以。除数一次增加1个。 在3之后我可以增加2.如果一个数可以被任何偶数整除,它将被2整除。

补充:如果你不需要把除数增加到这个数。你可以更早停止。让我在下面的步骤中解释一下(如果需要可以多读几遍)

第一步,任何数字都不能被大于它的一半的数字整除。 例如,13将永远不能被7,8,9整除……它甚至可以是偶数的一半。 例如,16将被8整除,但永远不会被9,10,11,12 ……
结论:一个数字将永远不能被一个大于其一半数值的数字整除。 所以,我们可以少循环50%。

第二步,现在,如果一个数字不能被3整除。(如果它可被3整除,那么它就不是质数)。然后,它不可以被大于其值1/3的任何数整除。例如,35不能被3整除。因此,它永远不会被大于35/3的数整除,永远不能被12, 13, 14整除…如果你取一个像36一样的偶数,它将永远不能被13, 14, 15整除。

结论: 一个数字可以被其数值的三分之一整除。

第三步,例如,你有一个数字127。127不能被2整除,因此你最多应该检查63.5。其次,127不能被3整除。因此,您将检查到127/3大约42。它不能被5整除,除数应该小于127/5大约25,而不是7。那么,我们该在哪里停下来?
结论: 除数将小于math.sqrt(N)

方法2

如果你不能理解也不用担心,别管它。如果那你不是一个研究人员就没关系。

function isPrime(n) { var pisor = 3, limit = Math.sqrt(n); //check simple cases if (n == 2 || n == 3) return true; if (n % 2 == 0) return false; while (pisor <= limit) { if (n % pisor == 0) return false; else pisor += 2; } return true; } isPrime(137); // = true isPrime(237); // = false

素数因子

Q:如何求出一个数的所有素数因子?
A:执行一个while循环。开始除以2,如果不能整除,记录这个除数,直到完成。

function primeFactors(n){ var factors = [], pisor = 2; while(n>2){ if(n % pisor == 0){ factors.push(pisor); n= n/ pisor; } else{ pisor++; } } return factors; } primeFactors(69); // = [3, 23]

Q:运行时间复杂度是多少? 你能做得更好吗?

A:O(n)。可以将除数从3开始,累加2。因为,如果一个数被任何偶数整除,它将被2整除。因此,你不需要除以偶数。此外,你不会有一个大于其价值一半的因素。如果你想让它变得复杂,那就用第一题的补充概念吧。

Fibonacci(斐波那契)

Q:如何获得第n个斐波纳契数字?
A: 我创建一个数组并从迭代开始。

斐波那契系列是面向初学者的最受欢迎的面试问题之一。 所以,你必须学习这一个。

方法1

function fibonacci(n){ var fibo = [0, 1]; if (n <= 2) return 1; for (var i = 2; i <=n; i++ ){ fibo[i] = fibo[i-1]+fibo[i-2]; } return fibo[n]; } fibonacci(12); // = 144

Q: 运行时间复杂度是多少?

A: O(n);

Q: 你能让它递归吗?

方法2

function fibonacci(n){ if(n < =1) { return n; } else { return fibonacci(n-1) + fibonacci (n-2); } } fibonacci(12); // = 144

Q: 运行时间复杂度是多少?
A: O(2n);关于时间复杂度的细节

最大公约数

Q: 你会如何找到两个数字的最大公约数?

function greatestCommonpisor(a, b){ var pisor = 2, greatestpisor = 1; //if u pass a -ve number this will not work. fix it dude!! if (a < 2 || b < 2) return 1; while(a >= pisor && b >= pisor){ if(a %pisor == 0 && b% pisor ==0){ greatestpisor = pisor; } pisor++; } return greatestpisor; } greatestCommonpisor(14, 21); // 7 greatestCommonpisor(69, 169); // = 1

算法范式

很抱歉。我也无法解释它。 因为我自己80%的情况下都不能理解它。 我的算法分析教练告诉我这个,又从课堂笔记偷走(我是一个好学生,顺便说一句!)

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

注意:用你的大脑来理解它。

去重

Q:你将如何从数组中删除重复的成员?
A: 执行一个循环,并保存一个对象/关联数组。如果我第一次找到一个元素,我会设置它的值为真(这将告诉我元素添加一次)。如果我在对象中找到这个元素,我不会将它插入到返回数组中。

function removeDuplicate(arr){ var exists ={}, outArr = [], elm; for(var i =0; i<arr.length; i++){ elm = arr[i]; if(!exists[elm]){ outArr.push(elm); exists[elm] = true; } } return outArr; } removeDuplicate([1,3,3,3,1,5,6,7,8,1]); // = [1, 3, 5, 6, 7, 8]

合并两个排序的数组

Q: 怎样合并两个已排序数组?
A: 我将为每个数组保留一个指针(看代码,并注意这个)。

function mergeSortedArray(a, b){ var merged = [], aElm = a[0], bElm = b[0], i = 1, j = 1; if(a.length ==0) return b; if(b.length ==0) return a; /* if aElm or bElm exists we will insert to merged array (will go inside while loop) to insert: aElm exists and bElm doesn't exists or both exists and aElm < bElm this is the critical part of the example */ while(aElm || bElm){ if((aElm && !bElm) || aElm < bElm){ merged.push(aElm); aElm = a[i++]; } else { merged.push(bElm); bElm = b[j++]; } } return merged; } mergeSortedArray([2,5,6,9], [1,2,3,29]);// = [1, 2, 2, 3, 5, 6, 9, 29]

不通过临时变量交换两个数的值