DEV面试题目答案

题目1：翻转字符串和电梯测试算法最推荐的网址：我认为比较好的答案，呵呵：publicstaticstringReverse(stringstr){if(string.IsNullOrEmpty(str)){thrownewArgumentException(参数不合法);}StringBuildersb=newStringBuilder(str.Length);for(intindex=str.Length-1;index=0;index--){sb.Append(str[index]);}returnsb.ToString();}使用StringBuilder时，请注意，应在构造StringBuilder对象时指明初始容量，否则默认容量是16个字符，当由于追加字符而超出默认容量时，就会分配一个新的串缓冲区，大小是原缓冲区的两倍。电梯调度算法：问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？解法一：采用枚举的方法O(N^2)#includevector#includeiostreamusingnamespacestd;intmain(void){inti,j,n,person,temp,ans,layer;vectorintnum;while(cinn)//表示n层数{for(i=1;i=n;i++){cinperson;//表示第几层下电梯的人数num.push_back(person);}ans=-1;for(i=1;i=n;i++){temp=0;for(j=1;j=n;j++){if(i=j)temp+=num[j-1]*(i-j);elsetemp+=num[j-1]*(j-i);}if(ans==-1||tempans){ans=temp;layer=i;}}cout最少的层数：ansendl;cout在第layer层下endl;}return0;}解法二：线性算法O(n)1：首先通过一次扫描计算第一层下所有乘客爬电梯的层数总和2：然后通过每一层动态变化求得最后的结果比如现在在第i层所有乘客爬电梯的层数总和为temp在第i层下的有num1在第i层的有num2在第i层上的有num3则如果在第i-1层下temp+num3-num1-num2如果在第i+1层下temp+num1+num2-num3#includevector#includeiostreamusingnamespacestd;intmain(void){intnum1,num2,num3,i,n,ans,person,layer;vectorintnum;while(cinn){ans=0;num.push_back(0);num3=0;for(i=1;i=n;i++){cinperson;//表示第几层下电梯的人数num.push_back(person);ans+=num[i]*(i-1);num3+=num[i];}//初始化num2=num[1];num3-=num2;num1=0;layer=1;for(i=2;i=n;i++){if(num1+num2num3){ans=ans+num1+num2-num3;layer=i;num1+=num2;num2=num[i];num3-=num[i];//动态变化，编程技巧}elsebreak;//这里利用一个性质，最优的层数一定在中间，在他下面和上面的都比他要多}cout最少的层数：ansendl;cout在第layer层下endl;}}还有些网址你看看：1、、、其余的答案（个人感觉可以不用看了）：1.publicstaticstringReverse(stringstr)2.{3.if(string.IsNullOrEmpty(str))4.{5.thrownewArgumentException(参数不合法);6.}7.8.char[]chars=str.ToCharArray();9.intbegin=0;10.intend=chars.Length-1;11.chartempChar;12.while(beginend)13.{14.tempChar=chars[begin];15.chars[begin]=chars[end];16.chars[end]=tempChar;17.begin++;18.end--;19.}20.21.stringstrResult=newstring(chars);22.23.returnstrResult;24.}一、编写反转字符串的程序，要求优化速度、优化空间解法一：第一次看到这题目，想到最简单、最直觉的解法就是：遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环，即可，于是有了第一个解法：char*strrev1(constchar*str){intlen=strlen(str);char*tmp=newchar[len+1];strcpy(tmp,str);for(inti=0;ilen/2;++i){charc=tmp[i];tmp[i]=tmp[len–i-1];tmp[len–i-1]=c;}returntmp;}解法二指针直接操作即可，实现代码为：char*strrev2(constchar*str){char*tmp=newchar[strlen(str)+1];strcpy(tmp,str);char*ret=tmp;char*p=tmp+strlen(str)-1;while(ptmp){chart=*tmp;*tmp=*p;*p=t;--p;++tmp;}returnret;}显然上面的两个解法中没有考虑时间和空间的优化，一个典型的优化策略就是两个字符交换的算法优化，我们可以完全不使用任何外部变量即完成两个字符（或者整数）的交换，这也是一个很经典的面试题目。特别是一些嵌入式硬件相关编程中经常要考虑寄存器的使用，因此经常有不使用任何第三个寄存器即完成两个寄存器数据的交换的题目。一般有两个解法，对应这里的解法三和解法四。解法三的实现代码为：char*strrev3(constchar*str){char*tmp=newchar[strlen(str)+1];strcpy(tmp,str);char*ret=tmp;char*p=tmp+strlen(str)-1;while(ptmp){*p^=*tmp;*tmp^=*p;*p^=*tmp;--p;++tmp;}returnret;}解法四的实现代码为：char*strrev4(constchar*str){char*tmp=newchar[strlen(str)+1];strcpy(tmp,str);char*ret=tmp;char*p=tmp+strlen(str)-1;while(ptmp){*p=*p+*tmp;*tmp=*p-*tmp;*p=*p-*tmp;--p;++tmp;}returnret;}实际上我们还可以通过递归的思想来解决这个问题，思想很简单：每次交换首尾两个字符，中间部分则又变为和原来字符串同样的问题，因此可以通过递归的思想来解决这个问题，对应解法五的实现代码为：char*strrev5(/**//*const*/char*str,intlen){if(len=1)returnstr;chart=*str;*str=*(str+len-1);*(str+len-1)=t;return(strrev5(str+1,len-2)-1);}以下给出一个测试程序：ntmain(intargc,char*argv[]){char*str=hello;P(str);char*str2=strrev1(str);P(str2);char*str3=strrev2(str2);P(str3);char*str4=strrev3(str3);P(str4);char*str5=strrev4(str4);P(str5);char*str6=strrev5(str5,strlen(str5));P(str6);return0;}你就可以看到字符串hello和olleh交替输出了。说明：1）这里解法中没有认真考虑输入字符串的合法性和特殊长度（如NULL、一个字符等）字符串的处理；2）前4个算法不改变输入字符串的值，解法五修改了输入字符串。经典字符串反转算法voidReverse(chars[]){for(inti=0,j=strlen(s)-1;ij;++i,--j){charc=s[i];s[i]=s[j];s[j]=c;}}#关于a,b交换其它算法：a^=b;b^=a;a^=b;题目2：判断是不是回文推荐网址：1、、题目3、测试圆珠笔这个还是和基本的理论相关的，主要是考虑系统测试包含些什么测试功能测试：圆珠笔按下是否能正常写字，写字太重会不回缩回去，继续按会不会弹回去性能测试：圆珠心弹出弹回的快慢负载测试：一直按，弹簧能接受多少次的升缩兼容性测试：换其他的笔芯能不能行强度测试：用力过度会怎样可恢复性测试：如果弹簧压久了，是否可恢复等等GUI测试：笔的外观，拿笔的舒适性安全性：考虑对笔芯的保护，是否对使用者造成危害等等题目四：输出所有组合网址：1、、题目5、求最大公约数解法一、（通过取余数，输入非正常数字，会有bug）usingSystem;usingSystem.Collections.Generic;usingSystem.Text;namespaceExMaxGongYueShu{classMaxGongYueShu{publicfloatmaxGongYueShu(intn1,intn2){inttemp=Math.Max(n1,n2);n2=Math.Min(n1,n2);//n2中存放两个数中最小的n1=temp;//n1中存放两个数中最大的while(n2!=0){n1=n1n2?n1:n2;//使n1中的数大于n2中的数intm=n1%n2;n1=n2;n2=m;}returnn1;}staticvoidMain(string[]args){intn1=Convert.ToInt32(Console.ReadLine());intn2=Convert.ToInt32(Console.ReadLine());if(n1*n2!=0){MaxGongYueShum=newMaxGongYueShu();Console.WriteLine(m.maxGongYueShu(n1,n2));}else{Console.WriteLi