# 算法

数组去重
数组排序
数组扁平化
斐波那契数列
输出所有和N的连续正数序列
最大蓄水池问题
找零问题、背包问题、凸包问题

# 推荐学习

堆栈、队列、链表：https://juejin.im/entry/58759e79128fe1006b48cdfd (opens new window)
递归：https://segmentfault.com/a/1190000009857470 (opens new window)
波兰式和逆波兰式-理论：http://www.cnblogs.com/chenying99/p/3675876.html (opens new window)
波兰式和逆波兰式-源码：https://github.com/Tairraos/rpn.js/blob/master/rpn.js (opens new window)

# 什么是哈希表？

散列表（也叫哈希表），是根据关键码值直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

# 实例

# 数组去重

/*
 * 1. ES6：set
 * 2. 循环比较
 * 3. 对象键值对
 * 4. 比较相邻项 
 */
/* 第一种：ES6: SET */
const newArr = [...new Set(arr)]; // Array.from(new Set(arr))

/* 第二种：当前项与后面的内容比较 */
// 1. splice删除当前项，i--；splice会改变原数组，存在数组塌陷问题
// 2. 定义一个新数组newArr = [...arr]，删除新数组newArr.splice(i, 1);
// 3. 定义一个空数组，i<arr.length，将不包含的push进去
// 4. 将当前项置为null，最后再把null删掉，arr[i]=null，arr = arr.filter(item => item !== null)
// 5. 将最后一项替换当前项arr[i]=arr[arr.length-1]，删除最后一项arr.length--，还从当强项循环比较i--；
let newArr = [...arr]; // 浅克隆，但每个数组都是一个堆，性能不好
for(let i=0;i<arr.length-1;i++){
    let item = arr[i],
        args = arr.slice(i + 1); // 除当前项的剩余所有项
    if(args,indexOf(item) > -1){ // 判断在剩余所有项中是否有当前项，// ES6: includes
        // 删除当前项
        /* arr.splice(i, 1); 
        i--;*/
        // newArr.splice(i, 1);
        // arr[i] = null
        arr[i]=arr[arr.length-1];
        arr.length--;
        i--;
    }else{
        // newArr.push(item);
    }
}
// arr = arr.filter(item => item !== null)

/* 第三种：对象键值对 */
let obj = {};
for(let i =0;i<arr.length;i++){
    let item = arr[i];
    if(typeof obj[item]){
        arr[i]=arr[arr.length-1];
        arr.length--;
        i--;
        continue;
    }
    obj[item] = item;
}
obj = null; // 最后销毁obj这个堆

/* 第四种：先排序，比较相邻项（基于正则） */
arr.sort((a, b) => a-b);
arr = arr.join('@') + '@'; // 每个数字后面加上'@'，10@10@10@10@10@
let reg = /(\d+@)\1*/g,
 arr = [];
arr.replace(reg, (n, m) => { // m：不重复的10@
 // arr.push(Number(m.slice(0, m.length-1)));
    arr.push(parseFloat(m)); // 可以直接拿到字符串中的数字部分
})

# 数组排序

快速排序：https://segmentfault.com/a/1190000009426421 (opens new window)
选择排序：https://segmentfault.com/a/1190000009366805 (opens new window)
希尔排序：https://segmentfault.com/a/1190000009461832 (opens new window)

冒泡排序：两两比较，将小的放前面，共比较arr.length-1轮，大的放后面，每一轮当前项和后一项比较，当前数组中最大的放到末尾

function bubble(arr) {
    let temp = null;
    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]){
              temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
             }
     }
    }
    return arr;
}

插入排序：

function insert(arr){
    let handle = [];
    handle.push(arr[0]);
    for(let i=0;i<arr.length;i++){
        let A = arr[i];
        for(let j=handle.length -1;j>=0;j--){
            let B = handle[j];
            if(A > B){
                handle.splice(j+1, 0, A);
                break;
            }
            if(j === 0){
              handle.unshift(A);  
             }
        }
    }
}

快速排序 - 二分法，性能最好

取中间值，分为左小右大两个数组，递归，再左右拼接

function quick(arr){
    if(arr.length <= 1) return arr;
    // 1. 找到数组的中间项，在原有的数组中把它移除
    let middleIndex = Math.floor(arr.length/2);
    let middleValue = arr.splice(middleIndex, 1)[0];
    // 2. 准备左右两个数组，循环剩下数组中的每一项，比当前项小的放到左数组中，大的放右数组中
    let leftArr = [],
        rightArr = [];
    for(let i=0;i<arr.length;i++){
        let item = arr[i];
        item < middleValue ? leftArr.push(item) : rightArr.push(item);
    }
    // 3. 递归左右数组，直到全部排完序，再将左+中+右拼接成最后的结果
    return quick(leftArr).concat(middleValue, quick(rightArr));
}

# 数组扁平化

多维数组降成一维数组

var arr = [1, [2, [3, [4, [5]]]]]
/* 第一种：ES6 */
arr = arr.flat(arr);

/* 第二种：转换为字符串 */
arr = aa.toString().split(',').map(item => Number(item));
arr = JSON.stringify(arr).replace(/(\[|\]\)/g, '').split(',').map(item => Number(item));

/* 第三种：基于数组的some方法：循环验证是否为数组 */
while (arr.some(item => Array.isArray(item))){
    arr = [].concat(...arr); // 降一维
}

/* 第四种：递归 */
function myFlat(arr){
    let result = [];
    function fn(newArr){
        for(let i=0;i<newArr.length;i++){
            let item = newArr[i];
            if(Array.isArray(item)){
               fn(item);
                continue;
            }
            result.push(item);
        }
    }
    fn(arr);
    return result;
}

# * 斐波那契数列（阿里）

斐波那契额数列为：[1, 1, 2, 3, 5, 8, 13, 21, ...]。当index > 1时，当前项是前两项之和

function fibonacci(n) {
    function fn(n, cur = 1, next = 1){
        if(n == 0) return cur;
        return fn(n-1, next, cur + next);
    }
    return fn(n);
}
function fibonacci1(n) {
    if(n <= 1) return 1;
    let arr = [1, 1];
    let i = n + 1 -2; // 即将要创建多少个
    white(i>0){
        let a = arr[arr.length -2];
         b = arr[arr.length -1];
        arr.push(a + b);
        i--;
    }
    return arr[arr.length -1];
}

# 输出所有和是N的连续正数序列（头条）

例如：输入15，返回[[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]]

// 从N开始计算连续M个的正数序列和 - 等差数列求和（(首+尾)*个数/2）
function fn(n){
    let result = [];
    let middle = Math.ceil(n/2); // 只有小于当前值的累加，才可能等于当前值
    for(let i=0; i<middle;i++){ // 从1开始累加
        for(let j=2;;j++){ // 累加多少次
            let total = (i+(i+j-1)*j/2; // 累加和
            if(total > n) {
                break;
            }else if(total === n){
                result.push(createArr(i, j));
                break; 
            }
        }
    }
    return result;
}
function createArr(n, len){
    let arr = new Array(len).fill(null),
        temp = [];
    arr[0] = n;
    arr = arr.map((item, index) => {
        if(item === null) {
            item = temp[index-1] + 1;
        }
        temp.push(item);
        return item;
    })
    return arr;
}

# 最大蓄水池问题

← 计算机基础数组相关 →