LeetCode 全系列速通 (五)

Рет қаралды 3,169

Күн бұрын

Пікірлер: 26

@yuzhin4426 Жыл бұрын

知识点 trie + heap + union find trie 知识点: kzbin.info/www/bejne/jKLCeoyngraierc template: kzbin.info/www/bejne/jKLCeoyngraierc word search II: kzbin.info/www/bejne/jKLCeoyngraierc design in-memory file system: kzbin.info/www/bejne/jKLCeoyngraierc heap 知识点: kzbin.info/www/bejne/jKLCeoyngraierc heapify from Lintcode: kzbin.info/www/bejne/jKLCeoyngraierc union find 知识点: kzbin.info/www/bejne/jKLCeoyngraierc account merge: kzbin.info/www/bejne/jKLCeoyngraierc

@qq_cat 2 жыл бұрын

感谢视频分享。讲的很好。Word Search II 用第一个“板子”慢的原因是第一个“板子”对于每个单词里面的每个字母，都需要call trie.startsWith 和 trie. search, 两个的时间复杂度都是O(m), m 是word当前长度，走完word的所有字母总时间复杂度就是O(m^2) 了。而第二个“板子“把TrieNode 传到了每一层，所以总时间复杂度是O(m)

@古城算法 2 жыл бұрын

感谢提示，非常赞👍🏻

@watwatwatwat 5 ай бұрын

好像说反了，应该是第一个板子是把TrieNode传到每一层DFS里，第二个板子是每个字母分别用startswith和search去搜索当前所有的前缀(str + board[x][y])，做了大量重复操作；其实如果想用类方法的话，可以把子节点TrieNode传下去，然后在下一层里对子节点用starswith接口查单个字母就行了

@frederickbarbarossa2746 Жыл бұрын

13:16 line14为何在line15-18之前而不是之后呢拿到p点检查完这个点是否contains一个完整单词才move p to its child

@frederickbarbarossa2746 Жыл бұрын

我自己来解答一下：trie node的特点就是 node自己存储什么字母是由它是它parent的哪个child来决定的所以dfs传入的是个parent节点通过p children来知道其子节点存储了哪个char，故而需要先p = p childern来到下一层去考察下一层是否存有完整的词

@frederickbarbarossa2746 Жыл бұрын

整个trie结构有三种节点：1 root 就是自己不代表任何字母也不可能是完整的词如果不认为空字符串是个词 2 普通的中间节点是通过它在parent节点是array里边哪个child来表达自己存储了什么char 所以这种节点是通过其parent内存的信息表达自己是哪个字母的而自己存的唯一关于自己的信息是自己是否是词的末字母 3 trie的业界点，它没有children 也就是其children array都是null 而叶节点一定是存了完整的词

@linyuan436 2 жыл бұрын

这个讲的特别好

@古城算法 2 жыл бұрын

感谢支持！

@linyuan436 2 жыл бұрын

@@古城算法请问啥时候出ood呀非常非常期待

@古城算法 2 жыл бұрын

@@linyuan436 哈哈，先让我休息休息缓缓，1月底看看

@frederickbarbarossa2746 Жыл бұрын

31:10 trie如果删除一个word难道只是去删除boolean的flag吗不需要删除整个路径吗但是如果删除整个路径说不定路径上其他节点是别的word共享的我觉得至少分两种情况讨论 1 删除的word对应叶节点，则可以把叶节点flag标记为false 同时到此叶节点的parent node的children array标记相应的cell为null 但是回溯的parent也挺麻烦 2 如果是中间节点则只能改flag为false