Skip to content

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

Description

@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用的还不是很顺。。

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions