DAY21 2026.05.10
LeetCode208 实现Trie（前缀树） [图论]
前缀树
初始化：
- 题目只包含26个小写字母，所以创建一颗26叉树，一开始只有一个根节点root
- 26叉树每个节点包含一个长为26的儿子节点列表child以及一个布尔值isEnd，isEnd表示该节点是否为终止节点
插入：
- 遍历字符串word，用curNode表示当前在树的哪个节点，初始值为root
- 如果word[i]不是curNode的儿子，则新建一个节点作为其儿子，连接下标位置为"word[i] - 'a'"
- 更新curNode为儿子列表中相应节点
- 遍历结束时，把curNode的isEnd标记为true，表示此处有一个单词已记录
查找：
- 遍历字符串word，用curNode表示当前在树的哪个节点，初始值为root
- 如果word[i]不是curNode的儿子，则没找到目标单词，直接返回false
- 如果word[i]是curNode的儿子，更新curNode为儿子列表中相应节点，往下遍历
- 遍历结束时，判断curNode的isEnd标记是否为true，如果为true则说明找到了目标单词，否则表示没匹配上
LeetCode215 数组中的第K个最大元素 [堆、快速选择排序]
方法一：小顶堆，时间复杂度O(nlogn)，使用优先队列实现小顶堆，维护队列大小最大为k个。当size大于k时，将队列中最小的（堆顶）弹出去。如此遍历完数组后，小顶堆peek即为数组中第K个最大元素
方法二：快速选择排序，时间复杂度O(n)，核心思路是第K大元素在升序数组的下标是n-k。
在nums中随机选择一个基准元素base，将小于base的元素放左边，大于等于base的元素放右边，这样划分后，base所处的位置就是最终在排序完毕后升序数组的位置
设base在nums中的下标为i。如果i=n-k，则找到答案；如果i>n-k，说明答案在base左侧部分，在其中继续寻找；如果i<n-k，说明答案在base右侧部分，在其中继续寻找
LeetCode347 前K个高频元素 [堆]
小顶堆，使用优先队列实现小顶堆，维护队列大小最大为k个
先用HashMap去重，统计数组中各元素的出现频次。然后实现用频次大小比较的优先队列，往里塞元素。当size大于k时，将队列中频次最小的元素（堆顶）弹出去。如此遍历完HashMap后，现有的小顶堆内元素即为前k个高频元素
LeetCode295 数据流的中位数 [堆]
大小顶堆。把一堆数均分成了left、right两部分，left里的数都比right的小，中位数就来自于left的最大值和right的最小值
随着addNum不断添加数字，要保证left里的数都比right的小，left和right的元素个数尽量相等，且总数为奇数个时，left比right多一个元素
left用大顶堆，right用小顶堆
如果当前left大小与right大小相等，添加的num先加到right里，再把right里最小的元素弹出，加到left里
如果当前left比right多一个元素，添加的num先加到left里，再把left中最大的元素弹出，加到right里
最后，如果当前总元素数为奇数，则中位数为left中最大元素（大顶堆peek）；如果当前总元素数为偶数，则中位数为left中最大元素（大顶堆peek）和right中最小元素（小顶堆peek）的平均数