- 数据结构与算法
- 一、数据结构
- 1.1 BST、AVL、Red-Black BST
- 1.2 Trie 字典树、LRU Cache、布隆过滤器
- 1.3 Union-find 并查集
- 1.4 数组 Array List、链表 linkedList、跳表 SkipList
- 跳表 [Skip list](https://gitee.com/lf-ren/java-re-new-builder/blob/master/projects/pro03Algorithm/src/main/java/com/hef/stack/SkipList.java)
- 1.5 栈、队列、双端队列Deque、优先队列Priority Queue
- 1.6 哈希表 HashMap、集合 Set
- 1.7 树、二叉树
- 1.8 堆 Heap
- 1.9 图
- 二、算法
- 2.1 [动态规划](https://gitee.com/lf-ren/java-re-new-builder/blob/master/document/week3-%E7%AE%97%E6%B3%95%E3%80%81springBoot/2021-09-14-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md)
- 2.2 [双指针法](https://gitee.com/lf-ren/java-re-new-builder/blob/master/document/week3-%E7%AE%97%E6%B3%95%E3%80%81springBoot/2021-10-05-%E5%8F%8C%E6%8C%87%E9%92%88%E6%B3%95.md)
- 2.3 [HashMap相关题目](https://gitee.com/lf-ren/java-re-new-builder/blob/master/document/week3-%E7%AE%97%E6%B3%95%E3%80%81springBoot/2021-10-16-%E5%93%88%E5%B8%8Cmap%E7%9B%B8%E5%85%B3%E9%A2%98%E7%9B%AE.md)
- 2.4 用栈来解决：
- 2.5 用队列来解决
- 2.6 用堆来解决（PriorityQueue）
- 2.7 递归的算法题目
- 2.8 分治和回溯（递归的细分）
- 2.9 BFS和DFS
- 2.9.1 DFS 的代码模版
- 2.9.2 BFS 的代码模版
- 2.9.3 BFS和DFS相关题目
- 2.10 贪心算法
- 2.11 二分查找 和 [牛顿迭代法](https://www.beyond3d.com/content/articles/8/)
- 二分查找的特性：
- 代码模版
- 三、方法论
- 3.1 做题四步
- 3.2 最大的误区
- BST 二分搜索树
- AVL 平衡二分搜索树
- Red-Black BST 红黑二分搜索树
- Trie 字典树
- LRU Cache
- 布隆过滤器
- Union-Find 并查集
-
数组：随机查询的时间复杂度为O(1) ，插入、删除的时间复杂度为O(n)
-
链表：随机查询的时间复杂度为O(n)，插入、删除的时间复杂度为O(1)
跳表的实现，参考跳表(skiplist)分析设计与实现(Java)
-
跳表只能用于（链表里的）元素有序的情况。
-
跳表对标的是平衡树（AVL Tree）、二分查找，是一种插入、删除、搜索时间复杂度搜是O(logn)的数据结构。
跳表的使用案例：Redis、LevelDB
redis: 有序集合是如何存储的
1. 当有序集合中的节点数量小于128的时候，并且所有节点member的长度小于64 的时候使用ziplist； 2. 当有序集合不满足上面两个任意一个条件的时候，改为使用skiplist； (ziplist 是一个字节数组)
redis 如何解决：数据量小的时候没有体现出跳表的优势（会出现多层级）：
1. 节点数量小于128 的时候使用ziplist； 2. redis 跳表 最大层级 32 （）
redis 的对象类型有哪些？底层的数据结构（有序集合 hash）； 字符串、整数、hash dict、压缩列表、set、跳表、字符串、list、消息队列 zset的底层使用什么数据结构实现的
redis为啥使用跳表，而不使用红黑树？
1. 红黑树实现复杂，跳表实现简单； 2. zrange(0, -1) 和红黑树一样， 但 zrange(10, 100) 红黑树很难做到；
- 双指针的算法题目
栈 Stack： 先入后出；添加、删除皆为O(1)；
队列 Queue：先入先出：添加、删除皆为O(1);
补充：java种 stack、queue、priority queue 的源码分析
大顶堆 MinHeap、小顶堆、堆排序
1.6 哈希表 HashMap、集合 Set补充：HashMap的源码分析
- HashMap相关题目
-
树的遍历
前per-order、中in-order、后序post-order
-
二叉搜索树
-
树的遍历相关题目
- 可以迅速找到一堆数中的最大值或者最小值的数据结构：大顶堆（或大根堆）、小顶堆（或小根堆）
- 二叉堆是堆的一种实现方式：完全二叉树实现堆；
- 堆排序
- DFS、BFS：因为可能成环，所以一定要加visited
- 连通图的个数；
- 拓扑排序
- 最短路径
- 最小生成树
- 最近相关性、洋葱一样的结构
- 经典题目：括号匹配、直方图
（遇到用队列来解决栈、或用栈来解决队列，一般的思路为使用两个栈或两个队列）
- 栈相关算法题目
- 滑动窗口
- 滑动窗口(使用堆，没有队列方便)
堆相关题目
2.7 递归的算法题目递归代码模版
- 递归终止条件；
- 处理当前层
- 下探到下一层
- 恢复状态
经典题目：
- 递归算法题目
找重复性
- 分治和回溯的算法题目
visited = set()
def dfs(node):
visited.add(node)
# process current node here
# ... ...
for node in node.children():
if not node in visited:
dfs(node)
2.9.2 BFS 的代码模版
使用队列（FIFO）
def bfs(root):
queue = []
queue.append(root)
while queue:
node = queue.popleft()
process(node)
nodes = generate_retated_nodes(node)
queue.push(nodes)
2.9.3 BFS和DFS相关题目
- BFS和DFS相关题目
-
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利的选择），从而希望导致结果是全局最好或最优的算法。
-
贪心算法与动态规划不同的地方在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则可以保存之前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
-
贪心：当下做局部最优判断；
-
回溯：能够回退
-
动态规划：最优判断+回退
-
贪心算法相关题目
- 目标函数单调性（单调递增或递减）
- 存在上下界
- 能够进行索引访问
left, right = 0, len(array)-1
while right>=left:
mid = (left+right)/2;
if (array[mid]==target):
return mid
elif array[mid]>target:
right = mid-1;
else:
left = mid+1;
- 二分查找相关题目
- 确认题意（审题）；
- 思考所有可能的方案，并选择最佳方案；
- 编写代码；
- 测试；
题目只做一遍。
