勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一些笔试题(包括金山西山居笔试)

以前做过的笔试题,都是自己曾经做的


# include <iostream>
using namespace std;
#define Q(x)  x*x
int main()
{
    
int a =10;
    
int b = 2;
    
int c = 1;

    a 
/=Q(b+c)/Q(b+c);

    cout 
<< a <<endl;
    
return 0;
}


因为 宏Q(x) 不规范,
所以结果 很迷惑人

a   /=Q(b+c)/Q(b+c);的执行顺序是从右到左

tmp = Q(b+c)/Q(b+c) =  2+1*2+1 / 2+1*2+1 =2+2+0+2+1=7  没有对宏加括号是经常容易犯错!

a = a/tmp = 10/7 = 1

所以  a = 1;








-----------------------------------------

题目2
反转一个字符串(西山居笔试题):
题目:写一个函数,把一个以0字符结尾的字符串str中的'A'字符移到str的末尾!

分析:
1:以时间换空间   从后向前循环查找字符A
2:以空间换时间   一次循环

算法1代码:

void Deal(char *str )
{
    
int len = strlen(str);
    
int a= len-1,b=0;
    
if (str[a] != '0')
    
{
        
return;             //如果最后一个字符不为'0'
    }

    
while (a>=0)
    
{
        
if (str[a] == 'A')
        
{
            
int n = a;
            
while (n < len-b-1)
            
{
                str[n] 
= str[n+1];  //
                n++;
            }

            str[n] 
='A';
            b
++;           //b累加,表示有b个字符A
        }

        a
--;
    }

}




算法2:
void Deal(char *str )
{
    
int len = strlen(str);
    
int a= len-1,b=0,i=0,j=0;
    
if (str[a] != '0')
    
{
        
return;             //如果最后一个字符不为'0'
    }

    
char * tmp = new char[len+1];
    
while(i<len)
    
{
        
if(str[i] !='A')
            tmp[j
++= str[i];
        
else
            b
++;          //多少个字符A
        i++;
    }


    
while (j<len)
    
{
        tmp[j
++= 'A';
    }

    tmp[len] 
= '\0';
    strcpy(str,tmp);

    
    delete tmp;   
//释放空间
    tmp = NULL;
}




PS:因为是直接手写的。。所以难免有错误!
现在修改了,对不起各位。。。

posted on 2008-12-22 22:24 expter 阅读(5720) 评论(14)  编辑 收藏 引用 所属分类: 工作笔记面试笔记算法与数据结构

评论

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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理