阅后即焚电面面筋

倒序浏览 · 2023-7-1 07:04:51

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

比较常规的流程

题目：给一个

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

时候，之前输入的内容会被积累，需要看当前的string在不在字典里

先写了O(n^2）的答案，然后讨论优化

金元宝儿

这种题trie都不是thread safe的，一旦有followup允许concurrent modification就gg了，concurrentskiplistset::subset在实际使用中更安全，空间更省。更快的是直接prefix hashmap。trie是只存在在课本里的东西

匿名用户-HTDFE *2023-7-1 13:37:42* · 2023-7-1 13:37:42

leetForMoney 发表于 2023-6-30 22:06
为什么-> find('e')返回True
是不是因为是最后一个？这玩意是不是要用trie啊

c + o + d + e = code

prefix tree, lc 原题

leetForMoney

为什么-> find('e')返回True
是不是因为是最后一个？这玩意是不是要用trie啊

匿名用户-KTICA *2023-7-2 01:48:48* · 2023-7-2 01:48:48

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

金元宝儿

匿名用户发表于 2023-07-01 10:48:48
prefixMap会不会是空间不优
我觉得我最近面试失败就是空间不优，没有用trie

讲道理skiplistset空间最优，trie每个词都有一堆中间node，每个node基本两个reference跑不了，读写还得lock。

匿名用户-KTICA *2023-7-2 02:41:27* · 2023-7-2 02:41:27

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

来自APP · 2023-7-2 09:15:43

匿名用户发表于 2023-07-01 11:41:27
你说的这个Node， reference，都是同一个量级的
不会改变空间复杂度

现在面试真的运气成分很大，有时候做出来了最优解也不一定能过，有时候没做出最优解反而过了

匿名用户-FOYLQ *2023-7-10 10:25:16* · 2023-7-10 10:25:16

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-UZMRM *2023-9-8 14:08:26* · 2023-9-8 14:08:26

这题不就是明显用trie吗？