Google面试题 (转载)

[milan817]

答案...

[大花狗上树]

比较笨的办法，不推荐使用，用此方法去参加考试，保证不会被录取，嘎嘎。

代码：

/*******************************/ /* Q:WWWDOT-GOOGLE=DOTCOM */ /* A:777589-188103=589486 */ /* 777589-188106=589483 */ /*******************************/ #include "stdio.h" void main() { int w,d,o,t,c,m,g,l,e; for (w = 1;w<=9;w++) for (d = 1;d<=9;d++) for (o = 0;o<=9;o++) for (t = 0;t<=9;t++) for (c = 0;c<=9;c++) for (m = 0;m<=9;m++) for (g = 1;g<=9;g++) for (l = 0;l<=9;l++) for (e = 0;e<=9;e++){ if (w!=d && w!=o && w!=t && w!=c && w!=m && w!=g && w!=l && w!=e) if (d!=o && d!=t && d!=c && d!=m && d!=g && d!=l && d!=e) if (o!=t && o!=c && o!=m && o!=g && o!=l && o!=e) if (t!=c && t!=m && t!=g && t!=l && t!=e) if (c!=m && c!=g && c!=l && c!=e) if (m!=g && m!=l && m!=e) if (g!=l && g!=e && l!=e){ int google=g*100000+o*10000+o*1000+g*100+l*10+e; int dotcom=d*100000+o*10000+t*1000+c*100+o*10+m; int wwwdot=w*100000+w*10000+w*1000+d*100+o*10+t; if(wwwdot==(google+dotcom)){ printf ("%d%d%d%d%d%d-",w,w,w,d,o,t); printf ("%d%d%d%d%d%d=",g,o,o,g,l,e); printf ("%d%d%d%d%d%d\n",d,o,t,c,o,m); } } } }

[ Last edited by 大花狗上树 on 2005-11-21 at 00:59 ]

[大花狗上树]

第三题
1
1个1，11
2个1，21
1个2，1个1，1211
1个1，1个2，2个1，111221

下一行应该是
3个1，2个2，1个1 312211

代码：

#include <iostream> #include <string> #include <sstream> using namespace std; main() { string s = "1"; cout << s << endl; for( int N=0; N<10; ++N ) { ostringstream os; for( size_t i=0; i<s.length(); ++i ) { size_t n = 1; char c = s[i]; for( ; i<s.length() && s[i+1]==c; ++i ) ++n; os << n << c; } s = os.str(); cout << s << endl; } return 0; }

[大花狗上树]

对第一题代码作了一定优化，速度大大提高，但总感觉还会有更好的方法。

代码：

/*******************************/ /* Q:WWWDOT-GOOGLE=DOTCOM */ /* A:777589-188103=589486 */ /* 777589-188106=589483 */ /*******************************/ #include "stdio.h" #include "conio.h" void main() { int w,d,o,t,c,m,g,l,e; for (w = 1;w<=9;w++) for (d = 1;d<=9;d++){ if (w==d) continue; for (o = 0;o<=9;o++) { if (o==d||o==w) continue; for (t = 0;t<=9;t++) { if (t==d||t==w||t==o) continue; for (c = 0;c<=9;c++) { if (c==d||c==w||c==o||c==t) continue; for (m = 0;m<=9;m++) { if (m==d||m==w||m==o||m==t||m==c) continue; for (g = 1;g<=9;g++) { if (g==d||g==w||g==o||g==t||g==c||g==m) continue; for (l = 0;l<=9;l++) { if (l==d||l==w||l==o||l==t||l==c||l==m||l==g) continue; for (e = 0;e<=9;e++){ if (e==d||e==w||e==o||e==t||e==c||e==m||e==g||e==l) continue; int google=g*100000+o*10000+o*1000+g*100+l*10+e; int dotcom=d*100000+o*10000+t*1000+c*100+o*10+m; int wwwdot=w*100000+w*10000+w*1000+d*100+o*10+t; if(wwwdot==(google+dotcom)){ printf ("%d%d%d%d%d%d-",w,w,w,d,o,t); printf ("%d%d%d%d%d%d=",g,o,o,g,l,e); printf ("%d%d%d%d%d%d\n",d,o,t,c,o,m); } } } } } } } } } getchar(); }

[ Last edited by 大花狗上树 on 2005-11-21 at 13:32 ]

[大花狗上树]

有这样一个函数，对于任意整数n，都能返回写出0到n之间出现“1”的个数。例如，f（13）=6。请注意f（1）=1，那么下一个能实现f（n）=n的最大数字是什么？

代码：

/*****************************************/ /* Result: */ /* f(199981)=199981 */ /*****************************************/ #include <stdio.h> #include <conio.h> void main() { int n = 2; int num = 1; int num_tmp,one; bool founded = false; while(!founded){ one=0; num_tmp=n; while(num_tmp > 0){ if(num_tmp % 10 == 1) one++; num_tmp = num_tmp / 10; } num = num + one; if(num == n) break; else n++; } printf("f(%d)=%d",n,n); getchar(); }

[大花狗上树]

再次优化第一题，用递归算法求解。

代码：

/*******************************/ /* Q:WWWDOT-GOOGLE=DOTCOM */ /* A:777589-188103=589486 */ /* 777589-188106=589483 */ /*******************************/ #include <stdio.h> void getans(int num[], int n_tmp) //通过递归调用对num_0_9数组进行组合排序 { int tmp; int w,d,o,t,g,l,e,c,m,wwwdot,google,dotcom; if(n_tmp == 1){ w = num[0]; d = num[1]; o = num[2]; t = num[3]; g = num[4]; l = num[5]; e = num[6]; c = num[7]; m = num[8]; wwwdot = w*111000 + d*100 + o*10 + t; google = g*100100 + o*11000 + l*10 + e; dotcom = d*100000 + o*10010 + t*1000 + c*100 + m; //其中的M和E的值可以互换，但不允许第一位是0。 if(w!=0 && g!=0 && d!=0) if((wwwdot-google==dotcom) || (wwwdot-(google-e+m) == (dotcom-m+e))) printf("%d - %d = %d\n",wwwdot,google,dotcom); } else{ for(int i = 0; i < n_tmp; i++){ tmp=num[i]; num[i]=num[n_tmp-1]; num[n_tmp-1]=tmp; getans(num, n_tmp-1); tmp=num[i]; num[i]=num[n_tmp-1]; num[n_tmp-1]=tmp; } } } void main() { int n = 10; int num_0_9[]={0,1,2,3,4,5,6,7,8,9}; getans(num_0_9, n); }

[ Last edited by 大花狗上树 on 2005-11-22 at 00:16 ]

[酒旗风]

这么长的程序
太有耐心了

[羽扇纶巾]

强了么！
就是看不懂。

[那时花开]

大花狗同志的算法让我想起用美国太空总署卫星追踪一只鸟

[leiyuss]

这个叫做学以致用~