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]

这个叫做学以致用~