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

[jianyuewu]

图

DFS做number of islands比较简单，但是union find写起来非常好理解。
uionfind要注意find可以路径压缩，union可以用rank来减少树的最大深度。

堆和排序

看到光头哥找到中位数的代码非常简短，震惊了。原来可以用负数来把CPP的大顶堆转为小顶堆，不用额外自己定义，这主意相当不错。
堆主要用于排序，找到第K大元素，中位数，99百分数等。配合散列表，可以统计某些场合的10大热门关键词等。但堆排序没有快排快，所以平时需要还是尽量快排，C语言用qsort()即可。

DFS

感觉DFS对树的遍历，图的遍历非常实用。
写起来有种顺滑的感觉。

BFS

queue按层遍历已经慢慢熟悉了，但是总感觉没有DFS清晰。
while循环前把第一个节点push到queue
->到while循环里拿到q.size()
->for循环开始遍历
->for循环里拿到q.front()，再q.pop()，处理当前元素
->下一层需要遍历的加到queue里去即可。
->再到下一个while循环去遍历，直到所有都遍历完。
visited树不需要，图需要，但图里visited用的还不是很顺。。

[Peng282]

图

DFS做number of islands比较简单，但是union find写起来非常好理解。
uionfind要注意find可以路径压缩，union可以用rank来减少树的最大深度。

堆和排序

看到光头哥找到中位数的代码非常简短，震惊了。原来可以用负数来把CPP的大顶堆转为小顶堆，不用额外自己定义，这主意相当不错。
堆主要用于排序，找到第K大元素，中位数，99百分数等。配合散列表，可以统计某些场合的10大热门关键词等。但堆排序没有快排快，所以平时需要还是尽量快排，C语言用qsort()即可。

DFS

感觉DFS对树的遍历，图的遍历非常实用。
写起来有种顺滑的感觉。

BFS

queue按层遍历已经慢慢熟悉了，但是总感觉没有DFS清晰。
while循环前把第一个节点push到queue
->到while循环里拿到q.size()
->for循环开始遍历
->for循环里拿到q.front()，再q.pop()，处理当前元素
->下一层需要遍历的加到queue里去即可。
->再到下一个while循环去遍历，直到所有都遍历完。
visited树不需要，图需要，但图里visited用的还不是很顺。。

BFS最重要的就是要先访问与当前节点所在的同层节点，然后访问其子节点。这里就很好的可以利用队列的这种数据结构，访问完了当前节点，再把子节点入队，因而同一层的节点都比下曾节点先入队。从而是出队的是一层一层的节点出队哈。