Js面试算法详解(2)
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 greatestCommonDivisor(a, b){
var divisor = 2,
greatestDivisor = 1;
//if u pass a -ve number this will not work. fix it dude!!
if (a < 2 || b < 2)
return 1;
while(a >= divisor && b >= divisor){
if(a %divisor == 0 && b% divisor ==0){
greatestDivisor = divisor;
}
divisor++;
}
return greatestDivisor;
}
greatestCommonDivisor(14, 21); // 7
greatestCommonDivisor(69, 169); // = 1
算法范式
很抱歉。我也无法解释它。 因为我自己80％的情况下都不能理解它。 我的算法分析教练告诉我这个，又从课堂笔记偷走（我是一个好学生，顺便说一句！）
function greatestCommonDivisor(a, b){
if(b == 0)
return a;
else
return greatestCommonDivisor(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]
内容版权声明：除非注明，否则皆为本站原创文章。