ARTS挑战第十五周

Algorithm

    1. 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

《抗压力–久世浩司》失败的分类以及处理方法

ARTS挑战第十五周

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 "圖包含負權重的回路"

ARTS挑战第十五周

迪杰斯特拉时间复杂度: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[]

内部网关路由协议

ARTS挑战第十五周

Tips

  1. gitmind.com 开始收费,但是gitmind.cn 不收费
  2. 屏幕的高度以及良好的坐姿真的很重要,特别是程序员
  3. 跑步的步频很重要,前期一直是160的步频,并且步幅比较大,这样很伤膝盖,也废腿
  4. 没事多看看力扣和牛客网的面经,就知道自己有多菜,瞬间动力满满

Share

上一篇:ARTS打卡第六周(2021.2.10)


下一篇:ARTS -开篇词