f********4 发帖数: 988 | 1 输入是个stream
class input_stream
{
// Character or -1
int read();
}
每次call read(),返回一个char,如果到头了就是返回-1
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
unordered_set record;
while(true){
char temp = in.read();
if(temp=-1)
break;
buf.push_back(temp);
if(buf.length()>10)
buf = buf.substr(1);
if(buf.lengh()==10){
if(record.count(buf)==1){
cout<
}
else record.emplace(buf);
}
}
}
挂了。。
当时想先写个work的。。不过后来想了一下,也没想出更好的
大家看看咋写更好 |
a********9 发帖数: 129 | 2 我也是这么做的,国人大哥,所以过了。。。 还有更好的方法么?这个已经是O(n)了
啊 |
f********4 发帖数: 988 | 3 。。。。
fb二面碰见国人挂了
L一面碰见红毛又挂了。。
我真的很想去CA旅游啊。。。让我过一次吧。。
【在 a********9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也是这么做的,国人大哥,所以过了。。。 还有更好的方法么?这个已经是O(n)了 : 啊
|
n****e 发帖数: 678 | 4 试着写一写:
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
int count = 0;
map > record;
while(true){
char temp = in.read();
if(temp=-1)
break;
buf.push_back(temp);
if(buf.length()==10)
buf = buf.substr(0, 10);
record[buf].push_back(count);
count++;
buf = buf.substr(1, 9);
}
}
map >::iterator iter;
for (iter = record.begin(); iter != record.end(); iter++) {
if (iter->second.size() > 1) {
int N = iter->second.size();
if (iter->second[N-1] - iter->second[0] >= 10) {
count << iter->first << endl;
}
}
}
}
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 输入是个stream : class input_stream : { : // Character or -1 : int read(); : } : 每次call read(),返回一个char,如果到头了就是返回-1 : Find and print repeated sequences of 10 characters : void find_repeated_sequences(input_stream in) : {
|
w********s 发帖数: 214 | 5 这个题目用java能写么?
【在 n****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 试着写一写: : Find and print repeated sequences of 10 characters : void find_repeated_sequences(input_stream in) : { : string buf; : int count = 0; : map > record; : while(true){ : char temp = in.read(); : if(temp=-1)
|
m********c 发帖数: 105 | 6 这个repeated sequences of 10 characters怎么理解?是说找出input_stream里,长
度为10的,重复出现的的吗? |
z*****5 发帖数: 38 | |
m**********4 发帖数: 774 | 8 java中,strings immutable,最好不要append在string后面。所以要用StringBuilder
,但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
maintain一个能两头插入的data structure,circular array 啥的,
但问题是还得算hashcode,override
equals,麻烦不说,也不可能提高效率很多啊。想不通为什么被废
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 输入是个stream : class input_stream : { : // Character or -1 : int read(); : } : 每次call read(),返回一个char,如果到头了就是返回-1 : Find and print repeated sequences of 10 characters : void find_repeated_sequences(input_stream in) : {
|
l*n 发帖数: 529 | 9 repeated sequence of 10 characters,是找另一个abcdefghij?
也算abcabcabcabcabcabc...这种连续重复的?string是要unique的还是所有的?问题
多多啊。
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 输入是个stream : class input_stream : { : // Character or -1 : int read(); : } : 每次call read(),返回一个char,如果到头了就是返回-1 : Find and print repeated sequences of 10 characters : void find_repeated_sequences(input_stream in) : {
|
f********4 发帖数: 988 | 10 是找另一个前面出现过的序列,也可以连续重复啊,只要重复就可以
算短一点,比如abcabcabcabc,比如说找长度为4
abca,bcab,cabc都是啊
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : repeated sequence of 10 characters,是找另一个abcdefghij? : 也算abcabcabcabcabcabc...这种连续重复的?string是要unique的还是所有的?问题 : 多多啊。
|
|
|
f********4 发帖数: 988 | 11 嗯,一开始我也提了,面试官也没答腔。我就说那我先写个work的吧
StringBuilder
【在 m**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java中,strings immutable,最好不要append在string后面。所以要用StringBuilder : ,但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己 : maintain一个能两头插入的data structure,circular array 啥的, : 但问题是还得算hashcode,override : equals,麻烦不说,也不可能提高效率很多啊。想不通为什么被废
|
s*w 发帖数: 729 | 12 无脑 rolling hash,对付这种定长的字串专用
从头扫到尾,对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
dered_set)存起来的 hash code,重复的话,就输出当前的子串
比直接存所有的unique子串要省时间省空间
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 输入是个stream : class input_stream : { : // Character or -1 : int read(); : } : 每次call read(),返回一个char,如果到头了就是返回-1 : Find and print repeated sequences of 10 characters : void find_repeated_sequences(input_stream in) : {
|
l*n 发帖数: 529 | 13 rolling hash有collision怎么办?最后你还是得存所有unique字串。想省空间还是得
上trie,插入即查询。
unor
【在 s*w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 无脑 rolling hash,对付这种定长的字串专用 : 从头扫到尾,对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor : dered_set)存起来的 hash code,重复的话,就输出当前的子串 : 比直接存所有的unique子串要省时间省空间
|
s********u 发帖数: 1109 | 14 rolling hash只要base取256即可,但好像会oveflow吧。不过我觉得的确是应该用循环
数组,因为你substr和pushback 恐怕都不是o1 |
f********4 发帖数: 988 | 15 哦,我去看看rolling hash是神马东西。。
push back和 substr时间复杂度应该都是liner的吧,因为只有10个character,但是空
间复杂度就不好说了,buf = buf.substr(1)我也搞不清是不是call 了copy
constructor
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : rolling hash只要base取256即可,但好像会oveflow吧。不过我觉得的确是应该用循环 : 数组,因为你substr和pushback 恐怕都不是o1
|
J****3 发帖数: 427 | 16 能举个overflow的例子吗 想半天没想明白, 这种1个char 1个char 读进来的情况 挺
符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
, 加在最后 rehash. 你说的循环数组是类似思想吗?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : rolling hash只要base取256即可,但好像会oveflow吧。不过我觉得的确是应该用循环 : 数组,因为你substr和pushback 恐怕都不是o1
|
l*n 发帖数: 529 | 17 他说的的overflow是因为rolling hash是个多项式,每次roll的时候是lastHash*base+
newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
rehash这一说。
这一题用rolling hash就只是在计算hash的时候节省一点,但还是需要像普通的hash
table那样处理collision,需要存所有unique字串。这么一来,感觉就需要自己搞一个
hashmap了,更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
缝连接。
【在 J****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能举个overflow的例子吗 想半天没想明白, 这种1个char 1个char 读进来的情况 挺 : 符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头 : , 加在最后 rehash. 你说的循环数组是类似思想吗?
|
J****3 发帖数: 427 | 18 我以为每次算roll 那个方程的时候就是rehash。。
用roll出来的hash值重载下[] operator?
base+
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他说的的overflow是因为rolling hash是个多项式,每次roll的时候是lastHash*base+ : newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有 : rehash这一说。 : 这一题用rolling hash就只是在计算hash的时候节省一点,但还是需要像普通的hash : table那样处理collision,需要存所有unique字串。这么一来,感觉就需要自己搞一个 : hashmap了,更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无 : 缝连接。
|
s********u 发帖数: 1109 | 19 如果是用256的底,没有collision,就像你一个数用十进制表示,只有唯一一种可能。
base+
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他说的的overflow是因为rolling hash是个多项式,每次roll的时候是lastHash*base+ : newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有 : rehash这一说。 : 这一题用rolling hash就只是在计算hash的时候节省一点,但还是需要像普通的hash : table那样处理collision,需要存所有unique字串。这么一来,感觉就需要自己搞一个 : hashmap了,更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无 : 缝连接。
|
l*n 发帖数: 529 | 20 不太明白。如果没有collision,那hashing的值域就跟定义域一样了,还需要hashing
作甚?
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是用256的底,没有collision,就像你一个数用十进制表示,只有唯一一种可能。 : : base+
|
|
|
m**********4 发帖数: 774 | 21 同觉得还是trie比较好。能否用trie+circular array? circular array只管记录,
两头插入删除都很方便, trie代替hash。不知道C++如何,但我觉得java中的string
和StringBuilder都不efficient。
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : rolling hash有collision怎么办?最后你还是得存所有unique字串。想省空间还是得 : 上trie,插入即查询。 : : unor
|
m**********4 发帖数: 774 | 22 我是C++盲,不知道这个CODE是不是有BUG:
1.你的read() return value是int,你可以直接转成char没有问题吗?
2.不知道unordered_set是啥,好象可以count。但你边读入边比较,这个count在到了
1以后就没有更新了吧,所以如果一个string出现了10次,你要print 9次,这个对
吗?
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 输入是个stream : class input_stream : { : // Character or -1 : int read(); : } : 每次call read(),返回一个char,如果到头了就是返回-1 : Find and print repeated sequences of 10 characters : void find_repeated_sequences(input_stream in) : {
|
f********4 发帖数: 988 | 23 1。可以啊,这个和什么语言没有关吗。。ASCII的话都这样的吧。。
2。set就是hash—map啊,本来就不用更新啊,汗。出现十次说明9次是重复的啊,没有
问题的
[发表自未名空间手机版 - m.mitbbs.com]
【在 m**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我是C++盲,不知道这个CODE是不是有BUG: : 1.你的read() return value是int,你可以直接转成char没有问题吗? : 2.不知道unordered_set是啥,好象可以count。但你边读入边比较,这个count在到了 : 1以后就没有更新了吧,所以如果一个string出现了10次,你要print 9次,这个对 : 吗?
|
s********u 发帖数: 1109 | 24 关键是rolling hash可以做到增量的计算,string就不行了。而且你用一个unordered_
set去存,一个是存10字符的字符串,一个只是记一个long long,还是有优劣之分的
hashing
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不太明白。如果没有collision,那hashing的值域就跟定义域一样了,还需要hashing : 作甚?
|
l*n 发帖数: 529 | 25 好像明白你的意思,是在利用字符只有10这一点吗?只算小写字母有26个,每个需要5
个bit,10个数一共是50个bit,比64要小。这样long的取值能比10个小写字母的范围大
。但是一旦加入数字或者大写字母就还是会有collision了。
如果是你说的256为底,需要8个bit,直接对应10字符的话,需要一共80bit,超过long
的64了吧?longlong 是128bit么?那的确是一个longlong一个串了。
unordered_
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 关键是rolling hash可以做到增量的计算,string就不行了。而且你用一个unordered_ : set去存,一个是存10字符的字符串,一个只是记一个long long,还是有优劣之分的 : : hashing
|
m**********4 发帖数: 774 | 26 in java, if you do
int x = 5;
char c = x;
it won't compile... Not sure why you can do
char temp = in.read();
还有你能把-1赋给char?我试了下
char c = (char)-1;
System.out.println((int)c);
I get 65335.
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1。可以啊,这个和什么语言没有关吗。。ASCII的话都这样的吧。。 : 2。set就是hash—map啊,本来就不用更新啊,汗。出现十次说明9次是重复的啊,没有 : 问题的 : : [发表自未名空间手机版 - m.mitbbs.com]
|
f********4 发帖数: 988 | 27 那个read函数,输出的本来就是字符啊。。就和97是‘a’一样
如果到头了才是-1
还有那个是typo。。应该是temp==-1
这些细枝末节的东西,非要在这里展示知道的很多,没有什么意思吧
【在 m**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : in java, if you do : int x = 5; : char c = x; : it won't compile... Not sure why you can do : char temp = in.read(); : 还有你能把-1赋给char?我试了下 : char c = (char)-1; : System.out.println((int)c); : I get 65335.
|
s********u 发帖数: 1109 | 28 long long是64,所以我前面说这个overflow很尴尬。正好差一些。
long是32吧一般。
5
long
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好像明白你的意思,是在利用字符只有10这一点吗?只算小写字母有26个,每个需要5 : 个bit,10个数一共是50个bit,比64要小。这样long的取值能比10个小写字母的范围大 : 。但是一旦加入数字或者大写字母就还是会有collision了。 : 如果是你说的256为底,需要8个bit,直接对应10字符的话,需要一共80bit,超过long : 的64了吧?longlong 是128bit么?那的确是一个longlong一个串了。 : : unordered_
|
s*w 发帖数: 729 | 29 只要你的 hash 足够好,collision 的几率很小的,和中彩票一样
hash 不够好,或者需要 double check 的话,多存一个 index
本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
collision 就一一对照一下
省空间,因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
省时间,因为 你只需要对整数操作
说的够明白吧?
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : rolling hash有collision怎么办?最后你还是得存所有unique字串。想省空间还是得 : 上trie,插入即查询。 : : unor
|
l*n 发帖数: 529 | 30 index就能表示字串了?stream读完了就没了,要index何用?
有
【在 s*w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只要你的 hash 足够好,collision 的几率很小的,和中彩票一样 : hash 不够好,或者需要 double check 的话,多存一个 index : 本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有 : collision 就一一对照一下 : 省空间,因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串? : 省时间,因为 你只需要对整数操作 : 说的够明白吧?
|
|
|
s*w 发帖数: 729 | 31 没注意看题,居然是 stream, 那的确不能存 index 了,不过还是可以用 rolling
hash
还是那句话,你要相信概率;坐飞机掉下来的概率其实也不小,大家不还天天坐嘛
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : index就能表示字串了?stream读完了就没了,要index何用? : : 有
|
p*******2 发帖数: 50 | 32 这个circular array可以直接用ArrayDeque?
StringBuilder
【在 m**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java中,strings immutable,最好不要append在string后面。所以要用StringBuilder : ,但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己 : maintain一个能两头插入的data structure,circular array 啥的, : 但问题是还得算hashcode,override : equals,麻烦不说,也不可能提高效率很多啊。想不通为什么被废
|
l*n 发帖数: 529 | 33 good point, java arraydeque就是现成的circular array。
【在 p*******2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个circular array可以直接用ArrayDeque? : : StringBuilder
|
t******i 发帖数: 483 | 34 abca, bcab, cabc 的话你这个程序就不work了吧。
set里面存了abca, count("bcab") 就是0了呀。
【在 f********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是找另一个前面出现过的序列,也可以连续重复啊,只要重复就可以 : 算短一点,比如abcabcabcabc,比如说找长度为4 : abca,bcab,cabc都是啊
|
d******g 发帖数: 42 | 35 我amazon做个跟这个差不多的,如果读到-1的时候你一样把它传给char,这样是不行的,,
,,,
会爆掉,,
你觉得呢 |
w****a 发帖数: 710 | 36 不是只有4个字母么?ATGC。
那10个字符可能性就一百多万个啊。一个int就能搞定,也没有碰撞的担忧。
或者干脆用20个bit来存10个字符,每走一个,就往左边shift两位,然后或一下新拿到
的字符。
写了一下:
void find_repeated_sequences(const input_stream& in) {
static map table = {{'A', 0},{'T', 1},{'G', 2},{'C', 3}};
int cur_code = 0;
const int STR_SIZE = 10;
auto print_code = [](int code) {
static char inv_table[4] = {'A','T','G','C'};
for(int i = 0; i < STR_SIZE; ++i) {
cout << inv_table[code & 0x3];
code >>= 2;
}
cout << endl;
};
for(int i = 0; i < STR_SIZE; ++i) {
char c = in.read();
if(c == -1) return;
cur_code |= table[c] << i*2;
}
unordered_map counter = {{cur_code, 1}};
while(true) {
char c = in.read();
if(c == -1) break;
cur_code = (cur_code >> 2) | (table[c] << (STR_SIZE-1)*2);
++counter[cur_code];
}
for(auto &p : counter) {
if(p.second > 1) print_code(p.first);
}
} |
t*******e 发帖数: 274 | 37 c++没看懂,能就你的思路举个例子么?
【在 w****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是只有4个字母么?ATGC。 : 那10个字符可能性就一百多万个啊。一个int就能搞定,也没有碰撞的担忧。 : 或者干脆用20个bit来存10个字符,每走一个,就往左边shift两位,然后或一下新拿到 : 的字符。 : 写了一下: : void find_repeated_sequences(const input_stream& in) { : static map table = {{'A', 0},{'T', 1},{'G', 2},{'C', 3}}; : : int cur_code = 0; : const int STR_SIZE = 10;
|