【微软面试题】请计算出1的个数
原题目：
给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。
例如：
N=2，写下1，2。这样只出现了1个"1"
N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样"1"的个数是5
请写出一个函数，返回1到N之间出现"1"的个数，比如 f(12)=5
大家发散下，看看到底有多少种算法吧。注意复杂度O(∩_∩)O
[解决办法]
我这个程序是输出从1到N，所有的数字的个数。包括1的个数。但是这个程序现在计算0的个数是不正确的。现在确保思路没有问题。
#include<iostream>#include<cmath>using namespace std;struct T{ int bit[10];};void plus(T& a,const T& b,const int k){ for(int i=0;i<10;i++) a.bit[i]+=b.bit[i]*k;}int main(){ int i,j,k,r,w,z,n,mask; T a[10]; T ans; for(i=0;i<10;i++){ k=n=i-2>0?i-2:0; for(j=0;j<n;j++) k=k*10+8; if(i>1)a[i].bit[0]=k*10+9; else a[i].bit[0]=0; for(j=1;j<=9;j++) a[i].bit[j]=i*pow(10,i-1); } while(cin>>n && n){ for(i=0;i<10;i++)ans.bit[i]=0; mask=100000000;//10^9 i=9; while(n/mask==0){ mask/=10; i--; } z=0; while(n){ i--; k=n/mask; n=n%mask; mask/=10; if(k==0){ z++; continue; } if(z!=0){ if(mask==0)ans.bit[0]+=z*k; else ans.bit[0]+=z*k*mask*10+n; z=0; } plus(ans,a[i],k); for(j=1;j<k;j++) if(mask)ans.bit[j]+=mask*10-1; ans.bit[k]+=n; for(j=1;j<=k;j++) ans.bit[j]++; ans.bit[0]+=i*k; r=0; w=9; for(j=i-2;j>0;j--){ r+=w*j; w=w*10; } ans.bit[0]+=r*k; } for(i=0;i<10;i++) cout<<ans.bit[i]<<endl; cout<<endl; } return 0;}
[解决办法]
//效率最低的一种算法：O(n^2)
#include <iostream>#include <string>int main(){ int num = 0; cout << "Please input a dec num:" ; cin >> num; int total = 0; for(int i = 1; i <= num; i++) { int value = i; while(value > 0) { int single = value % 10; if(single == 1) total ++; value /= 10; } } cout << num << " include 1 total :" << total << endl; return 0;}
[解决办法]