勤能補拙，Expter

# re: 一些筆試題（包括金山西山居筆試） 2008-12-22 23:31 second

問題2的算法1是不是有點問題：
其中b似乎沒有改變，一直是0
問題2的算法2是不是也有點問題：
while(i<len)循環中，如果str[i]='A',那么執行else總的b++，再返回while(i<len)，這時i仍然沒有改變，str[i]!='A'還是不成立還是執行else....
這樣就是一個死循環了  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-22 23:31 路過

樓主真雷人  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-23 09:45 guest

第二個題目很搞笑，如果只是移動一個字符的話，一次循環，如果是'A'后面的字符前移覆蓋那個'A'就可以了，覆蓋了多少個'A'，最后補多少個'A'，當然著個算法只是針對你這個題目而言的，不具備大的擴展性。  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-23 11:35 馬德里]

/我以為樓主有什么好一點的題呢,這樣的東西 還是自己偷著看比較好  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-25 08:24 nick

首先算法有誤：
if (str[a] != '0')
{
return; //如果最后一個字符不為'0'
}
這里肯定返回了，因為str[len-1]!=0, str[len]才等于0。

其次效率不高，因為如果A出現多次，算法1會有很多元素被拷貝多次，算法2 最后要做一次strcpy。

給出我的實現
void foo(char *str)
{
char *p = str;
// find the first 'A'
while (*p && *p!='A') p++;

if (*p==0)
return;

int count = 1;
char* dest = p; // first 'A' positon
p++;
char* src = p;

while (*p)
{
if (*p == 'A')
{
while (src != p)
{
*dest++=*src++;
}
count++;
src= p+1;
}
p++;
}

// copy the last part of the string
while(src != p)
{
*dest++ = *src++;
}

// write the 'A' to the end of the string
while (count)
{
*(p-count)='A';
count--;
}
}
  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-26 08:50 橙子

為什么要 strlen  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-28 13:45 nick

更好的實現：
void foo(char* str)
{
char* p = str;
while (*p && *p!='a') p++;

if (*p==0)
return;

char* dest = p;
p++;
char* src = p;
int c = 1;
while (*p)
{
if (*p == 'a')
{
c++;
p++;
}
else
{
*dest++=*p++;
}

}

while (c-->0)
{
*(--p)='a';
}
}  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2008-12-29 14:01 夢想飛揚

博主提供的算法1時間復雜度太高，算法2空間復雜度太高。
我寫了一個簡單的累計'A'值并覆蓋的算法，時間和空間復雜度都很低。
Deal3(char *str)
{
int len = strlen(str);
if (str[len-1] != '0')
return; //如果最后一個字符不為'0'

int k = 0;
for (int i=0; i<len; i++)
{
if (str[i] == 'A') //累計'A'的個數
k++;
else //覆蓋'A'
str[i-k] = str[i];
}

for (int i=0; i<k; i++)
str[len-1-i] = 'A';
}  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2009-01-13 15:50 flyound

void Deal(char * str)
{
if (str != NULL)
{
char * pBegin = str;
int len = strlen(str);
char * pEnd = str + len - 1;
while (pEnd != pBegin && (*pEnd == 'A' || *pEnd == 'a'))
{
pEnd --;
}
if (pEnd == pBegin)
{
return;
}

while (pBegin != pEnd)
{
if (*pBegin == 'A' || *pBegin == 'a')
{
char temp = *pEnd;
*pEnd = *pBegin;
char * pTemp = pBegin;
while (pTemp != (pEnd - 1))
{
* pTemp = *(pTemp + 1);
pTemp++;
}
*pTemp = temp;
pEnd --;
}
else
pBegin ++;
}
}
}  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2009-02-23 09:50 maosher

最后一個‘\0’是不也給移到中間了？  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2009-03-29 23:27 bruce wuu

夢想飛揚 的做法效率很高，佩服。
我這也有個做法，比較容易理解，多個先求字符串長度，可能效率低點。
void ReverseA(char *str)
{
int start=0;
int end=strlen(str)-1;
while(start<end)
{
if(str[start]!='A')
{
start++;
continue;
}
else
{
while(str[end]=='A'&&end>=0)
end--;
if(end>start)
{
char temp=str[start];
str[start]=str[end];
str[end]=temp;
}
else
break;
}
}
}  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2009-03-30 15:36 maosher

void Deal(char* str)
{
size_t n = strlen(str) ;
if (str[n] != '\0')
{
return;
}

int k = 0;
for (size_t i = 0; i != n+1; ++i)
{
if (str[i] == 'A')
{
++k;
}
else
{
str[i - k] = str[i];
}
}

for ( i = k; i != 0; --i)
{
str[n-i] = 'A';
}

}  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2010-03-08 17:55 試試其他的

int func(char *str)
{
char *p=str;

while(*str)
{
while(*str == 'A')
++str;

if(p != str)
*p=*str;

++p;
++str;

}

while(p != str)
{
*p='A';
++p;
}
}
  回復  更多評論   

# re: 一些筆試題（包括金山西山居筆試） 2010-07-23 23:21 luguo

在swap字符時候，使用^操作，而不是使用臨時變量...這個一般都是考點  回復  更多評論