勤能补拙，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字符时候，使用^操作，而不是使用临时变量...这个一般都是考点  回复  更多评论