爆笑！山东吃妇科药的刘常山，参加选秀抓狂表演！ (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

爆笑！山东吃妇科药的刘常山，参加选秀抓狂表演！ (转载)

爆笑！山东吃妇科药的刘常山，参加选秀抓狂表演！ (转载)# Joke - 肚皮舞运动

x*02012-10-03 07:10

1 楼

Given a string, find the longest substring that contains at most 2 distinct
characters.
e.g. “ababcbcbaaabbdef”
baaabb (6) ← Find this one!
bcbcb (5)
Alg:
1) scan , if find a distinct char, I
void find_longest_sub_string( char arr[ ], char result[ ] ){
int length_different_char = 0;
int max_len_substring = 0;
int current_len_substring = 0;
int i ;
int j ;
for ( i = 0 , j = 0 ; arr[i] != ‘\0’; i++, j++){
strcpy( &arr[i], &result[j] );
if( is_occured_before( result) != 0 ){
result[j+1] = arr[i+1];
length_different_char++;
current_len_substring++;
}
else{
result[j+1] = arr[i+1];
current_len_substring++;
}
if( length_different_char ==3 ){
current_len_substring-- ;
length_different_char = 0;
}
if( max_len_substring < current_len_substring){
max_len_substring = current_len_string;
current_len_substring = 0;
j = 0;
}

q*12012-10-03 07:10

2 楼

【以下文字转载自 Military 讨论区】
发信人: qx001 (qx), 信区: Military
标题: 爆笑！山东吃妇科药的刘常山，参加选秀抓狂表演！
发信站: BBS 未名空间站 (Wed Oct 3 10:34:41 2012, 美东)

O*i2012-10-03 07:10

3 楼

lz很厉害，乒乓和编程都强。
“我曾是名专业的乒乓球运动员，小学时与邓亚萍为同门师姐妹，并有幸受很优秀的教
练指导。”

a*o2012-10-03 07:10

4 楼

这个代码有问题吧

distinct

【在 x********0 的大作中提到】

: Given a string, find the longest substring that contains at most 2 distinct
: characters.
: e.g. “ababcbcbaaabbdef”
: baaabb (6) ← Find this one!
: bcbcb (5)
: Alg:
: 1) scan , if find a distinct char, I
: void find_longest_sub_string( char arr[ ], char result[ ] ){
: int length_different_char = 0;
: int max_len_substring = 0;

p*22012-10-03 07:10

5 楼

又是two pointers和sliding window的题目。

p*22012-10-03 07:10

6 楼

这类题我有总结。LeetCode上边很多，做好LeetCode这题一点问题也没有。
http://blog.sina.com.cn/s/blog_b9285de20101gs89.html

l*a2012-10-03 07:10

7 楼

如二爷所述，的确是走的two pointers的套路。
string findLongest(string s){
int maxLen = 0;
int startIndex = 0;
int endIndex = 0;
int i = 0;
int j = 0;
unordered_map m;
while(j < s.length()){
if(m.size() < 2 || m.find(s[j]) != m.end()){
m[s[j]]++;
j++;
if(maxLen < j - i){
maxLen = j - i;
startIndex = i;
endIndex = j;
}
}else if(m.find(s[j]) == m.end()){
while(m.size() == 2){
if(m.find(s[i]) != m.end() && m[s[i]] != 0){
m[s[i]]--;
if(m[s[i]] == 0)
m.erase(s[i]);
i++;
}
}
}
}
return s.substr(startIndex, endIndex - startIndex);
}

t*22012-10-03 07:10

8 楼

can use two auxiliary variables to record the two chars already appeared,
thus saving the time spent in is_occured_before( result); otherwise, is_
occured_before can be O(N) in worst case...
my humble opinion --- is it right?

t*22012-10-03 07:10

9 楼

what is the complexity of computing m.size() ? Thanks!

t*h2012-10-03 07:10

10 楼

void foo(char* s) {
if(!*s) return;
int end[2], start[2], chars[2];
int maxlen=2,maxstart=0,i,n=strlen(s),p;
if(n<3) {printf("%s\n",s);}
start[0]=0;end[0]=0;chars[0]=s[0];
if(s[1]==s[0]) {
start[1]=0;end[1]=1;chars[1]=chars[0];
} else {
start[1]=1;end[1]=1;chars[1]=s[1];
}
for(i=2;iif(s[i]!=chars[0]&&s[i]!=chars[1]) {
p=end[0]chars[p]=s[i];
start[p]=i;
start[1-p]=end[p]+1;
end[p]=i;
} else {
p=(chars[0]==s[i])?0:1;
end[p]=i;
}
int start1=MIN(start[0],start[1]);
int end1=MAX(end[0],end[1]);
if(end1-start1+1>maxlen) {
maxlen=end1-start1+1;
maxstart=start1;
}
}
char* r=strndup(s+maxstart,maxlen);
printf("%s\n", r);
free(r);
}

distinct

【在 x********0 的大作中提到】

p*22012-10-03 07:10

11 楼

你一次看你代码，钛膜拜了。

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

: void foo(char* s) {
: if(!*s) return;
: int end[2], start[2], chars[2];
: int maxlen=2,maxstart=0,i,n=strlen(s),p;
: if(n<3) {printf("%s\n",s);}
: start[0]=0;end[0]=0;chars[0]=s[0];
: if(s[1]==s[0]) {
: start[1]=0;end[1]=1;chars[1]=chars[0];
: } else {
: start[1]=1;end[1]=1;chars[1]=s[1];

t*h2012-10-03 07:10

12 楼

哈哈说得多练得少写出来像天书

【在 p*****2 的大作中提到】

:
: 你一次看你代码，钛膜拜了。

p*22012-10-03 07:10

13 楼

看来大牛要出山了

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

: 哈哈说得多练得少写出来像天书

t*h2012-10-03 07:10

14 楼

正拜读您老的博克没读完之前不敢出哇

【在 p*****2 的大作中提到】

:
: 看来大牛要出山了

l*b2012-10-03 07:10

15 楼

响应2爷号召，有题目就练，贴个我的：
public String getLongestSubstring(String s) {
if (s == null || s.length() == 0) return "";
if (s.length() <= 2) return s;

char a = '\0';
char b = '\0';
int aLastIndex = -1;
int bLastIndex = -1;
int left = 0;
int right = 0;
String result = "";
while (right < s.length()) {
char c = s.charAt(right);
if (a == '\0') {
a = c;
} else if (b == '\0' && a != c) {
b = c;
}

if (a == c) {
aLastIndex = right;
} else if (b == c) {
bLastIndex = right;
} else {
left = Math.min(aLastIndex, bLastIndex) + 1;
if (aLastIndex > bLastIndex) {
b = c;
bLastIndex = right;
} else {
a = c;
aLastIndex = right;
}
}

if (right - left + 1 > result.length()) {
result = s.substring(left, right + 1);
}

right++;
}
return result;
}

d*e2012-10-03 07:10

16 楼

扩展下，最多K个不同字符：
def find_longest_substr(s, k):
d = {}
i = j = 0
begin = end = 0
while j < len(s):
if s[j] in d:
d[s[j]] += 1
j += 1
else:
if len(d) < k:
d[s[j]] = 1
j += 1
else:
if j - i > end - begin:
begin = i
end = j
while len(d) == k:
d[s[i]] -= 1
if d[s[i]] == 0: del d[s[i]]
i += 1
return s[begin:end]

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

: 响应2爷号召，有题目就练，贴个我的：
: public String getLongestSubstring(String s) {
: if (s == null || s.length() == 0) return "";
: if (s.length() <= 2) return s;
:
: char a = '\0';
: char b = '\0';
: int aLastIndex = -1;
: int bLastIndex = -1;
: int left = 0;

l*a2012-10-03 07:10

17 楼

Constant

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

: what is the complexity of computing m.size() ? Thanks!

p*22012-10-03 07:10

18 楼

膜拜python。最近用ruby，python快忘光了。

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

: 扩展下，最多K个不同字符：
: def find_longest_substr(s, k):
: d = {}
: i = j = 0
: begin = end = 0
: while j < len(s):
: if s[j] in d:
: d[s[j]] += 1
: j += 1
: else:

h*g2012-10-03 07:10

19 楼

我也来一个。发现这个题目其实现场写不容易，细节很容易忽略。算法很简单，可还是
写了半个小时，怎么办？
void f(char*s, char*dest){
int set[256]={0};
int i=0, len=strlen(s);
int count=0, maxWin=0;
int l=0, r=len; //local window edges
int ll, rr; //global window edges

while(iif(count<2 || set[s[i]]){
r=i;
set[s[i]]++;
i++;
if(!set[s[i]]) count++;
if(maxWinmaxWin=r-l+1;
ll=l;
rr=r;
}
continue;
}
//else new letter appears:
if(maxWinmaxWin=r-l+1;
ll=l;
rr=r;
}
set[s[i]]++;
r++;
i++;
//move left edge:
while(--set[s[l++]]!=0);
}

if(!maxWin) sprintf(dest, "")
else{
for(int i=ll; i<=rr; i++){
dest[i-ll]=s[i];
}
}
}

h*g2012-10-03 07:10

20 楼

void parityDivision(int *A, int len){
int evenhead=0, odd=0;
while(evenheadif(A[evenhead]%2==0)
break;
evenhead++;
}
odd=evenhead+1;
while(oddif(A[odd]%2){ //odd number
int currentOdd=A[odd];
for(int i=odd-1; i>=evenhead; i--){
A[i+1]=A[i];
}
A[evenhead]=currentOdd;
evenhead++;
}
odd++;
}
}

s*n2012-10-03 07:10

21 楼

争取最简洁奖。很久不写C聊。
char* ls(const char* input, char* result){
int start = 0; int end = 0;
char first = 0; char second = 0;
char* p = input;
int i = 0;
int rs = 0; int re = 0;
which(*p){
if (*p != first || *p != second){
first= second;
second = *p;
start = i - 1 < 0 ? 0 : i - 1;
second = i;
}

if (*p == first){
swap (first, second);
end ++;
}

if (*p == second)
end++;

if (re - rs < start -end)
{ re = end; rs = start;}
p++; i++;
}
return strncpy (input + rs, result, re - rs);
}

M*n2012-10-03 07:10

22 楼

响应党的号召，也贴一个：
static int substr(char[] arr) {
String s=new String(arr);
if(arr.length<=2)
return arr.length;
int n=arr.length;

int init=0;
int pre=0;
int cur=0;

int maxLen=Integer.MIN_VALUE;
while(curcur++;

if (cur==n)
return n;
char c1=arr[init];
char c2=arr[cur];

pre=cur;

for(cur=cur+1;curif(arr[cur]==c1){
c1=c2;
c2=arr[cur];
pre=cur;
}
else if(arr[cur]!=c2) {
if(cur-init>maxLen)
maxLen=cur-init;
c1=c2;
c2=arr[cur];
init=pre;
pre=cur;
}
}
if(cur-init>maxLen)
maxLen=cur-init;
return maxLen;

}

M*n2012-10-03 07:10

23 楼

请问大牛，第一个wihile貌似多余，请问如何修改？

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

: 响应党的号召，也贴一个：
: static int substr(char[] arr) {
: String s=new String(arr);
: if(arr.length<=2)
: return arr.length;
: int n=arr.length;
:
: int init=0;
: int pre=0;
: int cur=0;

c*u2012-10-03 07:10

24 楼

如果at most 不是2个而是多个，是否要用hashset?

你一次看你代码，钛膜拜了。

【在 p*****2 的大作中提到】

:
: 膜拜python。最近用ruby，python快忘光了。

w*x2012-10-03 07:10

25 楼

string getLongset2Dist(const char* p)
{
if (p == NULL || *p == 0)
return "";
string strRet;
int rec[256] = { 0 };
int nCount = 0;
const char* pPrev = p;
const char* pIter = p;
while (*pIter != 0)
{
if (rec[*pIter] == 0)
nCount++;
rec[*pIter]++;
if (nCount > 2 && pIter - pPrev > strRet.length())
strRet = string(pPrev, pIter);
while (nCount > 2)
{
rec[*pPrev]--;
if (rec[*pPrev] == 0)
nCount--;
pPrev++;
}
pIter++;
}
if (pIter - pPrev > strRet.length())
strRet = string(pPrev, pIter);
return strRet;
}