1からnのこのn個の整数の10進数の表現の中で1の出現の回数を求めます
1450 ワード
http://www.cnblogs.com/GoAhead/archive/2012/05/28/2521415.html
たとえば12を入力すると、1から12までの整数に1を含む数字が1、10、11、12で、1は全部で5回表示されます.分析:これは広く伝わるgoogle面接問題です.
簡単な方法は、与えられた位置に基づいて分析することです.
個位に1の個数=n/10+(個位=0,0;個位>1,1;個位=1,低0位+1);//後ろのは皆さんが以前空だった時、1の数です.
10ビットビットに1の個数=n/100*10+(10ビット=0,0;10ビット>1,10;10ビット=1、下位1ビット+1)が現れる.
百位出現1の個数=n/1000*100+(百位=0,0;百位>1100;百位=1、低2位+1);
など
アルゴリズムの複雑さはビット数にのみ関係する
アルゴリズムの説明:
(1)与えられた正の整数aの桁数を求め、N,numと仮定して1の個数を保存する
(2)またp=a,num+=p/10 i*10 i-1;(i=1...N-1);
(3)p=a/10 i-1とする.p=p%10,if(p==1) num+=a%10i-1+1;if(p>1) num+=10i-1;(i=1....N)
(4)printf(num);
手動で解く:
125
ビット=12+1
10ビット=10+10
100ビット=0+26
59個1
アルゴリズム:
たとえば12を入力すると、1から12までの整数に1を含む数字が1、10、11、12で、1は全部で5回表示されます.分析:これは広く伝わるgoogle面接問題です.
簡単な方法は、与えられた位置に基づいて分析することです.
個位に1の個数=n/10+(個位=0,0;個位>1,1;個位=1,低0位+1);//後ろのは皆さんが以前空だった時、1の数です.
10ビットビットに1の個数=n/100*10+(10ビット=0,0;10ビット>1,10;10ビット=1、下位1ビット+1)が現れる.
百位出現1の個数=n/1000*100+(百位=0,0;百位>1100;百位=1、低2位+1);
など
アルゴリズムの複雑さはビット数にのみ関係する
アルゴリズムの説明:
(1)与えられた正の整数aの桁数を求め、N,numと仮定して1の個数を保存する
(2)またp=a,num+=p/10 i*10 i-1;(i=1...N-1);
(3)p=a/10 i-1とする.p=p%10,if(p==1) num+=a%10i-1+1;if(p>1) num+=10i-1;(i=1....N)
(4)printf(num);
手動で解く:
125
ビット=12+1
10ビット=10+10
100ビット=0+26
59個1
アルゴリズム:
1#include <stdio.h>
2 int test(int a){
3 int i;
4 int num=1;
5 if(a==0)
6 return 1;
7 for(i=1;i<=a;i++)
8 num*=10;
9 return num;
10 }
11 int function(int a){
12 int p=a;
13 int num=0;
14 int N=0;
15 int temp;
16 int i;
17 while(p!=0)
18 {
19 p=p/10;
20 N++;
21 }
22 p=a;
23 for(i=1;i<=N;i++){
24 num+=p/test(i)*test(i-1);
25 temp=a/test(i-1)%10;
26 if(temp==1)
27 num+=a%test(i-1)+1;
28 if(temp>1)
29 num+=test(i-1);
30 }
31 return num;
32 }
33
34 void main(){
35 printf("%d
",function(88888));
36 }