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

Activity

1. Peng282 commented on Jun 23, 2019

   

   Peng282

   on Jun 23, 2019

   Last edited by Peng282

   More actions

   图

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