Algorithm
-
- O(1) 时间插入、删除和获取随机元素](https://leetcode-cn.com/problems/insert-delete-getrandom-o1/) insert函数在数组尾部插入元素，使用hash表实现O(1)查找，remove函数使用hash查找，并交换与尾部元素交换后删除。
- 710. 黑名单中的随机数 sz表示除blacklist之外的元素个数，则需要把blacklist中在[0,sz) 区间的数，映射到[sz,N) 之间、且不是blacklist中的数，通过hash表记录映射关系。
Review
《抗压力–久世浩司》失败的分类以及处理方法
https://en.wikipedia.org/wiki/In_situ
在计算科学种，in situ 是一种不会打断系统正常状态的操作。例如数据库、操作系统的热备份，王者荣耀的热更新（不需要玩家退出游戏）。还有一个经常看到的概念就是in situ查询，就是直接在数据对象上进行查询，而不需要拷贝对象。
贝尔曼福特和迪杰斯特拉算法区别
https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95
贝尔曼福特时间复杂度：O(|V| |E|)
算法伪代码
procedure BellmanFord(list vertices, list edges, vertex source)
// 讀入邊和節點的列表並對distance和predecessor寫入最短路徑
// 初始化圖 O(|V|)
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// 對每一條邊重複操作 O(|V| |E|)
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// 檢查是否有負權重的回路 O(|E|)
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "圖包含負權重的回路"
迪杰斯特拉时间复杂度：O(|V|^2) ，dist使用数组实现；O(log|V|(|V|+|E|)) ，dist使用二叉堆实现。使用二叉堆实现时，二叉堆存储的是pair<顶点号, 距离>，表示dist[顶点号]=距离。
伪代码：
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph:
6 dist[v] ← INFINITY
7 prev[v] ← UNDEFINED
8 add v to Q
9 dist[source] ← 0
10
11 while Q is not empty:
12 u ← vertex in Q with min dist[u]
13
14 remove u from Q
15
16 for each neighbor v of u: // only v that are still in Q
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]:
19 dist[v] ← alt
20 prev[v] ← u
21
22 return dist[], prev[]
内部网关路由协议
Tips
- gitmind.com 开始收费，但是gitmind.cn 不收费
- 屏幕的高度以及良好的坐姿真的很重要，特别是程序员
- 跑步的步频很重要，前期一直是160的步频，并且步幅比较大，这样很伤膝盖，也废腿
- 没事多看看力扣和牛客网的面经，就知道自己有多菜，瞬间动力满满