学习算法 2019-09-01 10:22 folder Algorithms label 算法, Algorithms

回想起大学时，学习 C 语言，参加 ACM 竞赛。其实那时候的我对编程就是感兴趣的，当然源于高中学习 Visual Basic 也是一样的，充满了乐趣。这个月我选择学习算法，通过力扣开始我的初学（重回）算法之路。

当初离开算法之路的原因也是因为自认为高等数学没有学好导致的，那么毕业也就没有直接参加开发相关的工作，而是进入银行。

算法，重在解题思路、勤练、融会贯通，那么在我的前端工程师之路上，我也会尽我所能的掌握起来。

算法基本概念介绍

算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

时间复杂度

认识大O符号Big O notation

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模 的函数 ，算法的时间复杂度也因此记做

算法执行时间的增长率与 的增长率正相关，称作渐近时间复杂度，简称时间复杂度。

常见时间复杂度

我整理了一些常见的时间复杂度依次从小到大排序：

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

关于最优解

关于最优解的概念我通过 Google 并没有搜到一个比较合适的答案，但是我理解的最优解就是保证时间复杂度最小的情况下，寻求空间复杂度最小，这才是最优解，并且没有绝对最优解，只有相对最优解。

比较器

算法比较器用于检测你写的算法是否正确，他的优点是比测试用例更接近正确，前提建立在这个比较器是“正确”的。毕竟测试用例的数量是有限的，没有被穷举的。比较器最不容易出错的解法就是暴力解法，最为直接，最为致命。当然你在做算法题的时候，能用暴力解法做出来的题，你的时间复杂度肯定很糟糕，记得避开这一点。

支配理论（英语：master theorem）

在算法分析中，支配理论（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递回关系式的方法。这种方法最初由Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出，在那里被描述为解决这种递回的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen，Leiserson，Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。

排序算法

稳定的排序

• 冒泡排序
• 插入排序
• 归并排序
• 桶排序
• 基数排序

不稳定的排序

• 选择排序
• 随机数快速排序
• 堆排序

字符串算法

• 最长回文子串Manacher算法
• 克努斯-莫里斯-普拉特算法KMP算法

BFPTR算法

这里介绍一个比较好的算法，叫做BFPTR算法，又称为中位数的中位数算法，它的最坏时间复杂度为 ，它是由Blum、Floyd、Pratt、Rivest、Tarjan提出。该算法的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。

• BFPRT算法原理
• BFPRT 算法（TOP-K 问题）

搜索算法

• 广度优先搜索BFS
• 深度优先搜索DFS

图算法

• 拓扑排序
• 克鲁斯克尔算法Kruskal算法
• 普里姆算法Prim算法
• 戴克斯特拉算法Dijkstra算法

数据结构

• 二叉树
  • 树的遍历
  • 二叉树前(先)序、中序、后序遍历
  • 思考折纸问题：折纸问题与二叉树，[编程题]折纸问题 - 牛客网
• 并查集
• 布隆过滤器
• 一致哈希
• 散列函数哈希函数
• 散列表哈希表
• 前缀树Trie
  • 思考如何生成前缀树
• 邻接表
• 邻接矩阵
  • 思考如何表达图
  • 思考如何生成图
• 数组
  • 思考如何用数组结构实现队列和栈
• 队列
  • 思考如何用队列实现栈
  • 思考如何实现猫狗队列 - Google 搜索 猫狗队列
• 堆栈栈
  • 思考如何用栈实现队列
  • 思考如何实现一个特殊栈，提供获得栈中最小元素的方法
  • 思考如何实现随时找到数据流的中位数：[剑指offer] 数据流中的中位数
• 链表
  • 思考如何打印两个有序链表的公共部分
  • 判断一个链表是否为回文结构
  • 思考如何将单向链表按某值划分成左边小、中间相等、右边大的形式
  • 思考如何复制含有随机指针节点的链表
  • 思考两个单链表相交的一系列问题
  • 思考如何反转单向和双向链表

线性代数

• 矩阵
  • 思考如何实现转圈打印矩阵
  • 思考如何“之”字形打印矩阵
  • 思考如何在行列都排好序的矩阵中找数

不得不感叹，数学家和科学家的厉害之处，我也加油咯！多刷题。

附：我的力扣主页，以放置在博客底部外链栏。

面试资深前端工程师总结

本着面试也是一种学习的过程，当然进入面试需要精心准备简历，准备简历的时候能把自己看的“相对”比较的透彻，在这2年里自己掌握了什么，经历了什么，用精炼的语句把她们写在我的简历中。而且每次写简历都会发现，对自己以前写的简历不怎么满意，这一次的简历是更上一层楼的版本，我相信这也是一个进步的过程。

那么最后通过面试来真正的认识自己的能力，找到自己想要的方向。千万记住别沉浸在自己公司安逸的环境中，这样找突破点会有些困难，试着跳出这个环境来看看，外面的世界是如何的，越是安逸，越要逼着自己去看看外面。

回顾一下面试的问题：

• Webpack 热更新是如何实现的？
• 什么是 CORS ？有多少种方法可以实现？
• OPTION 请求是如何产生的？
• 如何自己实现一个 new ？
• 什么是原型链？
• 什么是 EVENT LOOP ？
• 介绍一下 box-sizing 属性？
• 什么是 BFC ？
• 什么是盒模型？
• 浏览器缓存机制有哪些？
• 有哪些首屏加载优化策略？
• 实现按需加载的方式有哪些？
• 什么是 React Fiber ？
• 什么是 React Hook ？
• React Diff 做了哪些优化？
• ……记不起来了

总之，经过面试，我也找到了自己的欠缺点，自己的弱项。对前端的基础知识点深度抓的还不够深、 CSS 方面基础和广度的欠缺，这是我首要需要解决的问题。当然了，按照我自己的计划继续努力即可，一天比一天强，加油。

React 源码阅读计划

截止 8 月底，从 ReactFiberBeginWork.js 穿插至 ReactDOMComponent.js 回到一些跟 0.3-stable 熟悉的位置。