h*********o
发帖数: 230 | 1 今天G家店面。
找最长回文，给的不是字符串，一个很长很长的datastream（一个字符块，一个字符块
的传进来），内存放不下。
设计一个算法怎么来找最长的回文。
没想出来。。。 |
W***o
发帖数: 6519 | |
i******t
发帖数: 22541 | |
h*********o
发帖数: 230 | 4 不会吧，DP 用的空间不是更多。。。
【在 i******t 的大作中提到】
: 会不会是意思让你用dp啊
|
h*********o
发帖数: 230 | 5 这个我倒是没有提。。。
但这个数据量太大。。
他说内存只能存俩block
【在 W***o 的大作中提到】
: 写到盘上先？
|
m*****n
发帖数: 2152 | 6 google就会出这种狗屎一样的题。
丫应该告诉你，数据流可以过几遍，而不是一遍。
每过过一遍，压缩一次最大回文，直到不能压缩为止。
这种题根本不肯能现场15分钟写code编出来。 |
f****g
发帖数: 207 | |
c********t
发帖数: 5706 | 8 agree, O(1) space. 不过这种特定题的特殊算法，知道就应该可以，电面要求写出来
实在是过分
【在 f****g 的大作中提到】
: manacher's algo
|
n**********r
发帖数: 43 | 9 怎么可能O(1)呢？O(n)吧？求思路。
感觉还是要写硬盘？实现一个Stream的操作类，一次读取时直接pre process然后写到
硬盘，
之后指定Buffer Size把硬盘虚拟成内存用？面这种题是人已招满直接想据的意思吧。
【在 c********t 的大作中提到】
: agree, O(1) space. 不过这种特定题的特殊算法，知道就应该可以，电面要求写出来
: 实在是过分
|
c********t
发帖数: 5706 | 10 你说得对，是O(n)。必须写到disk了。
【在 n**********r 的大作中提到】
: 怎么可能O(1)呢？O(n)吧？求思路。
: 感觉还是要写硬盘？实现一个Stream的操作类，一次读取时直接pre process然后写到
: 硬盘，
: 之后指定Buffer Size把硬盘虚拟成内存用？面这种题是人已招满直接想据的意思吧。
|
