算法与数据结构
2020-07-15 10:35:54 0 举报AI智能生成
简单的算法和数据结构的描述
作者其他创作
大纲/内容
并查集
站队问题
初始化
查询，合并
路径压缩
集合
Key不重复
映射
K/V键值对，Key不重复
队列
先进先出
栈
先进后出
链表
离散空间
查找慢，插入和删除结点快
数组
连续空间
查找快，插入和删除结点慢
复杂度
时间复杂度
子主题
子主题
子主题
子主题
子主题
O(1)常数复杂度，最佳，比如Hash表，缓存等
O(logn)仅次于常数复杂度，如二分查找，二叉搜索树等
O(n)线性复杂度，如大多数便利操作
O(n^2)双重for循环
O(2^n)递归的时间复杂度
空间复杂度
0(1)原地操作
O(n)开辟线性辅助空间
工具
Google搜索引擎
iTerm2+zsh最强终端体验
heyfocus.com
IDEA+Leetcode Plugin
LeetCode
LRU
HasTable+双向链表
get和set都是O(1)的复杂度
树
二叉树
遍历
DFS
BFS
二叉搜索树
平衡二叉树
AVL树
红黑树
剪枝
字典树
空间换时间
图
遍历时需要记录已经访问过的结点
递归，分治
盗梦空间
终止状态
本层处理
Drill Down
本层状态清理
二分查找
有序
有界
能够通过索引随机访问
贪心算法
判断能不能贪心
弱化版的动态规划
动态规划
简单版本是递归+缓存
高级版本是递推公式
状态的定义
有些场景需要套用模板
最优子结构
状态转移方程
位运算
需要记忆一些常见的位运算公司
布隆过滤器
判断不存在100%准确
判断存在有误差
利用hash函数将待判断Key对应到多个位上
0 条评论
下一页
