【010-week3】算法训练营第三周学习总结 #162

第三周学习内容：

第三周习题训练以下内容：

1. 图
2. 堆和排序
3. DFS
4. BFS

图

1. 定义

图的数学定义很复杂难懂，看老师讲义的图片更加直观。图的类型分为有向图和无向图，程序实现上图有多重表示法，但是leecode上一般使用邻接表方式比较多。

2. 做题实践

图的算法一般都和DFS和BFS分不开的。

1. leecode 200

根据老师上课内容，这道题可以使用沉没算法，通过DFS或者BFS将相连岛屿设置为0即可，还有一种方法是用并查集。但是代码实现还是写不出，要好好再复习复习。

2. leecode 210

我做这道题目，没有反应出来这是一道图的题目，看了题解才了解，有两种方法，
1.DFS 
2.拓扑排序，方法是BFS，但是顺序从最底层的节点往上遍历，这个方法一开始写有点不习惯。

堆和排序

1. 定义

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：
给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值

2. 作用

能在logN复杂度下获取一组可以动态扩容数据流的最小（最大）值。用于实现优先级队列。

3. 做题实践

1. leecode 703 

这道题的关键是数据流，如果是静态数组，我们可以直接使用分治法。但是因为数据是可以增加的，这个时候可以用堆简化时间复杂度。

2. leecode 295

这道题我还没有做，不过题目既然放到堆里，肯定是要用堆解决。我的思路是维护两个堆，一个大根堆，一个小根堆，只要维持两个堆数量相等，就能够很容易的获取中位数。

DFS

1. 代码模板

visited=set()
def dfs(node,visited):
  visited.add(node)
  #process currect node here
  process(node)
  for next_node in node.children:
    if not next_node in visited:
      dfs(next_node,visited)

2. 做题实践

DFS实现代码很简单，题目有时候看上去简单，但是在实现中没有看清题目可能会有错误的结果（比如：leecode 111）。DFS和BFS在一般情况下是通用的，DFS代码更简洁一点。

1. leecode 104 & leecode 111

这两道题目看似一样，但是 leecode 111，对于叶子节点的定义如果没有看清楚的话，最终会导致错误的结果。

2. leecode 127 

这道题目一开始使用DFS做，提交后超时了，后来使用BFS做成功了，看了题解也是BFS。这道题解的预处理很妙，可以将查询下一个单词的时间复杂度由O(N)改为O(1)。我一直觉得这块儿可以优化，但是没想出来，看题解后醍醐灌顶。

BFS

1. 代码模板

def BFS(graph,start,visited):
    queen=[]
    queen.append(start)
    while queen:
        node=queen.pop()
        visited.add(node)
        process(node)
        for next_node in node.children:
            if next_node not in visited:
            	queen.append(next_node)

2. 做题实践

DFS和BFS在一般情况下是通用的，所以在列题中有些题目是重复的，比如：leecode 529。同时我在刷题过程中还学到一些新的思路：

• 有些体况下，使用BFS是更优的解法，比起DFS时间复杂度更低更有效。
• 我们一般常见的BFS是从根节点向下遍历，在做题中发现，有些做法是从叶子结点，向上一层层的遍历。

1. leecode 310

这道题目就是从叶子节点向上使用BFS解法的一个典型题目，形式上和leecode 210的拓扑排序的解法很像，我尝试使用DFS，也能做出来并通过了提交，但是时间是BFS的30倍。

学习总结

最后总结一下这周的学习和刷题经历，这周的题目和知识点比起之前的更难了，一来这些数据结构和算法本身难度比较高，二来平时的开发中这些知识接触和使用也比较少。正在积极努力地通过实践覃超老师讲的刻意练习和五步做题法来弥补这方面的不足。