狗狗家挂经

难道不是反着加成Trie？

另外请教楼主面经题，棋盘放旗子是什么题？能否说的详细一点？

mrzhu 发表于 2019-1-2 06:37
是啊，看着简单的题往往不好做

第一题 应该用 rolling hash，hash1 从第一个str的尾巴开始 hash2 从第二个str的 头开始。碰到hash1==hash2 的时候 做一个实际的compare确认， 可以linear time， 这个算法写起来和理解起来都比KMP简单很多.        楼主能详细说一下围棋题目吗 。

a62253162 发表于 2019-1-2 11:17
第一题 应该用 rolling hash，hash1 从第一个str的尾巴开始 hash2 从第二个str的 头开始。碰到hash1==has ...

如何快速（利用已有的str的hash值）计算新str的hash也是挺难记的。否则每个str都重新计算的话，跟brute force相比，时间上优势可能并不大？

yxsh01 发表于 2019-1-2 06:47
第一题用类似kmp的方法做？

kmp怎么做？复杂度多少

关于第一问有点疑问，是一共只给两个str？

yiliaobailiao 发表于 2019-1-2 11:52
关于第一问有点疑问，是一共只给两个str？

其实我也想这么问。如果是这样还搞那么复杂干啥...

yiliaobailiao 发表于 2019-1-2 11:52
关于第一问有点疑问，是一共只给两个str？

如果我没记错应该是的

14417335 发表于 2019-1-2 10:42
另外请教楼主面经题，棋盘放旗子是什么题？能否说的详细一点？

这个就是那个常见的面经题，每一列其中的棋子不能重复，每一列都有自己的range所以row之间肯定是不会重复的。一般的解法就是每一列循环用set

leetcod_ 发表于 2019-1-2 09:17
第五轮等价于：我们去掉一个门，可以通过 吧？

不好意思我题说的不是很清楚，每一个点的门可以朝四个方向开，问改变哪一个门的方向可以通过

补充内容 (2019-1-2 12:15):
就是可以开一个门或者关一个门，如果让他过去的话应该是开一个门