[算法]Google的面试题

yongjian

Another algorithm in C. Someone else might have already thought similar. The main idea is to use memorization technology to keep track of all previous found 1's and calc how many 1's the current number carries. Algorithm to calc the current 1's are simply. O(kn) time where k is the digits of the number.

2. #define UL unsigned long
3. UL MAX=1111111112;
5. int main() {
6.   UL i, k, p=0;
7.   for(i = 1; i <= MAX; i++) {
8.     k = i;
9.     while(1) {
10.       if(k > 0 && k < 10) {
11.         if(k == 1) p++;
12.         break;
13.       } else if(k >= 10) {
14.         if(k%10 == 1) p++;
15.         k /= 10;
16.       }
17.     }
18.     if(p == i) printf("%d\n", p);
19.   }
20. }

复制代码

./counting_number_2  327.36s user 0.49s system 99% cpu 5:29.01 total

yongjian

Another algorithm in C. Someone else might have already thought similar. The main idea is to use memorization technology to keep track of all previous found 1's and calc how many 1's the current number carries. Algorithm to calc the current 1's are simply. O(kn) time where k is the digits of the number.

1. 
   
2. #define UL unsigned long
   
3. UL MAX=1111111112;
   
4. 
   
5. int main() {
   
6.   UL i, k, p=0;
   
7.   for(i = 1; i <= MAX; i++) {
   
8.     k = i;
   
9.     while(1) {
   
10.       if(k > 0 && k < 10) {
    
11.         if(k == 1) p++;
    
12.         break;
    
13.       } else if(k >= 10) {
    
14.         if(k%10 == 1) p++;
    
15.         k /= 10;
    
16.       }
    
17.     }
    
18.     if(p == i) printf("%d\n", p);
    
19.   }
    
20. }
    

复制代码

./counting_number_2  327.36s user 0.49s system 99% cpu 5:29.01 total

Mason_hou

今天看了一下大家的思路，好像方向不对阿，要提高这算法的效率，关键在于搜索的步长，而不是讨论怎么计算1的个数，大家在这里都只是想方设法提高计算1个数的效率而已。计算1个数的公式pointer 已经得出，这已经是最高效率的了。而且也证明了n的范围，这点很重要（虽然证明过程有些笔误）。
不过还有最关键的问题是搜索的步长，在这点上pointer的算法并非最好，不过也比普遍的递进好太多了。我也试着做了一些改进：

一、更改一下n的下界，
首先可以证明除1外最小n>5：
由pointer的公式有
f(an,an-1.....a0)=(an-1...a0)+1+f(10^n-1) + f(an-1,...,0) ,  an=1
又
f(an,an-1.....a0) ＝ (an...a0)
得
(an...a0)- (an-1...a0) = 1+f(10^n-1) + f(an-1,...,0)
-->
10^n = 1+n＊10^(n-1) + f(an-1,...,0) <= 2( 1+ n*10^(n-1))   ( 因 f(an-1,...,0)<=f(an,...,0), 且 (an-1...a0)可以为 0)
于是有 n> 5，编程可以直接跳到 n=1e5进行搜索。

二、提高搜索步长：
因假设一个数n长为 L，d = n－ f(n) 。
这里仅仅讨论d>0的情况。如果n增加能使d减少，则n至少固定含有一个'1'。并且在仅有一个1不变的情况下n每增加a，0<d-a<=d。基于这一思想，对于可能出现 L 个 '1'，pointer的算法保守得使用 d/L 作为增加的步长，但实际上可以动态设置。比较简单得就是原有的'1'的个数加上 d 的长度作为除数即可。

三、连续打印连续的10个数：
可以从公式证明在如果 n 是所求，且除个，十位仅有1个'1'，则连续的个十位由01－10都是所求。

程序：

2. #include<stdio.h>
3. #define __USE_ISOC99
4. #include<stdlib.h>
5. #define MAXNL  10 // It has been proofed that n<=8 and n_max = 1111111110
6. #define MAN_N 1111111111
7. long long tenpowers[MAXNL]= {1};// 10^i
8. long long rempowers[MAXNL]= {0};// remainder power: i*10^(i-1)
9. int remainders[MAXNL]={0};        //  remainders
11. // Suppose that n= a* 10^i+b, where i >0 and b<10^i.
12. // Then b_i = n- a*10^i, and b_num stores b_i.
13. long long b_num[MAXNL]={0};
15. int len=0; // length of n
17. long long countOnes(long long n)
18. {       
19.         int  i, j;
20.         long long ones_num=0;
21.         lldiv_t qr;       
22.         // initial
23.         len =0;
24.         qr.quot=n;
25.         // count len and set b_num
26.         while(qr.quot)        {
27.                 qr=lldiv(qr.quot, 10L);
28.                 remainders[len]=qr.rem;
29.                 if (len>0) { // set b_num
30.                         b_num[len]=b_num[len-1]+qr.rem*tenpowers[len];
31.                 }
32.                 else{
33.                         b_num[len]=qr.rem;
34.                 }
35.                 len++;
36.         }
37.         // count ones
38.         for(i=len-1; i>0; --i)        {
39.                 if(remainders[i]>1) {
40.                         ones_num+=tenpowers[i]+remainders[i]*rempowers[i];
41.                 }
42.                 else if(remainders[i]==1){
43.                         ones_num+=rempowers[i]+b_num[i-1]+1;
44.                 }
45.         }
46.         ones_num+=(remainders[i]>0)?1:0;
48.         return ones_num;
49. }
51. // count the number of one in remainders
52. int numOfOne() {
53.         int count=0,i;
54.         for (i=1;i<len;i++) { // ignore the first remainder
55.                 if ( 1 == remainders[i] ) {
56.                         count++;
57.                 }
58.         }
59.         return count;
60. }
62. // Print the adjoining ten number, each of who has only one '1' except the first one .
63. int printAdjTen( long long n, int n_num) {       
64.         int i;
65.         if (numOfOne() ==1) {                                       
66.                 for (i=0; i<9; i++) {       
67.                         printf("%4d: %lld\n", n_num++ ,++n);
68.                 }       
69.                 return 1;                               
70.         }
71.         return 0;       
72. }
74. // Get the length of one number
75. int getLen(long long n) {
76.         int len =0 ;
77.         for (len=0;len<MAXNL;len++) {
78.                 if ( n < tenpowers[len]) {
79.                         break;
80.                 }
81.         }               
82.         return len;
83. }
85. int main(int argc, char * argv[])
86. {
87.         long long ones_num,  diff; // numbers of '1' ; difference between n and ones_num
88.         int  i,n_num=1;
89.         int diff_len,step;
90.         long long  n=1;
91.         for(i=1;i<MAXNL;++i)         {
92.                 tenpowers[i]=tenpowers[i-1]*10L;
93.                 rempowers[i]=tenpowers[i-1]*i;
94.         }
95.         printf("%4d: %lld\n", n_num++ ,n);        // print '1'
96.         n = 1e5; // It has been proved that next n must be larger than 1e5
97.         while(n<MAN_N) { // searching
98.                 ones_num=countOnes(n);
99.                 diff=n-ones_num;
100.                 if(diff>len)        {
101.                         // set search step.
102.                         step=numOfOne();
103.                         if (step==0) {
104.                                 step = len-1;
105.                         }else {
106.                                 diff_len = getLen(diff); // get length of diff
107.                                 step = step+diff_len;
108.                                 if (step==len) {
109.                                         step--;
110.                                 }
111.                         }
112.                         n+=diff/step+1;
113.                 }else if(diff<0) {
114.                         n+=(-diff);
115.                 }else {
116.                         if(diff==0){
117.                                 printf("%4d: %lld\n", n_num++ ,n);                                                               
118.                                 if ( printAdjTen( n, n_num) ) {
119.                                         n+=9;
120.                                         n_num+=9;
121.                                 }
122.                         }                       
123.                         ++n;
124.                 }
125.          }
126.         return 0;
127. }

复制代码

Mason_hou

2.    1: 1
3.    2: 199981
4.    3: 199982
5.    4: 199983
6.    5: 199984
7.    6: 199985
8.    7: 199986
9.    8: 199987
10.    9: 199988
11.   10: 199989
12.   11: 199990
13.   12: 200000
14.   13: 200001
15.   14: 1599981
16.   15: 1599982
17.   16: 1599983
18.   17: 1599984
19.   18: 1599985
20.   19: 1599986
21.   20: 1599987
22.   21: 1599988
23.   22: 1599989
24.   23: 1599990
25.   24: 2600000
26.   25: 2600001
27.   26: 13199998
28.   27: 35000000
29.   28: 35000001
30.   29: 35199981
31.   30: 35199982
32.   31: 35199983
33.   32: 35199984
34.   33: 35199985
35.   34: 35199986
36.   35: 35199987
37.   36: 35199988
38.   37: 35199989
39.   38: 35199990
40.   39: 35200000
41.   40: 35200001
42.   41: 117463825
43.   42: 500000000
44.   43: 500000001
45.   44: 500199981
46.   45: 500199982
47.   46: 500199983
48.   47: 500199984
49.   48: 500199985
50.   49: 500199986
51.   50: 500199987
52.   51: 500199988
53.   52: 500199989
54.   53: 500199990
55.   54: 500200000
56.   55: 500200001
57.   56: 501599981
58.   57: 501599982
59.   58: 501599983
60.   59: 501599984
61.   60: 501599985
62.   61: 501599986
63.   62: 501599987
64.   63: 501599988
65.   64: 501599989
66.   65: 501599990
67.   66: 502600000
68.   67: 502600001
69.   68: 513199998
70.   69: 535000000
71.   70: 535000001
72.   71: 535199981
73.   72: 535199982
74.   73: 535199983
75.   74: 535199984
76.   75: 535199985
77.   76: 535199986
78.   77: 535199987
79.   78: 535199988
80.   79: 535199989
81.   80: 535199990
82.   81: 535200000
83.   82: 535200001
84.   83: 1111111110
86. real    0m0.006s
87. user    0m0.002s
88. sys     0m0.000s
90. model name      : Intel(R) Pentium(R) M processor 1.73GHz

复制代码

Mason_hou

比较pointer的算法，大概节省25％左右时间，以下是屏蔽输出各运行5000次的时间：
pointer：
real    0m24.951s
user    0m24.114s
sys     0m0.014s

my:
real    0m17.906s
user    0m17.316s
sys     0m0.008s

senmole

这个题我花了半天时间，就是一个排列组合的问题，用了一个递归做出来了，运行速度很快，几乎不用时间。

#include <stdio.h>

long fn(long);
int main(int argc, char *argv[])
{
        long num = atoi(argv[1]);
        long n = fn(num);
       
        printf("{0, ..., %ld}中共有%ld个1\n", num, n);
       
        return 0;
}

long fn(long num)
{
        long height_bit;        // 用存储最高位
        long low_bits;        // 存储最高位除外的低几位
        int bits;                // 用于存储num的位数
        long power;
        long t;
       
        if (num == 0)
                return 0;
        if (num < 10)
                return 1;
       
        height_bit = num;
        low_bits = 0;
        bits = 1;
        power = 1;
        t = 0;
        while (height_bit / 10) {
                low_bits += height_bit % 10 * power;
                height_bit /= 10;
                t = t * 10 + 9;
                power *= 10;
                bits++;
        }
       
        if (low_bits == t) {
                return (power + (height_bit + 1) * (power / 10) * (bits - 1));
        }
       
        return (fn((height_bit - 1) * power + t) + fn(low_bits) +
            low_bits+1);
}

senmole

Post by senmole;1842868
这个题我花了半天时间，就是一个排列组合的问题，用了一个递归做出来了，运行速度很快，几乎不用时间。

#include <stdio.h>

long fn(long);
int main(int argc, char *argv[])
{
        long num = atoi(argv[1]);
        long n = fn(num);
       
        printf("{0, ..., %ld}中共有%ld个1\n", num, n);
       
        return 0;
}

long fn(long num)
{
        long height_bit;        // 用存储最高位
        long low_bits;        // 存储最高位除外的低几位
        int bits;                // 用于存储num的位数
        long power;
        long t;
       
        if (num == 0)
                return 0;
        if (num < 10)
                return 1;
       
        height_bit = num;
        low_bits = 0;
        bits = 1;
        power = 1;
        t = 0;
        while (height_bit / 10) {
                low_bits += height_bit % 10 * power;
                height_bit /= 10;
                t = t * 10 + 9;
                power *= 10;
                bits++;
        }
       
        if (low_bits == t) {
                return (power + (height_bit + 1) * (power / 10) * (bits - 1));
        }
       
        return (fn((height_bit - 1) * power + t) + fn(low_bits) +
            low_bits+1);
}

修正：
上面有个错误，最后一句返回语句需要改成：
if (height_bit == 0) {
    return (fn((height_bit - 1) * power + t) + fn(low_bits) + low_bits + 1);
}
else {
    return (fn((height_bit - 1) * power + t) + fn(low_bits));
}

pking

都是夹高手啊

xgywd

/*这是一个计算从1数到n,1出现次数的程序，我的解法，从最高位开算，只算最高位能包含多少个
1，然后砍掉最高算次高，一直砍到最低位一切OK，不过需注意的是，出现某个位上有1和0的时候
计算1个数的方法和高于1有数不一样。因为只是计算其权位上的数，所以循环次数只是有几位数就循环几次，我感觉还是比较快的，不知道我这个新手怎么样，希望高手能指点*/


#include <iostream>
#include  <ctime>
using namespace std;

const int ten=10;

int  quan(long);                                        //计算一个数的位数，也就是这个数的最高权
int bit(long);                                                //计算一个数最高权上的数
long  sumhigh(long);                                        //把一个数的最高位砍掉（去掉最高位）
long pow(int x,int y);                                //计算一个数的正数次幂



int main()
{
               

        long a,b,c,high,d;
        int x,y,z;
       
        cout <<"请输入一个整数，我们将判断它包含的数中有多少个1：\n";
        cin >>a;
       
        d=a;                                                //d,用来存储a的值，以便下面运算的时候不受a的变化影响
        b=0;
        high=0;                                        //high用来存储一个数的绝对最高位
        for (long i=quan(a);i>0;--i)
                {
               
               
                if  (quan(a)<i)        y = 0 ;        //如果把a取权之后小于i,证明当前位置为零。
               
                else y= bit(a);                       
               
               
                if (y==1)
                        {
                        c=high*pow(ten,i-1)+sumhigh(a)+1;               
                        b=b+c;
                        }
               
               
                else if (y>1)
                        {
                        c=high*pow(ten,i-1)+pow(ten,i-1);
                        b=b+c;
                        }
                else if (y==0&&i!=1)
                        {
                        c=high*pow(ten,i-1);
                        b=b+c;
                        }
                else if(y==0&&i==1)
                        {
                        c=high;
                        b=b+c;
                        }
               
                high=d/pow(ten,i-1);
               
                if (y!=0)        a=sumhigh(a);
               
                }
       
        cout <<"包含1的个数有："<<b<<"个\n";
       
}


int quan(long x)
{
        bool a=true;
        int b=0;
        do
        {
        if (x<1)
                {
                a=false;
                }
                else
                {
                x=x/ten;
                b++;
                }
        }while(a);
return b;
}


int bit(long x)
{
        int a,b=1;
        do
        {
        if (x>=ten)
                {       
                x=x/ten;
                }
        else b=0;
        }while (b);
return x;
}


long sumhigh(long x)
{
        long a;
        a= x-bit(x)*pow(ten,quan(x)-1);
return a;
}


long pow(int x,int y)
{
        long a=1;
        if (y>0)
                {
                for (int i=0;i<y;++i)
                        {
                        a=a*x;
                        }
                }
        else if (y==0) a=1;
       
return a;
}

pointer

嗯, 很好----发现大部分人理解错了题, 你是少有的理解了的人.

Hand

Post by Mason_hou;1818060
今天看了一下大家的思路，好像方向不对阿，要提高这算法的效率，关键在于搜索的步长，而不是讨论怎么计算1的个数，大家在这里都只是想方设法提高计算1个数的效率而已。计算1个数的公式pointer 已经得出，这已经是最高效率的了。而且也证明了n的范围，这点很重要（虽然证明过程有些笔误）。
不过还有最关键的问题是搜索的步长，在这点上pointer的算法并非最好，不过也比普遍的递进好太多了。我也试着做了一些改进：

一、更改一下n的下界，
首先可以证明除1外最小n>5：
由pointer的公式有
f(an,an-1.....a0)=(an-1...a0)+1+f(10^n-1) + f(an-1,...,0) ,  an=1
又
f(an,an-1.....a0) ＝ (an...a0)
得
(an...a0)- (an-1...a0) = 1+f(10^n-1) + f(an-1,...,0)
-->
10^n = 1+n＊10^(n-1) + f(an-1,...,0) <= 2( 1+ n*10^(n-1))   ( 因 f(an-1,...,0)<=f(an,...,0), 且 (an-1...a0)可以为 0)
于是有 n> 5，编程可以直接跳到 n=1e5进行搜索。

二、提高搜索步长：
因假设一个数n长为 L，d = n－ f(n) 。
这里仅仅讨论d>0的情况。如果n增加能使d减少，则n至少固定含有一个'1'。并且在仅有一个1不变的情况下n每增加a，0<d-a<=d。基于这一思想，对于可能出现 L 个 '1'，pointer的算法保守得使用 d/L 作为增加的步长，但实际上可以动态设置。比较简单得就是原有的'1'的个数加上 d 的长度作为除数即可。

三、连续打印连续的10个数：
可以从公式证明在如果 n 是所求，且除个，十位仅有1个'1'，则连续的个十位由01－10都是所求。

程序：

1. 
   
2. #include<stdio.h>
   
3. #define __USE_ISOC99
   
4. #include<stdlib.h>
   
5. #define MAXNL  10 // It has been proofed that n<=8 and n_max = 1111111110
   
6. #define MAN_N 1111111111
   
7. long long tenpowers[MAXNL]= {1};// 10^i
   
8. long long rempowers[MAXNL]= {0};// remainder power: i*10^(i-1)
   
9. int remainders[MAXNL]={0};        //  remainders
   
10. 
    
11. // Suppose that n= a* 10^i+b, where i >0 and b<10^i.
    
12. // Then b_i = n- a*10^i, and b_num stores b_i.
    
13. long long b_num[MAXNL]={0};
    
14. 
    
15. int len=0; // length of n
    
16. 
    
17. long long countOnes(long long n)
    
18. {       
    
19.         int  i, j;
    
20.         long long ones_num=0;
    
21.         lldiv_t qr;       
    
22.         // initial
    
23.         len =0;
    
24.         qr.quot=n;
    
25.         // count len and set b_num
    
26.         while(qr.quot)        {
    
27.                 qr=lldiv(qr.quot, 10L);
    
28.                 remainders[len]=qr.rem;
    
29.                 if (len>0) { // set b_num
    
30.                         b_num[len]=b_num[len-1]+qr.rem*tenpowers[len];
    
31.                 }
    
32.                 else{
    
33.                         b_num[len]=qr.rem;
    
34.                 }
    
35.                 len++;
    
36.         }
    
37.         // count ones
    
38.         for(i=len-1; i>0; --i)        {
    
39.                 if(remainders[i]>1) {
    
40.                         ones_num+=tenpowers[i]+remainders[i]*rempowers[i];
    
41.                 }
    
42.                 else if(remainders[i]==1){
    
43.                         ones_num+=rempowers[i]+b_num[i-1]+1;
    
44.                 }
    
45.         }
    
46.         ones_num+=(remainders[i]>0)?1:0;
    
47. 
    
48.         return ones_num;
    
49. }
    
50. 
    
51. // count the number of one in remainders
    
52. int numOfOne() {
    
53.         int count=0,i;
    
54.         for (i=1;i<len;i++) { // ignore the first remainder
    
55.                 if ( 1 == remainders[i] ) {
    
56.                         count++;
    
57.                 }
    
58.         }
    
59.         return count;
    
60. }
    
61. 
    
62. // Print the adjoining ten number, each of who has only one '1' except the first one .
    
63. int printAdjTen( long long n, int n_num) {       
    
64.         int i;
    
65.         if (numOfOne() ==1) {                                       
    
66.                 for (i=0; i<9; i++) {       
    
67.                         printf("%4d: %lld\n", n_num++ ,++n);
    
68.                 }       
    
69.                 return 1;                               
    
70.         }
    
71.         return 0;       
    
72. }
    
73. 
    
74. // Get the length of one number
    
75. int getLen(long long n) {
    
76.         int len =0 ;
    
77.         for (len=0;len<MAXNL;len++) {
    
78.                 if ( n < tenpowers[len]) {
    
79.                         break;
    
80.                 }
    
81.         }               
    
82.         return len;
    
83. }
    
84. 
    
85. int main(int argc, char * argv[])
    
86. {
    
87.         long long ones_num,  diff; // numbers of '1' ; difference between n and ones_num
    
88.         int  i,n_num=1;
    
89.         int diff_len,step;
    
90.         long long  n=1;
    
91.         for(i=1;i<MAXNL;++i)         {
    
92.                 tenpowers[i]=tenpowers[i-1]*10L;
    
93.                 rempowers[i]=tenpowers[i-1]*i;
    
94.         }
    
95.         printf("%4d: %lld\n", n_num++ ,n);        // print '1'
    
96.         n = 1e5; // It has been proved that next n must be larger than 1e5
    
97.         while(n<MAN_N) { // searching
    
98.                 ones_num=countOnes(n);
    
99.                 diff=n-ones_num;
    
100.                 if(diff>len)        {
     
101.                         // set search step.
     
102.                         step=numOfOne();
     
103.                         if (step==0) {
     
104.                                 step = len-1;
     
105.                         }else {
     
106.                                 diff_len = getLen(diff); // get length of diff
     
107.                                 step = step+diff_len;
     
108.                                 if (step==len) {
     
109.                                         step--;
     
110.                                 }
     
111.                         }
     
112.                         n+=diff/step+1;
     
113.                 }else if(diff<0) {
     
114.                         n+=(-diff);
     
115.                 }else {
     
116.                         if(diff==0){
     
117.                                 printf("%4d: %lld\n", n_num++ ,n);                                                               
     
118.                                 if ( printAdjTen( n, n_num) ) {
     
119.                                         n+=9;
     
120.                                         n_num+=9;
     
121.                                 }
     
122.                         }                       
     
123.                         ++n;
     
124.                 }
     
125.          }
     
126.         return 0;
     
127. }
     

复制代码