f*4
2 楼
输入是个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的。。不过后来想了一下,也没想出更好的
大家看看咋写更好
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
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的。。不过后来想了一下,也没想出更好的
大家看看咋写更好
M1
3 楼
food processor包饺子有用处么?
blender呢?
blender呢?
a*9
4 楼
我也是这么做的,国人大哥,所以过了。。。 还有更好的方法么?这个已经是O(n)了
啊
啊
p*e
7 楼
我怎么看了好几遍标题都没有看见那个饺字呢? 是不是最近闲的........ 老有一种要
re的冲动.
re的冲动.
n*e
8 楼
试着写一写:
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 的大作中提到】
: 输入是个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)
: {
Find and print repeated sequences of 10 characters
void find_repeated_sequences(input_stream in)
{
string buf;
int count = 0;
map
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
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 的大作中提到】
: 输入是个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)
: {
j*u
9 楼
菜还是自己切得比blender打出来的好吃。
m*c
12 楼
这个repeated sequences of 10 characters怎么理解?是说找出input_stream里,长
度为10的,重复出现的的吗?
度为10的,重复出现的的吗?
z*5
14 楼
哥,这个if(temp=-1)太囧了。。。
m*4
16 楼
java中,strings immutable,最好不要append在string后面。所以要用StringBuilder
,但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
maintain一个能两头插入的data structure,circular array 啥的,
但问题是还得算hashcode,override
equals,麻烦不说,也不可能提高效率很多啊。想不通为什么被废
【在 f********4 的大作中提到】
: 输入是个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)
: {
,但StringBuilder 的substring方法又不efficient。不知道他是不是想让你自己
maintain一个能两头插入的data structure,circular array 啥的,
但问题是还得算hashcode,override
equals,麻烦不说,也不可能提高效率很多啊。想不通为什么被废
【在 f********4 的大作中提到】
: 输入是个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
18 楼
repeated sequence of 10 characters,是找另一个abcdefghij?
也算abcabcabcabcabcabc...这种连续重复的?string是要unique的还是所有的?问题
多多啊。
【在 f********4 的大作中提到】
: 输入是个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)
: {
也算abcabcabcabcabcabc...这种连续重复的?string是要unique的还是所有的?问题
多多啊。
【在 f********4 的大作中提到】
: 输入是个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
21 楼
s*w
22 楼
无脑 rolling hash,对付这种定长的字串专用
从头扫到尾,对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
dered_set)存起来的 hash code,重复的话,就输出当前的子串
比直接存所有的unique子串要省时间省空间
【在 f********4 的大作中提到】
: 输入是个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)
: {
从头扫到尾,对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
dered_set)存起来的 hash code,重复的话,就输出当前的子串
比直接存所有的unique子串要省时间省空间
【在 f********4 的大作中提到】
: 输入是个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)
: {
s*u
24 楼
rolling hash只要base取256即可,但好像会oveflow吧。不过我觉得的确是应该用循环
数组,因为你substr和pushback 恐怕都不是o1
数组,因为你substr和pushback 恐怕都不是o1
l*n
27 楼
他说的的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 的大作中提到】
: 能举个overflow的例子吗 想半天没想明白, 这种1个char 1个char 读进来的情况 挺
: 符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
: , 加在最后 rehash. 你说的循环数组是类似思想吗?
newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
rehash这一说。
这一题用rolling hash就只是在计算hash的时候节省一点,但还是需要像普通的hash
table那样处理collision,需要存所有unique字串。这么一来,感觉就需要自己搞一个
hashmap了,更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
缝连接。
【在 J****3 的大作中提到】
: 能举个overflow的例子吗 想半天没想明白, 这种1个char 1个char 读进来的情况 挺
: 符合用rh的啊。 先存第一个长度为10的string, 对新进来的chara, 去掉原string 头
: , 加在最后 rehash. 你说的循环数组是类似思想吗?
J*3
28 楼
我以为每次算roll 那个方程的时候就是rehash。。
用roll出来的hash值重载下[] operator?
base+
【在 l*n 的大作中提到】
: 他说的的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直接无
: 缝连接。
用roll出来的hash值重载下[] operator?
base+
【在 l*n 的大作中提到】
: 他说的的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
29 楼
如果是用256的底,没有collision,就像你一个数用十进制表示,只有唯一一种可能。
base+
【在 l*n 的大作中提到】
: 他说的的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直接无
: 缝连接。
base+
【在 l*n 的大作中提到】
: 他说的的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直接无
: 缝连接。
m*4
32 楼
我是C++盲,不知道这个CODE是不是有BUG:
1.你的read() return value是int,你可以直接转成char没有问题吗?
2.不知道unordered_set是啥,好象可以count。但你边读入边比较,这个count在到了
1以后就没有更新了吧,所以如果一个string出现了10次,你要print 9次,这个对
吗?
【在 f********4 的大作中提到】
: 输入是个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)
: {
1.你的read() return value是int,你可以直接转成char没有问题吗?
2.不知道unordered_set是啥,好象可以count。但你边读入边比较,这个count在到了
1以后就没有更新了吧,所以如果一个string出现了10次,你要print 9次,这个对
吗?
【在 f********4 的大作中提到】
: 输入是个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
33 楼
1。可以啊,这个和什么语言没有关吗。。ASCII的话都这样的吧。。
2。set就是hash—map啊,本来就不用更新啊,汗。出现十次说明9次是重复的啊,没有
问题的
[发表自未名空间手机版 - m.mitbbs.com]
【在 m**********4 的大作中提到】
: 我是C++盲,不知道这个CODE是不是有BUG:
: 1.你的read() return value是int,你可以直接转成char没有问题吗?
: 2.不知道unordered_set是啥,好象可以count。但你边读入边比较,这个count在到了
: 1以后就没有更新了吧,所以如果一个string出现了10次,你要print 9次,这个对
: 吗?
2。set就是hash—map啊,本来就不用更新啊,汗。出现十次说明9次是重复的啊,没有
问题的
[发表自未名空间手机版 - m.mitbbs.com]
【在 m**********4 的大作中提到】
: 我是C++盲,不知道这个CODE是不是有BUG:
: 1.你的read() return value是int,你可以直接转成char没有问题吗?
: 2.不知道unordered_set是啥,好象可以count。但你边读入边比较,这个count在到了
: 1以后就没有更新了吧,所以如果一个string出现了10次,你要print 9次,这个对
: 吗?
l*n
35 楼
好像明白你的意思,是在利用字符只有10这一点吗?只算小写字母有26个,每个需要5
个bit,10个数一共是50个bit,比64要小。这样long的取值能比10个小写字母的范围大
。但是一旦加入数字或者大写字母就还是会有collision了。
如果是你说的256为底,需要8个bit,直接对应10字符的话,需要一共80bit,超过long
的64了吧?longlong 是128bit么?那的确是一个longlong一个串了。
unordered_
【在 s********u 的大作中提到】
: 关键是rolling hash可以做到增量的计算,string就不行了。而且你用一个unordered_
: set去存,一个是存10字符的字符串,一个只是记一个long long,还是有优劣之分的
:
: hashing
个bit,10个数一共是50个bit,比64要小。这样long的取值能比10个小写字母的范围大
。但是一旦加入数字或者大写字母就还是会有collision了。
如果是你说的256为底,需要8个bit,直接对应10字符的话,需要一共80bit,超过long
的64了吧?longlong 是128bit么?那的确是一个longlong一个串了。
unordered_
【在 s********u 的大作中提到】
: 关键是rolling hash可以做到增量的计算,string就不行了。而且你用一个unordered_
: set去存,一个是存10字符的字符串,一个只是记一个long long,还是有优劣之分的
:
: hashing
m*4
36 楼
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 的大作中提到】
: 1。可以啊,这个和什么语言没有关吗。。ASCII的话都这样的吧。。
: 2。set就是hash—map啊,本来就不用更新啊,汗。出现十次说明9次是重复的啊,没有
: 问题的
:
: [发表自未名空间手机版 - m.mitbbs.com]
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 的大作中提到】
: 1。可以啊,这个和什么语言没有关吗。。ASCII的话都这样的吧。。
: 2。set就是hash—map啊,本来就不用更新啊,汗。出现十次说明9次是重复的啊,没有
: 问题的
:
: [发表自未名空间手机版 - m.mitbbs.com]
f*4
37 楼
那个read函数,输出的本来就是字符啊。。就和97是‘a’一样
如果到头了才是-1
还有那个是typo。。应该是temp==-1
这些细枝末节的东西,非要在这里展示知道的很多,没有什么意思吧
【在 m**********4 的大作中提到】
: 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.
如果到头了才是-1
还有那个是typo。。应该是temp==-1
这些细枝末节的东西,非要在这里展示知道的很多,没有什么意思吧
【在 m**********4 的大作中提到】
: 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
38 楼
long long是64,所以我前面说这个overflow很尴尬。正好差一些。
long是32吧一般。
5
long
【在 l*n 的大作中提到】
: 好像明白你的意思,是在利用字符只有10这一点吗?只算小写字母有26个,每个需要5
: 个bit,10个数一共是50个bit,比64要小。这样long的取值能比10个小写字母的范围大
: 。但是一旦加入数字或者大写字母就还是会有collision了。
: 如果是你说的256为底,需要8个bit,直接对应10字符的话,需要一共80bit,超过long
: 的64了吧?longlong 是128bit么?那的确是一个longlong一个串了。
:
: unordered_
long是32吧一般。
5
long
【在 l*n 的大作中提到】
: 好像明白你的意思,是在利用字符只有10这一点吗?只算小写字母有26个,每个需要5
: 个bit,10个数一共是50个bit,比64要小。这样long的取值能比10个小写字母的范围大
: 。但是一旦加入数字或者大写字母就还是会有collision了。
: 如果是你说的256为底,需要8个bit,直接对应10字符的话,需要一共80bit,超过long
: 的64了吧?longlong 是128bit么?那的确是一个longlong一个串了。
:
: unordered_
s*w
39 楼
只要你的 hash 足够好,collision 的几率很小的,和中彩票一样
hash 不够好,或者需要 double check 的话,多存一个 index
本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
collision 就一一对照一下
省空间,因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
省时间,因为 你只需要对整数操作
说的够明白吧?
【在 l*n 的大作中提到】
: rolling hash有collision怎么办?最后你还是得存所有unique字串。想省空间还是得
: 上trie,插入即查询。
:
: unor
hash 不够好,或者需要 double check 的话,多存一个 index
本来只需要存 hash code, 现在用 map/unordered_map 存 (hash code,ind); 发现有
collision 就一一对照一下
省空间,因为 存子串显然要很浪费, 你想假如现在要求算 1k 长的子串?
省时间,因为 你只需要对整数操作
说的够明白吧?
【在 l*n 的大作中提到】
: rolling hash有collision怎么办?最后你还是得存所有unique字串。想省空间还是得
: 上trie,插入即查询。
:
: unor
p*2
42 楼
d*g
45 楼
我amazon做个跟这个差不多的,如果读到-1的时候你一样把它传给char,这样是不行的,,
,,,
会爆掉,,
你觉得呢
,,,
会爆掉,,
你觉得呢
w*a
46 楼
不是只有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);
}
}
那10个字符可能性就一百多万个啊。一个int就能搞定,也没有碰撞的担忧。
或者干脆用20个bit来存10个字符,每走一个,就往左边shift两位,然后或一下新拿到
的字符。
写了一下:
void find_repeated_sequences(const input_stream& in) {
static map
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
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
47 楼
c++没看懂,能就你的思路举个例子么?
【在 w****a 的大作中提到】
: 不是只有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;
【在 w****a 的大作中提到】
: 不是只有4个字母么?ATGC。
: 那10个字符可能性就一百多万个啊。一个int就能搞定,也没有碰撞的担忧。
: 或者干脆用20个bit来存10个字符,每走一个,就往左边shift两位,然后或一下新拿到
: 的字符。
: 写了一下:
: void find_repeated_sequences(const input_stream& in) {
: static map
:
: int cur_code = 0;
: const int STR_SIZE = 10;
相关阅读
关于h1b和入职时间的问题有没有嵌入式的工作机会啊?amazon是不是流行默剧啊。诚心请教一个start up的offer[合集] 攒RP,跟大家分享一些找工经验和教训(非工科)CMU, berkeley,stanford这样的牛校的eecs的postdoc能给多少请问除了bloomberg还有哪些公司接受非CS的fresh Ph.D码工申请的?今年就业形势是比往年差吧找工作不顺,请教OPT和H1的难题老板不让去实习[合集] 问个h1b申请时间和premium processing的问题[合集] LG找工作一年上来求建议Facebook onsite结束 求bless面试时关于工作开始时间的问题LCA时间求安慰兼bless求暴力fibonacci的复杂度请问e-verify 通过就可以合法工作吗?[合集] startup公司很难申请到H1B吗?问一个关于reference的问题