v******a
发帖数: 54 | 1 一个char stream
byte b=read() 从网络接收数据
怎么判读stream是palindrome?
stream可能是很大，内存可能放不下 |
s*********t
发帖数: 1663 | 2 先存到硬盘上，读完了再判断
【在 v******a 的大作中提到】
: 一个char stream
: byte b=read() 从网络接收数据
: 怎么判读stream是palindrome?
: stream可能是很大，内存可能放不下
|
M********5
发帖数: 715 | 3 还没来得及仔细想，intuitive的想法是
先把所有的数据保存下来，保存到文件里面
然后，比如你的内存是nM的，取出文件的开头n/2 M和结尾的n/2 M
然后这样子一点一点的比较？ |
k*n
发帖数: 150 | 4 出题人的意思似乎是要随时判断？到当前这个byte为止是不是一个回文？
【在 M********5 的大作中提到】
: 还没来得及仔细想，intuitive的想法是
: 先把所有的数据保存下来，保存到文件里面
: 然后，比如你的内存是nM的，取出文件的开头n/2 M和结尾的n/2 M
: 然后这样子一点一点的比较？
|
v******a
发帖数: 54 | 5 yes
【在 k*n 的大作中提到】
: 出题人的意思似乎是要随时判断？到当前这个byte为止是不是一个回文？
|
M********5
发帖数: 715 | 6 那思想其实也是差不多得嘛。。。至少我这样子认为
反正如果接收的数据很大，就要先存到硬盘上去
如果说要随时判断，那么就分点内存用做算法，另外的内存继续读数据？ |
k*n
发帖数: 150 | 7 睡觉了，躺床上想去。。。
【在 M********5 的大作中提到】
: 那思想其实也是差不多得嘛。。。至少我这样子认为
: 反正如果接收的数据很大，就要先存到硬盘上去
: 如果说要随时判断，那么就分点内存用做算法，另外的内存继续读数据？
|
i***1
发帖数: 95 | 8 很有意思的题目。。。
我有个idea，如果一个串是palindrome，那么对它的hash，从头到尾，和从尾到头是一
样的。
譬如用这样的hash方法。
int hash(char a[], int n)
{
int res = 0;
for(int i=0;i
res = ((res*37)+(int)char[i])%3137;
}
在扫描的同时，保存另一个hash值。（和上面的hash方法要有点变化）
在此基础上，可以用bloom filter的方法，减少false positive的可能性。 |
g****n
发帖数: 431 | 9 从头到尾hash可以累积计算，但从尾到头需要重读一遍已经接受的数据。如果每接受一
个byte，都读一
遍整个数据，时间是n^2，而且题目说数据很大内存放不下，那么对这么大的数据n^2时
间可能太长了
【在 i***1 的大作中提到】
: 很有意思的题目。。。
: 我有个idea，如果一个串是palindrome，那么对它的hash，从头到尾，和从尾到头是一
: 样的。
: 譬如用这样的hash方法。
: int hash(char a[], int n)
: {
: int res = 0;
: for(int i=0;i: res = ((res*37)+(int)char[i])%3137;
: }
|
g****n
发帖数: 431 | 10 clarify一下题目：不断从网络接收一个stream，要求判断对于当前接受到的数据，是
否为回文，且当
前接受的数据很大，内存装不下。如果题目是这样：
判断回文至少要O(n)时间，遍历已有数据不能避免，那么可以想办法在必须遍历的时候
，才去遍历。可以
有2个条件：
1. 对于接受到的每个字符，用计数器记录出现的次数。回文的必要条件是所有字符的
个数都为偶数（可以有一个奇数）。
2. 开2个m大小的cache在内存中。第一个保存数据最开始的m个字符，第二个保存最后m
个字符（可以用
环形数组实现）。回文的必要条件是2个cache互为回文。
每接收到一个字符，如果上面2个条件满足，那么遍历整个已有数据，判断是否回文。
如果m开得比较大，
那么浪费的时间会非常小。
【在 v******a 的大作中提到】
: 一个char stream
: byte b=read() 从网络接收数据
: 怎么判读stream是palindrome?
: stream可能是很大，内存可能放不下
|
|
|
h**k
发帖数: 3368 | 11 有人有思路么？
【在 v******a 的大作中提到】
: 一个char stream
: byte b=read() 从网络接收数据
: 怎么判读stream是palindrome?
: stream可能是很大，内存可能放不下
|
g******d
发帖数: 511 | 12 要考虑两种情况:
AABAA
AABB
对了,iq351,recurtier说了多长时间才可以申请GOOG? |
g******d
发帖数: 511 | 13 先分bucket存,数据流结束后,就知道最中间数的在那个bucket,然后双向比较.可以
concurrent比较所有的buckets. |
h**k
发帖数: 3368 | 14 用bucket存前面的元素，不会破坏元素顺序么？
【在 g******d 的大作中提到】
: 先分bucket存,数据流结束后,就知道最中间数的在那个bucket,然后双向比较.可以
: concurrent比较所有的buckets.
|
g******d
发帖数: 511 | 15 我这个bucket说错了,实际应该是多个文件.
something like
File A (从后到前) == File B (offset x) + File B next (0)
B需要读一部分下一个文件.
【在 h**k 的大作中提到】
: 用bucket存前面的元素，不会破坏元素顺序么？
|
h**k
发帖数: 3368 | 16 那就是还要保存前面所有的元素。如果内存不允许的话，有办法么？
【在 g******d 的大作中提到】
: 我这个bucket说错了,实际应该是多个文件.
: something like
: File A (从后到前) == File B (offset x) + File B next (0)
: B需要读一部分下一个文件.
|
p********7
发帖数: 549 | 17 先把可以用的内存分成5部分，每个部分占用Km空间。
先把数据读入M1并且从2头到中间来判断
M1满了，存M2，并且M1从头开始，M2从尾开始判断
M2满了，存M3.新的数据继续读到M3.
M3满了，就把M2存到file1.然后新的数据读到M2.
M2满了，就把M3存file2，读新的数据到M3.
如果M1，和M2，M3的数据都没问题，需要读file的文件继续判断，就把需要的file读到
M4，M5
file的数序是从2头到中间。 |
