2019中高级前端秘籍之算法篇

2019中高级前端秘籍之CSS篇
 2019中高级前端秘籍之JavaScript篇
 2019中高级前端秘籍之浏览器篇
 2019中高级前端秘籍之服务端与网络篇
 2019中高级前端秘籍之算法篇

其实算法方面在前端的实际项目中涉及得并不多，但还是需要精通一些基础性的算法，一些公司还是会有这方面的需求和考核，建议大家还是需要稍微准备下，这属于加分题。

1. 五大算法

贪心算法: 局部最优解法
分治算法: 分成多个小模块，与原问题性质相同
动态规划: 每个状态都是过去历史的一个总结
回溯法: 发现原先选择不优时，退回重新选择
分支限界法

2. 基础排序算法

冒泡排序: 两两比较

    function bubleSort(arr) {
        var len = arr.length;
        for (let outer = len ; outer >= 2; outer--) {
            for(let inner = 0; inner <=outer - 1; inner++) {
                if(arr[inner] > arr[inner + 1]) {
                    [arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
                }
            }
        }
        return arr;
    }

选择排序: 遍历自身以后的元素，最小的元素跟自己调换位置

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

插入排序: 即将元素插入到已排序好的数组中

function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  //外循环从1开始，默认arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}

3. 高级排序算法

快速排序
- 选择基准值(base)，原数组长度减一(基准值)，使用 splice
- 循环原数组，小的放左边(left数组)，大的放右边(right数组);
- concat(left, base, right)
- 递归继续排序 left 与 right

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); 
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左边
        } else {
            right.push(arr[i]) //放在右边
        }
    }
    return quickSort(left).concat(current,quickSort(right));
}

希尔排序：不定步数的插入排序，插入排序
口诀: 插冒归基稳定，快选堆希不稳定

image.png

稳定性：同大小情况下是否可能会被交换位置, 虚拟dom的diff，不稳定性会导致重新渲染；

4. 递归运用(斐波那契数列)：爬楼梯问题

初始在第一级，到第一级有1种方法(s(1) = 1)，到第二级也只有一种方法(s(2) = 1)，第三级(s(3) = s(1) + s(2))

function cStairs(n) {
    if(n === 1 || n === 2) {
        return 1;
    } else {
        return cStairs(n-1) + cStairs(n-2)
    }
}

5. 数据树

二叉树: 最多只有两个子节点
- 完全二叉树
- 满二叉树
  - 深度为 h, 有 n 个节点，且满足 n = 2^h - 1
二叉查找树: 是一种特殊的二叉树，能有效地提高查找效率
- 小值在左，大值在右
- 节点 n 的所有左子树值小于 n，所有右子树值大于 n

image.png

遍历节点
- 前序遍历
  - 1. 根节点
  - 1. 访问左子节点，回到 1
  - 1. 访问右子节点，回到 1
- 中序遍历
  - 1. 先访问到最左的子节点
  - 1. 访问该节点的父节点
  - 1. 访问该父节点的右子节点，回到 1
- 后序遍历
  - 1. 先访问到最左的子节点
  - 1. 访问相邻的右节点
  - 1. 访问父节点，回到 1
插入与删除节点

6. 天平找次品

有n个硬币，其中1个为假币，假币重量较轻，你有一把天平，请问，至少需要称多少次能保证一定找到假币?

三等分算法:
- 1. 将硬币分成3组，随便取其中两组天平称量
  - 平衡，假币在未上称的一组，取其回到 1 继续循环
  - 不平衡，假币在天平上较轻的一组，取其回到 1 继续循环

作者：郭东东
链接：https://juejin.im/post/5c64d15d6fb9a049d37f9c20
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最后编辑于：2019.04.11 17:45:06