js-经常遇到的算法题

---

最近在面试中遇到几个js算法题，感觉挺有借鉴意义，整理一下。

1. 数组去重
比如输入: [1,2,3,4,2,3,4]
输出: [1,2,3,4]
需要去掉重复的2、3、4 这两个元素
这道题在面试的试题中出现率比较高，主要考察个人对object的使用，利用key来进行筛选。有多种方法，这里只列举一种常用的方法。

function unique(arr){
  let res = [];
  let json = {};
  for (var i = 0 , l = arr.length; i < l; i++) {
        if (!json[arr[i]]) {
            res.push(arr[i]);
            json[arr[i]] = 1;
        }
  }
  return res;
}
let arr = [1,2,3,4,2,3,4];
console.log(unique(arr)); //[1,2,3,4]

2. 统计一个字符串中出现最多的及其出现的次数
给出一个字符串，统计出现次数最多的字母。如：“asdfssaaasasasasaa”，其中出现最多的是a

function repeated (str){
  let json = {};
  for(let i = 0 , l = str.length; i < l; i++){
    if(!json[str.charAt(i)]){
        json[str.charAt(i)] = 1;
    } else {
        json[str.charAt(i)]++;
    }
  }
  let iMax = 0;
  let iIndex = '';
  for(let j in json){
    if(json[j] > iMax){
        iMax = json[j];
        iIndex = j;
    }
  }
  console.log('出现次数最多的是:'+iIndex+'出现'+iMax+'次');
}
let str = 'asdfssaaasasasasaa';
repeated(str);

3.计算一个整数的阶乘
如果用字母n来代表一个整数，阶乘代表着所有小于或等于n的整数的乘积。阶乘通常简写成 n! ； 例如: （5! = 1 * 2 * 3 * 4 * 5 = 120）
刚开始想到的是用循环来实现，在实现之前需要对输入的数字做一下判断

function factorial (num) {
    if (num < 0) {
        return -1;
    } else if (num === 0 || num === 1) {
        return 1;
    } else {
        for (var i = num - 1; i >= 1; i--) {
            num *= i;
        }
    }
    return num;
};
let num = factorial(5);
console.log(num);

用递归来实现这一方法，毕竟阶乘函数是递归函数的典型实例

function factorialize(num) {
  return num > 1 ? num * factorialize(num-1) : 1;
}

4.冒泡排序

let examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
    for(let i=0;i<arr.length-1;i++){
        for(let j=0;j<arr.length-1-i;j++){
            if(arr[j]>arr[j+1]){
                let temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
sortarr(examplearr);
console.log(examplearr);

解析
两个循环
当i=0的时候，里面的循环完整执行，从j=0执行到j=6,这也就是第一遍排序，结果是将最大的数排到了最后，这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]
当i=1的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是j<arr.length-1-i的巧妙之处，结果是[8,15,55,76,21,39,88,94]
说到这里，规律就清楚了，每次将剩下数组里面最大的一个数排到最后面，当第一个循环执行到最后的时候，也就是i=6,此时，j=0,只需要比较数组的第一和第二项，比较完毕，返回。

以下为引用示例
5.不需要借助第三个临时变量，实现两个变量的交换

function swap（a,b）{
    b=b-a;
    a=a+b;
    b=a-b;
    return [a,b];
}

6.斐波那契数列

function getFib(n){
   let fibairr =[];
   let  i=0;
   while(i<n) {
     if (i<=1){
       fibarr.push(i);
      } else{
     fibarr.push(fibarr[i-1])
    } 
    i++;
  }
  return fibarr;
}

7.找出下列正整数组的最大差值
输入的数组是[10,5,11,7,8,9]
输出 6

function getMaxPro(arr){
    let minPrice=arr[0];
    let maxProfit=0;
    for (let i=0;i<arr.length;i++){
       let currentPrice=arr[i];
       minPrice=Math.min(minPrice,currentPrice);
       let potentialProfit =currenrPrice-minPrice;
       maxProfit=Math.max(maxProfit,potentialProfit);
     }
     return maxProfit;  
   }

8.随机生成指定长度的字符串
比如指定的长度为8

function random(n){
   let str='abcdefghijkmnopqrstuvwxyz9876543210';
   let tmp='',
       i=0,
       l=str.length;
  for(i=0;i<n;i++){
    tmp +=str.charAt(Math.floor(Math.random()*l))
   }
   return tmp;
}

更多示例