Javascript 面试中常见的小算法问题

最近在多次的校招面试中，面试官都问到了我一些算法问题，可能是因为之前没有好好的刷过算法也没有针对性的去准备方面的知识，导致自己答的不太好，即使针对面试官的有些问题能够给出自己的大体思路，但是面试官让我去给出更优的解决方案时也会无从应答。之前我主要是觉得前端这块对算法的要求不是很高，没必要去刷算法。但是实习期间和校招面试的经历告诉我，算法这东西对于一个技术开发者来说是一项必备的基本技能。

因此最近我花时间把前端开发中可能会用到的一些基本的算法问题整理了一下，下面的一些 javascript 的基本算法题是我在 That Js Dude上学习并整理出来的，希望会对你们有所帮助。

1. 判断一个数是不是质数？

问：你怎么去检查一个数是不是质数？
答：一个质数就是只能被它本身和1整除，那么我可以首先定义一个除数divisor，然后开启while循环，如果给定的数你能够被divisor整除，则可以判定它不是质数，否则让divisor递增1。如果循环之后发现都没有这样的divisor存在，则判定它是质数。

方法1：

function isPrime(n){
    var divisor = 2;

    while (n > divisor){
        if(n % divisor == 0){
            return false; 
        } else {
            divisor++;
        }
    }
    return true;
}
> isPrime(137);
  = true
> isPrime(237);
  = false

这种方法是最容易能够想到的，但是还存在很大的优化空间。

问：能优化下么？
答：可以，上面循环中我对divisor每次增加1，其实 n > 3 的时候divisor每次递增2就可以，因为一个数如果可以被一个偶数整除，那么它就可以被2整除。因此我可以减少一些循环次数。

• step-1: Any number will not be divisible by a number bigger than half of it. for example, 13 will never be divisible by 7, 8, 9 .. it could be as big as half of it for even number. for example, 16 will be divisible by 8 but will never be by 9, 10, 11, 12…
• Decision: a number will never be divisible by a number bigger than half of its values. So, we dont have to loop 50%
• step-2: Now, if a number is not divisible by 3. (if it is divisible by 3, then it wouldn’t be a prime number). then it would be divisible any number bigger than the 1/3 of its value. for example, 35 is not divisible by 3. hence it will be never divisible by any number bigger than 35/3 will never be divisible by 12, 13, 14 … if you take an even number like 36 it will never be divisible by 13, 14, 15
• Decision: a number could be divisible by numbers 1/3 of its value.
• step-3: For example u have the number 127. 127 is not divisible by 2 hence you should check upto 63.5. Secondly, 127 is not divisible by 3. So, you will check up to 127/3 approximately 42. It is not divisible by 5, divisor should be less than 127/5 approximately 25 not by 7. So, where should we stop?
• Decision: divisor would be less than Math.sqrt (n)

方法2：

function isPrime(n) {
    var divisor = 3,
        limit = Math.sqrt(n);
    // 2,3肯定是质数
    if (n === 2 || n === 3) {
        return true;
    }
    // 被2整除，肯定不是质数
    if (n % 2 === 0) {
        return false;
    }
    // 循环遍历
    while (divisor <= limit) {
        if (n % divisor === 0) {
            return false;
        } else {
            // 当n>3,不需要每次加1，直接加2即可
            divisor += 2;
        }
    }
    return true;
}

> isPrime(137);
  = true
> isPrime(237);
  = false

2. 找出一个偶数的所有质数因子？

问：给你任意一个偶数，让你找出它的所有质数因此，怎么做？
答：2是最小的质数，我选择2作为基准除数，让给定数去循环的除以这个除数，如果能整除，则把整除之后的数再去除以基准除数，如果不能整除，则调整基准除数，然后再进行判断。

具体代码如下：

function primeFactors(n) {
    var divisor = 2,
        factors = [];

    while (n >= 2) {
        if (n % divisor === 0) {
            factors.push(divisor);
            n = n / divisor;
        } else {
            divisor++;
        }
    }
    return factors;
}
> primeFactors(12)
  = [2, 2, 3]

3. Fibonacci数？

问：给定一个数n，如何找到第n个 Fibonacci 数
答：通过数组的形式，列出fibo数组，然后填充每一项。

方法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(5)
  = 8
> fibonacci(6)
  = 13

问：如果用递归怎么实现？
答：可以。

方法2：

function fibonacci(n) {
    if (n < 2) {
        return n;
    }  
    return fibonacci(n - 1) + fibonacci(n - 2);
}
> fibonacci(5)
  = 8
> fibonacci(6)
  = 13

4. 找出两个数的最大公约数？

问：给定两个整数，找出它们的最大公约数
答：取divisor为2作为基准除数，让两个数去除以divisor如果它们都能被整除，则更新最大公约数，依次循环即可

方法1：

function biggestFactor(num1, num2) {
    var divisor = 2,
        biggestDivisor = 1;
    while (num1 >= divisor && num2 >= divisor) {
        if (num1 % divisor === 0 && num2 % divisor === 0) {
            biggestDivisor = divisor;
        }
        divisor++;
    }
    return biggestDivisor;
}
> biggestFactor(12,16)
  = 4

方法2：

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

这种方法没大看懂。。。

5. 数组去重？

问：现在有一个数组，如何去掉其中重复的元素
答：设定exists对象，遍历数组，让数组项作为exists对象的键并设值为 true，如果遇到exists对象的键对应值为undefined，则该数组项是第一次出现，并把它 push 到结果数组中

具体代码如下：

function duplicateArr(arr) {
    var i = 0,
        len = arr.length,
        res = [],
        exists = {};

    for (var i = 0; i < len; i++) {
        var elm = arr[i];
        if (!exists[elm]) {
            res.push(elm);
            exists[elm] = true;
        }
    }
    return res;
}

6. 合并两个排序数组？

代码如下：

function merge(arr1, arr2) {
    var iA = 0, iB = 0,
        lenA = arr1.length,
        lenB = arr2.length,
        res = [];
    while (iA < lenA && iB < lenB) {
        if (arr1[iA] < arr2[iB]) {
            res.push(arr1[iA++]);
        } else {
            res.push(arr2[iB++]);
        }
    }
    return res.concat(arr1.slice(iA), arr2.slice(iB));
}
> merge([2,5,6,9], [1,2,3,29])
  = [1, 2, 2, 3, 5, 6, 9, 29]

还可以下面这样：

function merge(arr1, arr2) {
    var res = [];
    while (arr1.length > 0 && arr2.length >0) {
        if (arr1[0] < arr2[0]) {
            res.push(arr1.shift());
        } else {
            res.push(arr2.shift());
        }
    }
    return res.concat(arr1, arr2);
}
> merge([2,5,6,9], [1,2,3,29])
  = [1, 2, 2, 3, 5, 6, 9, 29]

7. 字符反转？

方法1：

function reverseStr(str) {
    var resStr = '';
    for (var i = str.length - 1; i >= 0; i--) {
        resStr += str[i];
    }
    return resStr;
}

方法2：

function reverseStr(str) {
    if (!str || typeof str !== 'string' || str.length < 2) {
        return str;
    }
    var strArr = [];
    for (var i = str.length - 1; i >= 0; i--) {
        strArr.push(str[i]);
    }
    return strArr.join('');
}

方法3：

function reverseStr(str) {
    var strArr = str.split('');
    var len = strArr.length;
    var middleIndex = Math.floor(len / 2);

    for (var i = 0; i <= middleIndex; i++) {
        var temp = strArr[i];
        strArr[i] = strArr[len - i - 1];
        strArr[len - i - 1] = temp;
    }
    return strArr.join('');

}

方法4：

function reverseStr(str) {
    if (str.length < 2) {
        return str;
    }
    return reverse(str.substr(1)) + str.charAt(0);
}

方法5：

function reverseStr(str) {
    if (!str || srt.length < 2) {
        return str;
    };
    var strArr = str.split('').reverse();
    return strArr.join('');

}

8. 反转语句？

代码如下：

function reverseWords(str) {
    var rev = [], 
        wordLen = 0;
    for (var i = str.length-1; i >= 0; i--) {
        if(str[i] === ' ' || i === 0){
            rev.push(str.substr(i,wordLen+1));
            wordLen = 0;
        } else {
            wordLen++;
        }
    }
    return rev.join(' ');
}

优化代码：

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

9. 寻找一个数组中的最大的两个值的和？

代码如下：

function topSum(arr) {
    var biggest = arr[0],
        second = arr[1],
        i = 2,
        len = arr.length;
    if (biggest < second) {
        biggest = arr[1];
        second = arr[0];
    }
    for (; i < len; i++) {
        if (biggest < arr[i]) {
            second = biggest;
            biggest = arr[i];
        } else if (second < arr[i]) {
            second = arr[i];
        }
    }
    return biggest + second;
}
> topSum([1,8,9,12,2,3,4])
  = 21

10. 给定两个无序数组，找出是否能有两个元素想加等于指定的一个数，返回这样的两个数的下标？

思路：最先想到的是双重循环

代码如下：

function sumFinder(arr, num) { 
    var len = arr.length;
    var res = [];
    for (var i = 0; i < len - 1; i++) {
        for (var j = i + 1; j < len; j++) {
            if (arr[i] + arr[j] === num) {
                res.push({
                    index1: i,
                    index2: j
                });
            } 
        }
    }
    return JSON.stringify(res);
}

问：有没有更好的方法呢？
答：

代码如下：

function sumFinder(arr, num) {
    var differ = {},
        substract,
        i = 0;
        len = arr.length;
    for (; i < len; i++) {
        substract = num - arr[i];
        if (!differ[substract]) {
            differ[arr[i]] = true;
        } else {
            return true
        }
    }
    return false;
}

问：还有没更好的办法？
答：

代码如下：

function sumFinder(arr, num) {
    arr = arr.sort(function (a, b) {
        return a - b;
    });
    console.log(arr);
    var iLeft = 0, 
        iRight = arr.length - 1;
    var res = [];
    while (iLeft < iRight) {
        console.log(1);
        if (arr[iLeft] + arr[iRight] > num) {
            iRight--;
        } else if (arr[iLeft] + arr[iRight] < num) {
            iLeft++;
        } else {
            res.push({
                index1: iLeft,
                index2: iRight
            });
            iLeft++;
            iRight--;
        }

    }
    return JSON.stringify(res);
}

11. 水仙花数？

问：给你个数，判断它是不是水仙花数？
答：水仙花就是每一位的n次幂的和等于其自身的数

代码如下：

function narcissistic(value) {
    var val = String(value).split(''),
        len = val.length;
    var result = val.map(function (v, i) {
        v = parseInt(v, 10);
        return Math.pow(v, len);
    }).reduce(function (prev, curr, i, arr) {
        return prev + curr;
    });
    return result === value;
}

问：如何生成从 n 到 m 的所有水仙花数？
答：遍历之即可，暂时没有想到更好的办法。。。

代码如下：

function generateNarcissistic(n, m) {
    var result = [];
    var i = n,
        val = [],
        tmp = 0;
    while (i <= m) {
        val = String(i).split('');
        var len = val.length;
        tmp = val.map(function (v, i) {
            v = parseInt(v, 10);
            return Math.pow(v, len);
        }).reduce(function (prev, curr) {
            return prev + curr;    
        });
        if (i === tmp) {
            result.push(i);
        }
        i++;
    }
    return result;
}

12. 数组乱序？

问：如何将一个排序好的数组乱序？
答：可以运用著名的 Fisher–Yates 算法

具体代码如下：

function randomarizeArray(arr) {
    var curIndex = 0,
        randomIndex,
        tmpValue,
        len = arr.length;

    while (curIndex !== (len - 1)) {
        randomIndex = Math.floor(Math.random() * (len - 1 - curIndex + 1) + curIndex);
        tmpValue = arr[curIndex];
        arr[curIndex] = arr[randomIndex];
        arr[randomIndex] = tmpValue;
        curIndex++;
    }
    return arr;
}

还可以如下：

function shuffle(array) {
    var counter = array.length, temp, index;

    // While there are elements in the array
    while (counter > 1) {
        // Pick a random index
        index = Math.floor(Math.random() * (--counter));
        console.log(index);
        // Decrease counter by 1

        // And swap the last element with it
        temp = array[counter];
        array[counter] = array[index];
        array[index] = temp;
    }

    return array;
}

13. 数组扁平化？

问：给定一个随机数组，数组可能包含数组，将其扁平化并去掉其中的重复元素。
答：采取递归调用的方式

function flatArray(arr) {
    var result = [];
    process(arr);
    function process(arr) {
        var i = 0, len = arr.length, item;
        for (; i < len; i++) {
            item = arr[i];
            if (typeof item === 'number' && result.indexOf(item) == -1) {
                result.push(item);
            } else if (Object.prototype.toString.call(item) === '[object Array]') {
                process(item);
            }
        }
    }
    return result;
}

14. 找出一个字符串中的第一个不重复字符

问：如果给你一个字符串，比如”stress”，如何找出第一个不重复出现的字符”t”
答：遍历整个字符串，然后运用indexOf(char)来找出第一个不重复的字符

具体代码如下：

function repeater(str) {
    for (var i = 0; i < str.length; i++) {
        var char = str.charAt(i); 
        if (str.indexOf(char) === i && str.indexOf(char, i + 1) === -1) {
            return char;
        }
    }
    return null;
}

此外还可以通过正则表达式匹配的方式
具体代码如下：

function repeater(str) {
    var result = false;

    while (str) {
        var len = str.length;
        var char = string[0];
        var reg = new RegExp(char, "gi");
        str = str.replace(reg, "");
        if (str.length == len - 1) {
            result = char;
            break;
        }
    }
    return result;
}

还有一种解决方案：

function repeater(str) {
    var strArr =  str.split('');
    for (var i = 0; i < str.length; i++) {
        var char = str.charAt(i);
        if (strArr.filter(function (j) {
                return j === char;
            }).length === 1) {
            return char;
        }
    }
    return null;
}

15. 找出一个数组的最大和的子数组

问：给你一个数组，如何找出这个数组的最大和子数组
答：

具体代码如下：

function childArray(arr) {
    var currSum = arr[0], maxSum = arr[0], iL = 0, iR, begain, end;
    for (var i = 1; i < arr.length; i++) {
        if (currSum > 0) {
            currSum += arr[i];
            iR = i;
        } else {
            currSum = arr[i];
            iL = i;
            iR = i;
        }
        if (currSum > maxSum) {
            maxSum = currSum;
            begain = iL;
            end = iR;
        }
    }
    return maxSum+""+begain+""+end;
}

16. 给定顺序数组，去掉两个数，然后数组乱序，找出去除的两个数

具体代码如下：

function absent(arr){
    var mia= [], min= Math.min.apply('',arr), max= Math.max.apply('',arr);
    while(min<max){
        if(arr.indexOf(++min)== -1) mia.push(min);
    }
    return mia;
}