javascript 算法 珠峰面试学习

数组排序

1.ES5

ary.sort((a,b)=>(a-b));

2.冒泡排序

冒泡排序

原则：
2-1.比较arr.length-1轮，没循环一轮，将当前数组的最大值，移动到最右侧
2-2.每轮比较原则，前后比较，不包含最后一个，不包含上一轮的中最右侧的最大值

var arr = [1,3,32,5,1,2,3,4];
for(var i=0; i<arr.length-1; i++){
    for(var j=0; j<arr.length-i-1; j++){
        if(arr[j]>arr[j+1]){
            var temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}
console.log(arr);

3.快速排序
递归找中间项，比较左右拼接数组

var arr = [1,3,32,5,1,2,3,4];
function quick(arr){
    if(arr.length<=1){return arr;}
    var mid = Math.floor(arr.length/2);
    var midVal = arr.splice(mid,1)[0];
    var left = [],
        right = [];
    for(var i=0; i<arr.length; i++){
        if(arr[i]<=midVal){
            left.push(arr[i])
        }else{
            right.push(arr[i]);
        }
    }   
    return quick(left).concat([midVal],quick(right));
};
console.log(quick(arr));

4.插入排序
类似抽扑克牌，每次从牌库中，抽一张，与手里的牌比对，排序，直到牌库全抽完

var arr = [1,3,32,5,1,2,3,4];
var resArr = [];
function insertSort(arr){
    if(arr.length<1){ return;}
    var rNum = arr.splice(0,1)[0];
    if(resArr.length<1){
        resArr.push(rNum);
    }else{
        var maxI = 0;
        for(var i=0; i<resArr.length; i++){
            if(rNum>resArr[i]){
                maxI=i+1;
            }
        };
        resArr.splice(maxI,0,rNum); 
    }
    insertSort(arr);
}
insertSort(arr);
console.log(resArr);

数组去重

1.ES6 new Set();

var resArr = Array.from(new Set([1,5,1,2]));
var resArr = [...new Set([1,5,1,2])];

2.对象Key值法

var arr = [1,2,5,2];
var obj = {};
var resArr = [];

for(var i=0; i<arr.length; i++){
    var _key = arr[i];
    if(!obj[_key]){
        obj[_key] = _key;
        resArr.push(_key);
    }
};

3.前后比对法 （涉及知识点，数组塌陷：操作数组时候，改变长度，而发生索引跳过某项数据的情况）

var ary = [1,5,4,12,1,5,3,7,8,12];
for(var i=0; i<ary.length-1; i++){
   var numNow = ary[i];
   var cmpArr = ary.slice(i+1);
   if(cmpArr.indexOf(numNow)!=-1){
      ary[i] = ary[ary.length-1];
      ary.length--;
      i--;
   }
};
console.log(ary);

var arr = [1,3,32,5,1,2,3,4];
for(var i=0; i<arr.length-1; i++){
    var iNow = arr[i];
    var leaveArr = arr.slice(i+1);
    if(leaveArr.indexOf(iNow)!=-1){
        arr.splice(i,1);
        i--
    }
}
console.log(arr);   

4.先排序，再前后比较法

var arr = [1,3,32,5,1,2,3,4];
var resArr = [];
arr.sort((a,b)=>{return a-b}).forEach((item,index)=>{
    if(item == arr[index+1] && typeof arr[index+1] != 'undefined'){
    }else{
        resArr.push(item);  
    }
});
console.log(resArr);

数组扁平化

1.ES6

arr.flat(Infinity);

2.字符串方式

arr.toString().split(',').map(val=>Number(val));
JSON.stringify([1,2,[3,4,[5,6]]]).replace(/(\[|\])/g,'').split(',').map(val=>Number(val));

3.通过some方法以及展开运算符来实现

var arr = [1,2,[5,2,[12,41]]];
while(arr.some(item=>{return Array.isArray(item)})){
    arr = [].concat(...arr);
};
console.log(arr);

斐波那契数列

又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”
1,1,2,3,5....
前两项为1，从第三项开始，后面面每一项的值都等于前面相邻两个值的和

//斐波那契数列
function fibonacci(n){
    if(n<=1){return 1;}
    var arr = [1,1];
    var addLth = n+1-2;
    while(addLth>0){
        var a = arr[arr.length-2];
        var b = arr[arr.length-1];
        arr.push(a+b);
        addLth--;
    }
    return arr[n];
}