Google电话面试

rual 发表于 2017-2-4 10:15
我事后想了一下，就是walls and gates 那个leetcode题，变了一种说法而已。主要就是把那个dfs前后左右移 ...

好的感谢LZ

trie树算是空间换时间了，题目的要求是尽可能用更小的空间存储吧。

应该就是这个题目187. Repeated DNA Sequences
没办法用一个Integer表示一个，因为数字0-9将会用掉5个bit, 5乘以9就是45个bit. 只能用Long表示，
一个有10^9个ssn，每一个ssn一个long, 就是8byte,一起就是8 * 10 ^ 9 byte. 就是10g
用trie:
最多要9层。 每一个数字4个byte。一起 (10^9 + 10^8 + 10^7+10^6.. + 10^1)，也就是10^9，所以其实一样的空间
用trie和long表示都是一样的好