给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | class Solution {public: int NumberOf1Between1AndN_Solution (int n) { if(n<=0 )return 0; if(n<10 )return 1; char strN [50]; sprintf (strN ,"%d",n); //这里保证进来的数字都是大于 等于10 的 int first =*strN- '0'; int length =strlen (strN ); int num1 ; if(first >1) num1 =pow (10, length-1); else num1 =atoi (strN +1)+ 1; int num2 =first *(length- 1)*pow (10, length-2); int num3 =0; for(int i=1;i<=atoi (strN +1); i++) num3 +=NumberOf1( i); return num1+ num2+num3; } int NumberOf1 (int n) { int number =0; while(n) { if(n%10 ==1) number ++; n =n /10; } return number; } }; |
在个位出现1的个数=n/10+(个位=0,0；个位>1,1;个位=1，低0位+1)；
十位位出现1的个数=n/100*10+(十位=0,0；十位>1,10,；十位=1，低一位+1)；
百位出现1的个数=n/1000*100+(百位=0,0；百位>1,100;百位=1，低两位+1)；
等等
算法的复杂度仅仅和位数有关