RA一个月能做几次survey？ - 未名空间MITBBS历史存档

d*12011-03-17 07:03

1 楼

本人因为工作性质，加上自己喜欢了解底层百姓的生活，更可能是自己在中国也是底
层吧，所以可以了解一些美国很底层人的命运。今天说的这故事，实在让我震惊，所以
写下来，让大家知道一个真实的美国的另外一面。
夫妻加4个孩子。和一条狗，住我隔壁，因为我穷，所以选了个便宜的CONDO，在这里
住的就都是穷人了。
吸毒，酗酒，烟是他们的生活。
1：丈夫得的是DDD病。身体特别痛，4次手术后只能申请DISABLE，下星期上庭，决定
是否可以拿。今年39岁。
2：妻子做MINIMUM工作。每天有60美元。2孩子已经离开家，其他2个是14岁，女，9岁
男。夫妻2人都是酒鬼烟鬼。2人平均每天在烟酒上花20美元。房子是750美元/月。所以
他们靠老婆的工作根本不行。
我搬来第3天，他们找我借15美元。要买酒，我拒绝了。因为总在外面抽烟，很快混亲
热了。。。
故事开始：
本人喜欢算命，也给美国人算。算丈夫的时候，他很满意，说太准了。老婆回来，也
让我算。。结果我说8-14的时候不好。。丈夫马上就补充性的问老婆：”你那强奸不
是。。。。“ 老婆故意装着不接话，我也装着没有听见。。但我明白他老婆小时候被
害过。当时我的确很同情。。。
2天后。。那男孩一头黄发，加上面部很多雀斑。我就问他的头发是染的吗。。老婆
悄悄地说，那年我被强奸。。估计是。。。还是个双胞胎，1个生出来就死了。。这
时候丈夫也接话，说肯定不会让孩子知道。。。
又2天后，我给他们30美元，提议让所有CONDO的4家一起开个PARTY。。我说想看大家
醉的样子。。
结果因为没有确定好。整个PARTY成了他老婆个人的。。到11点。。醉了。。第2天
早晨，丈夫和我说，老婆12-2点不知道到哪里去了。回来头碰到墙。。清一大块。。
他们孩子很好。对那男孩也很好，但老婆明显担心丈夫会暗里对孩子不好（有例子，。
。）2人就是喝酒问题，明显老婆2次被强奸都是因为醉了。。
根本不悔改。。

c*z2011-03-17 07:03

2 楼

given a string ,return the longest substring that contains at most two
characters.
该咋写？

w*e2011-03-17 07:03

3 楼

刚才收据出个survey，输入code后竟然说已经做过了这个月。

f*g2011-03-17 07:03

4 楼

真吓人，乱七八糟的生活

t*e2011-03-17 07:03

5 楼

Two pointer traversal + memorization. 这类题目是不是都差不多这样

b*92011-03-17 07:03

6 楼

清cookie
跟ra无关，跟浏览器使用有关

k*n2011-03-17 07:03

7 楼

動物一樣的生活

f*w2011-03-17 07:03

8 楼

和leetcode的Longest Substring Without Repeating Characters类似
两个指针start和end，从左往右扫一遍，如果start和end之间符合条件就++end，否则
就++start

s*d2011-03-17 07:03

9 楼

一个code做一个survey.
如有很多code,ie 3个，firefox 3个，chrome3个，不过也有可以弄unlimited的。
再有就是换电脑做。

m*62011-03-17 07:03

10 楼

"丈夫和我说，老婆12-2点不知道到哪里去了"
难道他们第五个孩子要黑头发?

【在 d********1 的大作中提到】

: 本人因为工作性质，加上自己喜欢了解底层百姓的生活，更可能是自己在中国也是底
: 层吧，所以可以了解一些美国很底层人的命运。今天说的这故事，实在让我震惊，所以
: 写下来，让大家知道一个真实的美国的另外一面。
: 夫妻加4个孩子。和一条狗，住我隔壁，因为我穷，所以选了个便宜的CONDO，在这里
: 住的就都是穷人了。
: 吸毒，酗酒，烟是他们的生活。
: 1：丈夫得的是DDD病。身体特别痛，4次手术后只能申请DISABLE，下星期上庭，决定
: 是否可以拿。今年39岁。
: 2：妻子做MINIMUM工作。每天有60美元。2孩子已经离开家，其他2个是14岁，女，9岁
: 男。夫妻2人都是酒鬼烟鬼。2人平均每天在烟酒上花20美元。房子是750美元/月。所以

l*a2011-03-17 07:03

11 楼

我去替你onsite吧

【在 c**z 的大作中提到】

: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？

s*d2011-03-17 07:03

12 楼

大大，不是有人说清cookie没用吗？

【在 b*******9 的大作中提到】

: 清cookie
: 跟ra无关，跟浏览器使用有关

a*i2011-03-17 07:03

13 楼

“明显老婆2次被强奸都是因为醉了。。”
看lz的意思是。

【在 m******6 的大作中提到】

: "丈夫和我说，老婆12-2点不知道到哪里去了"
: 难道他们第五个孩子要黑头发?

v*l2011-03-17 07:03

14 楼

我电面的时候问了这题，记录一下那个turning point 就好

w*e2011-03-17 07:03

15 楼

知道了，明天换台电脑试试，谢谢mm和楼上的tx!

【在 s*****d 的大作中提到】

: 一个code做一个survey.
: 如有很多code,ie 3个，firefox 3个，chrome3个，不过也有可以弄unlimited的。
: 再有就是换电脑做。

M*M2011-03-17 07:03

16 楼

类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
unordered_map 记录这2个char最后出现的index。
string findsubstring(string s) {
if(s.empty()) {
return string();
}
queue que;
unordered_map map;
int maxlen = 0, maxindex=0, index=0;
for(int i=0; iif(map.find(s[i])==map.end()) {
if(que.size()==2) {
if(i-index>maxlen) {
maxlen = i-index;
maxindex = index;
}
//update que and map
char c=que.front();
que.pop();
index = map[c]+1;
map.erase(c);
}
map[s[i]] = i;
que.push(s[i]);
} else {
map[s[i]] = i;
}
}
if(s.size()-index>maxlen) {
maxlen = s.size()-index;
maxindex = index;
}
return s.substr(maxindex, maxlen);
}

i*u2011-03-17 07:03

17 楼

如果问你一个character你就会，问两个就不会了？是不是第二天就被据了：）
开个玩笑啊别怒

j*d2011-03-17 07:03

18 楼

at most two
characters.。什么意思？2个不一样的？aaaaab算longest是么？

s*r2011-03-17 07:03

19 楼

这题啥意思都没看懂，lz题目没写清楚吧？

a*e2011-03-17 07:03

20 楼

没看懂， string 里除了字符都是空格？

【在 c**z 的大作中提到】

: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？

w*t2011-03-17 07:03

21 楼

这个空间复杂度高了，会要求你不用额外数据结构来解决。
这题 corner case多

【在 M*****M 的大作中提到】

: 类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
: unordered_map 记录这2个char最后出现的index。
: string findsubstring(string s) {
: if(s.empty()) {
: return string();
: }
: queue que;
: unordered_map map;
: int maxlen = 0, maxindex=0, index=0;
: for(int i=0; i

p*n2011-03-17 07:03

22 楼

O(1) space complexity.
O(n) time complexity.
// Given a string, return the longest substring that contains at most // two
characters.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}

int first_start = 0;
int second_start;
char first = input[0];
char second;
int end = 1;
while (end < input.size() && input[end] == first) {
end++;
}
if (end == input.size()) {
return input.size();
} else {
second = input[end];
second_start = end;
}

int solution = end - first_start + 1;
while (end < input.size() - 1) {
end++;
if (input[end] == first || input[end] == second) {
solution = (end - first_start + 1) > solution ?
(end - first_start + 1) : solution;
} else {
first = second;
first_start = second_start;
second = input[end];
second_start = end;
}
}
return solution;
}
int main() {
string input1 = "aabcdeffzzeee";
string input2 = "abababa";
cout << "solution length == "<< FindLength(input2) << endl;
return 0;
}

y*a2011-03-17 07:03

23 楼

int longestTwoCharWindow(String s) {
if (s.length()==0) return 0;
char c1=s.charAt(0),c2=c1;
int ct=1,ml=1,rec=1;
for (int l=0,r=1;rif (ct==1)
if (s.charAt(r)==c1)++rec;
else {++ct;rec=1;c2=s.charAt(r);}
else if (ct==2)
if (s.charAt(r)==c1){rec=1;}
else if (s.charAt(r)==c2){++rec;}
else {l=r-rec;rec=1;c1=c2;c2=s.charAt(r);}
ml=Math.max(ml, r-l);
}
return ml;
}

p*n2011-03-17 07:03

24 楼

Space O(1)
Time O(n)
// Given a string, return the longest substring that contains at most // two
characters.
// solution: scan the string and update the first and second letter's last
occurrence
// indices, and update the solution's start index.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}

int solu_start = 0;
int first_end, second_end;
char first = input[0];
char second;
int curr = 1;
while (curr < input.size() && input[curr] == first) {
curr++;
}
if (curr == input.size()) {
return input.size();
} else {
first_end = curr - 1;
second = input[curr];
second_end = curr;
}

int solution = curr - solu_start + 1;
while (curr < input.size() - 1) {
curr++;
if (input[curr] == first) {
first_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else if (input[curr] == second) {
second_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else { // look back to last curr
if (input[curr - 1] == first) {
solu_start = second_end + 1;
second = input[curr];
second_end = curr;
} else {
solu_start = first_end + 1;
first = input[curr];
first_end = curr;
}
}
}
return solution;
}
int main() {
string input1 = "aabcdeffzzeee";
string input2 = "ababa";
string input3 = "ababacccccc";
cout << "solution length == "<< FindLength(input3) << endl;
return 0;
}

i*d2011-03-17 07:03

25 楼

Space O(1), Time O(n)
public int maxLength(String s){
if (s.isEmpty()) return 0;
int diffCharIndex = -1, currentLength = 1, maxLength = 1;
for (int i = 1; i < s.length(); i++)
{
if (s.charAt(i) != s.charAt(i-1))
{
if (diffCharIndex == -1 || s.charAt(i) == s.charAt(
diffCharIndex)) {
currentLength++; diffCharIndex = i - 1; }
else { currentLength = i - diffCharIndex; diffCharIndex = i-
1; }
}
else currentLength++;
if (currentLength > maxLength) maxLength = currentLength;
}
return maxLength;
}

a*y2011-03-17 07:03

26 楼

int FindLongsetTwoLetterSubstr(const std::string& str) {
int max_len = 0;
int curr_len = 0;
int n = str.size();
if (n == 0) {
return 0;
}
char letters[2];
letters[0] = str[0];
int i = 0;
int last_pos = 0;
for (; i < n; ++i) {
if (i != 0 && str[i] != str[i - 1]) {
letters[1] = str[i];
last_pos = i;
break;
}
}
int org_pos = 0;
for (; i < n; ++i) {
if (str[i] != str[i - 1]) {
if (str[i] != letters[0] && str[i] != letters[1]) {
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
curr_len = i - last_pos;
org_pos = last_pos;
last_pos = i;
if (str[org_pos] == letters[0]) {
letters[1] = str[i];
} else {
letters[0] = str[i];
}
} else {
last_pos = i;
}
}
}
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
return max_len;
}

s*62011-03-17 07:03

27 楼

两个指针
int longestSubstr(string s) {
int count[256];
memset(count, 0, sizeof(count));
int cnt = 0;
int i = 0;
int res = 0;
for(int j=0; jcount[s[j]] ++;
if(count[s[j]] == 1) cnt ++;
while(cnt > 2) {
count[s[i]] --;
if(count[s[i]] == 0) cnt --;
i ++;
}
res = max(res, j-i+1);
}
return res;
}

s*62011-03-17 07:03

28 楼

就是两个指针+一个计数的，假设是string是 acsii
int longestSubstr(string s) {
int count[256];
memset(count, 0, sizeof(count));
int cnt = 0;
int i = 0;
int res = 0;
for(int j=0; jcount[s[j]] ++;
if(count[s[j]] == 1) cnt ++;
while(cnt > 2) {
count[s[i]] --;
if(count[s[i]] == 0) cnt --;
i ++;
}
res = max(res, j-i+1);
}
return res;
}

m*k2011-03-17 07:03

29 楼

counter用不着吧，sliding window idea,
public static int getLongestSubStringWith2Chars(String s) {
if(s==null || s.isEmpty()){
return 0;
}
int c1Idx = 0;
int c2Idx = 0;
int c3Idx = 0;
int l = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) != s.charAt(c2Idx)) {
c3Idx = i;
int temp = c3Idx - c1Idx;
if (temp > l) {
l = temp;
System.out.format("length:%d start:%d end:%d\n", l,
c1Idx, c3Idx - 1);
}
c1Idx = c2Idx;
c2Idx = c3Idx;
}
}
c3Idx = s.length();
int temp = c3Idx - c1Idx;
if (temp > l) {
l = temp;
System.out.format("length:%d start:%d end:%d\n", l, c1Idx,
c3Idx - 1);
}
return l;
}
/**********test********/
@Test
public void testGetLongestSubStringWith2Chars() {
String s = "";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 0);
s = null;
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 0);
s = "abaaab";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 4);
s = "abcaaabbb";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 6);
s = "aaaaabbbbbcdeff";
Assert.assertTrue(getLongestSubStringWith2Chars(s) == 10);
}

Q*a2011-03-17 07:03

30 楼

string LongestMostTwoSubString(string s) {
printf("s.size():%dn", s.size());
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
for (;;) {
while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (--charCounts[s[start]] != 2) ++start;
++start;
++end;
}
return s.substr(maxStart, maxLen);
}
int main() {
string ss[] = {"", "abcdefgh", "abcdefghabcdefgh", "
abcdefghabcdefghabcdefghijklmnopqrst"};
for (auto s: ss) {
printf("%sn", LongestMostTwoSubString(s).c_str());
}
return 0;
}

【在 c**z 的大作中提到】

: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？

t*i2011-03-17 07:03

31 楼

不错，这个一改就可以适用于任何 N 个的情况

【在 Q*****a 的大作中提到】

: string LongestMostTwoSubString(string s) {
: printf("s.size():%dn", s.size());
: // assume char in s are all ASCII, otherwise we can unsigned char and
: 256 slots
: vector charCounts(128, 0);
: int maxStart = 0;
: int maxLen = 0;
: int start = 0, end = 0;
: for (;;) {
: while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;

m*k2011-03-17 07:03

32 楼

sally216 的简洁，一改就可以适用于任何 N 个的情况

【在 t*******i 的大作中提到】

: 不错，这个一改就可以适用于任何 N 个的情况

s*n2011-03-17 07:03

33 楼

re

【在 m*****k 的大作中提到】

: sally216 的简洁，一改就可以适用于任何 N 个的情况

p*n2011-03-17 07:03

34 楼

sally 的写法要扫2遍，快index一遍，慢index一遍, 但可以扩展到n个letter.
其他算法有的只要扫一遍。

Q*a2011-03-17 07:03

35 楼

这个偶审题错误，原题是要求如同aaaaabbb这样最多不超过两个不一样的字符构成的子
串，我理解成如abcdabcd这种每个字符出现最多不超过两次。代码没有sally216的简洁
，不过个人习惯解这种区间问题的时候这么写了。顺便鄙视一下买买提的发文超时，居
然没有在session里保存，辛苦敲了半天的东西都没了。telnet时代就有的功能居然都
没实现。
string LongestMostTwoCharsSubString(string s) {
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
int uniqCharCounts = 0;
for (;;) {
for (;end < s.size(); ++end) {
if (++charCounts[s[end]] == 1) ++uniqCharCounts;
if (uniqCharCounts > 2) break;
}
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (uniqCharCounts > 2) {
if (--charCounts[s[start]] == 0) {
--uniqCharCounts;
break;
}
++start;
}
++start;
++end;
}
return s.substr(maxStart, maxLen);
}

【在 t*******i 的大作中提到】

: 不错，这个一改就可以适用于任何 N 个的情况

o*s2011-03-17 07:03

36 楼

这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
挪动i指针往后吧。
比如说aabbcd，应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
先移动i到b，这样res变成3了

【在 s******6 的大作中提到】

: 就是两个指针+一个计数的，假设是string是 acsii
: int longestSubstr(string s) {
: int count[256];
: memset(count, 0, sizeof(count));
: int cnt = 0;
: int i = 0;
: int res = 0;
: for(int j=0; j: count[s[j]] ++;
: if(count[s[j]] == 1) cnt ++;

m*k2011-03-17 07:03

37 楼

aabb时res就是4了

【在 o****s 的大作中提到】

: 这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
: 挪动i指针往后吧。
: 比如说aabbcd，应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
: 先移动i到b，这样res变成3了

j*32011-03-17 07:03

38 楼

哈哈我最喜欢这种题

c*z2011-03-17 07:03

39 楼

given a string ,return the longest substring that contains at most two
characters.
该咋写？

t*e2011-03-17 07:03

40 楼

Two pointer traversal + memorization. 这类题目是不是都差不多这样

f*w2011-03-17 07:03

41 楼

和leetcode的Longest Substring Without Repeating Characters类似
两个指针start和end，从左往右扫一遍，如果start和end之间符合条件就++end，否则
就++start

l*a2011-03-17 07:03

42 楼

我去替你onsite吧

【在 c**z 的大作中提到】

: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？

v*l2011-03-17 07:03

43 楼

我电面的时候问了这题，记录一下那个turning point 就好

M*M2011-03-17 07:03

44 楼

类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
unordered_map 记录这2个char最后出现的index。
string findsubstring(string s) {
if(s.empty()) {
return string();
}
queue que;
unordered_map map;
int maxlen = 0, maxindex=0, index=0;
for(int i=0; iif(map.find(s[i])==map.end()) {
if(que.size()==2) {
if(i-index>maxlen) {
maxlen = i-index;
maxindex = index;
}
//update que and map
char c=que.front();
que.pop();
index = map[c]+1;
map.erase(c);
}
map[s[i]] = i;
que.push(s[i]);
} else {
map[s[i]] = i;
}
}
if(s.size()-index>maxlen) {
maxlen = s.size()-index;
maxindex = index;
}
return s.substr(maxindex, maxlen);
}

i*u2011-03-17 07:03

45 楼

如果问你一个character你就会，问两个就不会了？是不是第二天就被据了：）
开个玩笑啊别怒

j*d2011-03-17 07:03

46 楼

at most two
characters.。什么意思？2个不一样的？aaaaab算longest是么？

s*r2011-03-17 07:03

47 楼

这题啥意思都没看懂，lz题目没写清楚吧？

a*e2011-03-17 07:03

48 楼

没看懂， string 里除了字符都是空格？

【在 c**z 的大作中提到】

: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？

w*t2011-03-17 07:03

49 楼

这个空间复杂度高了，会要求你不用额外数据结构来解决。
这题 corner case多

【在 M*****M 的大作中提到】

: 类似找longest substring without duplicates. 用queue记录2个已经出现的char，用
: unordered_map 记录这2个char最后出现的index。
: string findsubstring(string s) {
: if(s.empty()) {
: return string();
: }
: queue que;
: unordered_map map;
: int maxlen = 0, maxindex=0, index=0;
: for(int i=0; i

y*a2011-03-17 07:03

50 楼

int longestTwoCharWindow(String s) {
if (s.length()==0) return 0;
char c1=s.charAt(0),c2=c1;
int ct=1,ml=1,rec=1;
for (int l=0,r=1;rif (ct==1)
if (s.charAt(r)==c1)++rec;
else {++ct;rec=1;c2=s.charAt(r);}
else if (ct==2)
if (s.charAt(r)==c1){rec=1;}
else if (s.charAt(r)==c2){++rec;}
else {l=r-rec;rec=1;c1=c2;c2=s.charAt(r);}
ml=Math.max(ml, r-l);
}
return ml;
}

p*n2011-03-17 07:03

51 楼

Space O(1)
Time O(n)
// Given a string, return the longest substring that contains at most // two
characters.
// solution: scan the string and update the first and second letter's last
occurrence
// indices, and update the solution's start index.
int FindLength(const string& input) {
if (input.size() <= 2) {
return input.size();
}

int solu_start = 0;
int first_end, second_end;
char first = input[0];
char second;
int curr = 1;
while (curr < input.size() && input[curr] == first) {
curr++;
}
if (curr == input.size()) {
return input.size();
} else {
first_end = curr - 1;
second = input[curr];
second_end = curr;
}

int solution = curr - solu_start + 1;
while (curr < input.size() - 1) {
curr++;
if (input[curr] == first) {
first_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else if (input[curr] == second) {
second_end = curr;
solution = (curr - solu_start + 1) > solution ?
(curr - solu_start + 1) : solution;
} else { // look back to last curr
if (input[curr - 1] == first) {
solu_start = second_end + 1;
second = input[curr];
second_end = curr;
} else {
solu_start = first_end + 1;
first = input[curr];
first_end = curr;
}
}
}
return solution;
}
int main() {
string input1 = "aabcdeffzzeee";
string input2 = "ababa";
string input3 = "ababacccccc";
cout << "solution length == "<< FindLength(input3) << endl;
return 0;
}

i*d2011-03-17 07:03

52 楼

Space O(1), Time O(n)
public int maxLength(String s){
if (s.isEmpty()) return 0;
int diffCharIndex = -1, currentLength = 1, maxLength = 1;
for (int i = 1; i < s.length(); i++)
{
if (s.charAt(i) != s.charAt(i-1))
{
if (diffCharIndex == -1 || s.charAt(i) == s.charAt(
diffCharIndex)) {
currentLength++; diffCharIndex = i - 1; }
else { currentLength = i - diffCharIndex; diffCharIndex = i-
1; }
}
else currentLength++;
if (currentLength > maxLength) maxLength = currentLength;
}
return maxLength;
}

a*y2011-03-17 07:03

53 楼

int FindLongsetTwoLetterSubstr(const std::string& str) {
int max_len = 0;
int curr_len = 0;
int n = str.size();
if (n == 0) {
return 0;
}
char letters[2];
letters[0] = str[0];
int i = 0;
int last_pos = 0;
for (; i < n; ++i) {
if (i != 0 && str[i] != str[i - 1]) {
letters[1] = str[i];
last_pos = i;
break;
}
}
int org_pos = 0;
for (; i < n; ++i) {
if (str[i] != str[i - 1]) {
if (str[i] != letters[0] && str[i] != letters[1]) {
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
curr_len = i - last_pos;
org_pos = last_pos;
last_pos = i;
if (str[org_pos] == letters[0]) {
letters[1] = str[i];
} else {
letters[0] = str[i];
}
} else {
last_pos = i;
}
}
}
curr_len = i - org_pos;
if (curr_len > max_len) {
max_len = curr_len;
}
return max_len;
}

Q*a2011-03-17 07:03

54 楼

string LongestMostTwoSubString(string s) {
printf("s.size():%dn", s.size());
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
for (;;) {
while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (--charCounts[s[start]] != 2) ++start;
++start;
++end;
}
return s.substr(maxStart, maxLen);
}
int main() {
string ss[] = {"", "abcdefgh", "abcdefghabcdefgh", "
abcdefghabcdefghabcdefghijklmnopqrst"};
for (auto s: ss) {
printf("%sn", LongestMostTwoSubString(s).c_str());
}
return 0;
}

【在 c**z 的大作中提到】

: given a string ,return the longest substring that contains at most two
: characters.
: 该咋写？

t*i2011-03-17 07:03

55 楼

不错，这个一改就可以适用于任何 N 个的情况

【在 Q*****a 的大作中提到】

: string LongestMostTwoSubString(string s) {
: printf("s.size():%dn", s.size());
: // assume char in s are all ASCII, otherwise we can unsigned char and
: 256 slots
: vector charCounts(128, 0);
: int maxStart = 0;
: int maxLen = 0;
: int start = 0, end = 0;
: for (;;) {
: while (end < s.size() && ++charCounts[s[end]] <= 2) ++end;

m*k2011-03-17 07:03

56 楼

sally216 的简洁，一改就可以适用于任何 N 个的情况

【在 t*******i 的大作中提到】

: 不错，这个一改就可以适用于任何 N 个的情况

s*n2011-03-17 07:03

57 楼

re

【在 m*****k 的大作中提到】

: sally216 的简洁，一改就可以适用于任何 N 个的情况

p*n2011-03-17 07:03

58 楼

sally 的写法要扫2遍，快index一遍，慢index一遍, 但可以扩展到n个letter.
其他算法有的只要扫一遍。

Q*a2011-03-17 07:03

59 楼

这个偶审题错误，原题是要求如同aaaaabbb这样最多不超过两个不一样的字符构成的子
串，我理解成如abcdabcd这种每个字符出现最多不超过两次。代码没有sally216的简洁
，不过个人习惯解这种区间问题的时候这么写了。顺便鄙视一下买买提的发文超时，居
然没有在session里保存，辛苦敲了半天的东西都没了。telnet时代就有的功能居然都
没实现。
string LongestMostTwoCharsSubString(string s) {
// assume char in s are all ASCII, otherwise we can unsigned char and
256 slots
vector charCounts(128, 0);
int maxStart = 0;
int maxLen = 0;
int start = 0, end = 0;
int uniqCharCounts = 0;
for (;;) {
for (;end < s.size(); ++end) {
if (++charCounts[s[end]] == 1) ++uniqCharCounts;
if (uniqCharCounts > 2) break;
}
int len = end - start;
if (len > maxLen) {
maxStart = start;
maxLen = len;
}
if (end == s.size()) break;
while (uniqCharCounts > 2) {
if (--charCounts[s[start]] == 0) {
--uniqCharCounts;
break;
}
++start;
}
++start;
++end;
}
return s.substr(maxStart, maxLen);
}

【在 t*******i 的大作中提到】

: 不错，这个一改就可以适用于任何 N 个的情况

o*s2011-03-17 07:03

60 楼

这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
挪动i指针往后吧。
比如说aabbcd，应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
先移动i到b，这样res变成3了

【在 s******6 的大作中提到】

: 就是两个指针+一个计数的，假设是string是 acsii
: int longestSubstr(string s) {
: int count[256];
: memset(count, 0, sizeof(count));
: int cnt = 0;
: int i = 0;
: int res = 0;
: for(int j=0; j: count[s[j]] ++;
: if(count[s[j]] == 1) cnt ++;

m*k2011-03-17 07:03

61 楼

aabb时res就是4了

【在 o****s 的大作中提到】

: 这个解法我觉得有问题啊，应该是一旦发现cnt++ > 2, 先update res的值吧，然后再
: 挪动i指针往后吧。
: 比如说aabbcd，应该是一碰到c，就先update res=4，按照sally216给的，碰到c，就
: 先移动i到b，这样res变成3了

j*32011-03-17 07:03

62 楼

哈哈我最喜欢这种题

f*t2011-03-17 07:03

63 楼

// given a string ,return the longest substring that contains at most two
characters.
string twoChar(const string &s) {
if (s.empty()) {
return "";
}
char a, b;
int na = 0, nb = 0;
int left = 0;
int res = 0;
int pos = -1;
for (int right = 0; right < s.size(); ++right) {
if (0 < na && a == s[right]) {
++na;
} else if (0 < nb && b == s[right]) {
++nb;
} else if (na == 0) {
++na;
a = s[right];
} else if (nb == 0) {
++nb;
b = s[right];
} else {
if (res < na + nb) {
res = na + nb;
pos = left;
}
while (na > 0 && nb > 0) {
if (s[left] == a) {
--na;
} else {
--nb;
}
++left;
}
--right;
}
}
if (res < na + nb) {
res = na + nb;
pos = left;
}
return string(s.begin() + pos, s.begin() + pos + res);
}