数据结构和算法

时间复杂度

用大写 O 表示，定性描述算法运行的时间，有O(1),O(n),O(logN),O(n^2)

空间复杂度

用大写 O 表示，算法运行过程中临时占用的内存的度量有O(1),O(n),O(logN),O(n^2)

数据结构

栈

特点： 有序的数据结构，先进后出

1. 栈应用场景

• 十进制转二进制
• 函数调用栈
• 可以用 Array.push pop 方法模拟栈

2. leetcode

• 20.有效的括号
• 144.二叉树的前序遍历 val left right

队列

特点：有序的数据结构，先进先出

1. 队列场景

• js 异步中的任务队列，为什么引入任务队列

2. leetcode

• 933.计算最近请求次数

链表

特点： 有序的数据结构，元素存储不连续，用 next 指针连在一起

1. 场景

• 原型链， 对象的__proto__相当于一个 next 指针，指向构造函数的 prototype
• 使用链表指针获取 JSON 节点值

2. 和数组的区别

• 数组：增删非首尾元素需要移动元素
• 链表：增删非首尾，只需改 next 指向

3. leetcode

• 237.删除链表中的节点 - p.next = p.next.next
• 206.反转链表 - 反转两个节点 n->n+1 n+1 -> n
• 2.两数相加 -
• 83.删除排序链表中的重复元素

集合

特点： 无序且唯一的数据结构

1. 和栈、链表、队列区别

• 集合不可以重复

2. 应用场景

• ES6 中的集合 Set
• 可求交集等

字典

特点： 与集合类似，存储唯一值的键值对形式数据结构

1. 应用场景

• ES6 中的字段 Map

2. leetcode

• 1. 两数之和

树

特点： 分层数据抽象模型，js 没有树，用 Object 和 Array 构建树

• 深度优先遍历
  • 反问根节点
  • 对根节点的 children 挨个深度遍历
• 广度优先遍历
  • 用队列解决
  • 创建一个队列，根节点入队
  • 将根节点出队将 children 入队
  • 重复队头出队，children 入队

1. 应用场景

• DOM、级联选择等
• 二叉树（每个节点最多只能有两个节点）递归
  • 先序遍历 访问顺序 根->left->right
  • 中序遍历 访问顺序 left->根->right
  • 后序遍历 访问顺序 left->right->根
• 二叉树（每个节点最多只能有两个节点）非递归
  • 先序遍历 用栈
  • 中序遍历 用栈
  • 后序遍历 用栈

2. leetcode

• 104.二叉树的最大深度 - 深度优先
• 111.二叉树的最小深度 - 广度优先
• 102.二叉树的层序遍历 - 广度优先

图

特点： 网络结构抽象模型，由边链接的节点， js 没有图，可用 Object 和 Array 构建图，图的表示法：邻接矩阵、邻接表

1. 应用场景

• 道路、航班等路径

堆

特点： 特殊的完全二叉树，所有节点都大于等于（最大堆），或小于等于子（最小堆）节点

• js 通常用数组表示堆
• 左侧子节点位置是 2 * index + 1
• 右侧子节点位置是 2 * index + 2
• 父节点位置 (index - 1 ) / 2 的熵

算法设计思想

分治

特点： 将问题分为多个和原问题相似的小问题，递归解决小问题，再合并

1. leetcode

• 374.猜数字大小

动态规划

特点： 将问题分解为相互重叠的子问题，反复求解子问题

1. 场景

• 斐波那契数列问题

2. leetcode

• 70.爬楼梯

贪心

特点： 期盼通过每个阶段的局部最优选择，达到全局最优，结果不一定是最优

1. leetcode

• 455.分饼干

回溯

特点： 渐进式寻找并构建问题解决方式策略，选一个可能的动作开始，如果不行回溯再选另一个可能的动作开始，直到问题解决

1. 场景

• 全排列 (leetcode 46)

排序及搜索算法

冒泡

快速

插入

归并

选择

二分搜索