1. JS面试中常见的算法题

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

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

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. 斐波那契

1、1、2、3、5、8......，求第n个数的值。(肥婆纳妾数列)

最简单的做法：递归

function fibonacci(N) {
    if (N < 2) return N;
    return fibonacci(N - 1) + fibonacci(N - 2);
}

但是递归会有严重的效率问题。比如想要求得f(10)，首先需要求f(9)和f(8)。同样，想求f(9)，首先需要f(8)和f(7)...这样就有很多重复值，计算量也很大。
改进：从下往上计算，首先根据f(0)和f(1)计算出f(2)，再根据f(1)和f(2)计算出f(3)......以此类推就可以计算出第n项。时间复杂度O(n)。

function fibonacci(N) {
    if ( N <= 1) return N;
    const result = new Array(N);
    result[0] = 0;
    result[1] = 1;
    for (let i = 2; i < N + 1; i++) {
        result[i] = result[i - 1] + result[i - 2];
    }
    return result[N];
}
console.log(fibonacci(5));

3. 求最大公约数

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

// 方法一
function greatestCommonDivisor1(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(greatestCommonDivisor1(8, 4)); // 4
console.log(greatestCommonDivisor1(69, 169)); // 1

// 方法二
function greatestCommonDivisor2(a,b){
    if (b === 0) {
        return a;
    } else {
        return greatestCommonDivisor2(b,a%b);
    }
};

4. 数组去重

对原数组进行遍历；
获取arr[i]的值 j ；
对应到辅助数组 exits 的位置 j 的值，如果没有，则证明arr[i] 的值没有重复；
此时将值 j 存入res数组，并将辅助数组 j 位置的值置为 true。
最后返回res数组。

// 方法一
function reset(arr){
  let n = []
  for(let i = 0; i < arr.length; i++ ){
    if(n.indexOf(arr[i] === -1)){
      n.push(arr[i])
    }
  }
  return n
}
console.log(reset([1, 10, 2, 1, 1, 2, 3])) // [1, 10, 2, 3]


// 方法二
[...new Set([1, 10, 2, 1, 1, 2, 3])];

5. 删除重复的字符

解法和上一题类似。

 function removeDuplicateChar(str){
    if (!str || str.length < 2 || typeof str != "string") {
        return;
    };
    let charArr = [],res = [];
    for(let i = 0; i < str.length; i++){
        let c = str[i];
        if(charArr[c]){
            charArr[c]++;
        }else{
            charArr[c] = 1;
        }
    }
    for(let j in charArr){
        if (charArr[j] === 1) {
            res.push(j);
        }
    }
    return res.join("");
}
console.log(removeDuplicateChar("Learn more javascript dude"));

6. 字符串反向

// 方法一
function reverse(str){
    let resStr = "";
    for(let i = str.length-1; i >= 0; i--){
        resStr += str[i];
    }
    return resStr;
}
console.log(reverse("ABCDEFG"));

// 方法二
function reverse2(str){
    if (!str || str.length < 2 || typeof str != "string") {
        return str;
    };
    let res = [];
    for(let i = str.length-1; i >= 0; i--){
        res.push(str[i]);
    }
    return res.join("");
}
console.log(reverse2("Hello"));

7. 字符串原位反转

function reverseInPlace(str){
    return str.split(' ').reverse().join(' ').split('').reverse().join('');
}
console.log(reverseInPlace('I am the good boy'));

8. 判断是否是回文

function isPalindrome(str){
    if (!str || str.length < 2) {
        return;
    }
    for(let i = 0; i < str.length/2; i++){
        if (str[i] !== str[str.length-1-i]) {
            return false;
        }
    }
    return true;
}
console.log(isPalindrome("madama"))

// 面试题：打印出 1 - 10000 之间的所有对称数
// 例如：121、1331 等
// [...Array(10000).keys()].filter((x) => {
//   return x.toString().length > 1 && x === Number(x.toString().split('').reverse().join(''))
// })

9. 判断数组中是否有两数之和

eg：在一个未排序的数组中找出是否有任意两数之和等于给定的数。
给出一个数组[6,4,3,2,1,7]和一个数9，判断数组里是否有任意两数之和为9。
1、循环遍历数组，let subStract = num - arr[i];
2、如果 differ[subStract] 里有值，则返回true；如果没有，将 differ[arr[i]] 置为 true。

function sumFind(arr,num){
    if (!arr || arr.length < 2) {
        return;
    };
    let differ = {};
    for(let i = 0; i < arr.length; i++){
        let subStract = num - arr[i];
        if (differ[subStract]) {
            return true;
        } else {
            differ[arr[i]] = true;
        }
    }
    return false;
}
console.log(sumFind([6,4,3,2,1,7], 9));  // true

10. 连字符转成驼峰

如：get-element-by-id 转为 getElementById

// 方法一
function getCamelCase(str){
  let arr = str.split('-')
  return arr.map((item, index) => {
    console.log(item)

    if(index === 0){
      return item
    }else{
      return item.charAt(0).toUpperCase()
    }
  }).join('')
}

console.log(getCamelCase('name-age-height')) // nameAgeHeight

// 方法二
function getCamelCase(str) {
  return str.splice(/-([a-z])/g, function(all, i){
    return i.toUppercase()
  })
}

11. 加油站问题-贪心算法

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。
要求：
输入：第一行有2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。
输出：输出编程计算出的最少加油次数。如果无法到达目的地，则输出"NoSolution"。

function greedy(n, k, arr){
    // n:加满可以行驶的公里数; k:加油站数量; arr:每个加油站之间的距离数组
    if (n == 0 || k == 0 || arr.length == 0 || arr[0] > n) {
        return "No Solution!";  // arr[0] > n ：如果第一个加油站距离太远，也无法到达
    };
    let res = 0, distance = 0;  // res：加油次数；distance：已行驶距离
    for(let i = 0; i <= k; i++){
        distance += arr[i];
        if (distance > n) {  // 已行驶距离 > 加满可以行驶的公里数
            if(arr[i] > n){  // 如果目前加油站和前一个加油站的距离 > 加满可以行驶的公里数，则无法到达
                return "No Solution!";
            };
            // 可以在上一个加油站加油，行驶到目前的加油站i：
            distance = arr[i];
            res++;  // 加油次数+1
        }
    }
    return res;
}
let arr = [1,2,3,4,5,1,6,6];
console.log(greedy(7,7,arr))  // 4

12. 用正则实现trim()清除字符串两端空格

String.prototype.trim1 = function(){
    // return this.replace(/\s*/g,"");  // 清除所有空格
    return this.replace(/(^\s*)|(\s*$)/g,"");  // 清除字符串前后的空格
};
console.log("  hello word ".trim1())  // "hello word"

13. 将数字12345678转化成RMB形式：12,345,678

思路：将字符串切割成数组再反转，遍历数组，加入辅助数组，当数组长度为3的倍数，再向辅助数组加入 “,”。

// 方法一
function RMB(str){
    let arr = str.split("").reverse();
    let res = [];
    for(let i = 0; i < arr.length; i++){
        res.push(arr[i]);
        if ((i + 1) % 3 === 0) {
            res.push(",");
        }
    }
    return res.reverse().join("");
}
console.log(RMB("12345678"))

// 方法二
Number(12345678).toLocaleString()

// 方法三
'12345678'.replace(/\B(?=(\d{3})+(?!\d))/g, ',')

14. 删除相邻相同的字符串

function delSrt(str){
    let res = [], nowStr;
    for(let i = 0; i < str.length; i ++){
        if (str.charAt(i) != nowStr) {
            res.push(str.charAt(i));
            nowStr = str.charAt(i);
        }
    }
    return res.join("");
}
console.log(delSrt("aabcc11"))

15. 排序 (从小到大)

// 冒泡排序（两两比较）
function bubbleSort(array) {
  var temp; // 临时角色
  for (var i = 0; i < array.length; i++) {
    for (var j = array.length - 1; j > i; j--) {
      if (array[j] < array[j - 1]) {
        temp = array[j];
        array[j] = array[j - 1];
        array[j - 1] = temp;
      }
    }
  }
  return array;
}

// 快速排序
// - 选择基准值(base)，原数组长度减一(基准值)，使用 splice
// - 循环原数组，小的放左边(left数组)，大的放右边(right数组);
// - concat(left, base, right)
// - 递归继续排序 left 与 right
function qSort(arr) {
  if (arr.length == 0) return []
  let left = [], right = [], pivot = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return qSort(left).concat(pivot, qSort(right));
}