狗家VO超详细过经11/19 +follow up 附上详细timeline 求大米！！

月黑风高 发表于 2021-12-14 15:33
请问用trie做的时间复杂度是什么？
正常思路就是其久而的解法二吗？用hashmap?

时间复杂度是 O(build trie(word数量*word长度)+dfs(2^input length))）

seabiscuit119 发表于 2021-12-14 15:53
第三题为啥bobas不输出呢？ 如果是sequence match的话也满足啊

最早的output是说match的第一个word，boba是match的第一个word就直接return了

yuyuyu0905 发表于 2021-12-14 20:59
第一题面试官应该想要的答案是扫描线。

简写一下名字，面试官的思路是：

确实是！ 非常感谢思路，这题总算弄懂了

感谢楼主分享。想问下DP那题follow up 能说一下思路吗 。想了好久不知道怎么搞状态方程

月黑风高 发表于 2021-12-15 07:33
请问用trie做的时间复杂度是什么？
正常思路就是其久而的解法二吗？用hashmap?

第一思路也是起九儿

匿名者 发表于 2021-12-16 00:32
第一思路也是起九儿

起九儿 试着用 dfs+Trie 的方法做了一下，会超时诶。2^N 的时间复杂度还是太高了。

zhang123587 发表于 2021-12-17 11:59
起九儿 试着用 dfs+Trie 的方法做了一下，会超时诶。2^N 的时间复杂度还是太高了。

hashmap 的思路不会有问题啊
感觉dfs+trie有点复杂了

感谢楼主分享
请问Dp那道是什么意思啊
先是一道简单的一维dp，一个游戏，每种move，需要turns，可以打出damage，最多x轮能打出的伤害
moves[[1,1][2,3][3,4][7,10]], turns 10  [turns, damage] Output: max damage you can get
是moves0 需要1 turn 可以打出1 damage
是moves1 需要2 turn 可以打出3 damage
是moves2 需要3 turn 可以打出4 damage
是moves3 需要7 turn 可以打出10 damage
然后要求只能turn 10次的画可以打出的最大damange吗 这里是14？

yulisa1 发表于 2021-12-22 15:25
感谢楼主分享
请问Dp那道是什么意思啊
先是一道简单的一维dp，一个游戏，每种move，需要turns，可以打出d ...

是的 就是这个意思！

太强了，所以楼主是今年9月入学的，明年暑假毕业入职NG吗？