题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
解题思路：例如21345分成两段1-1345 1346-21345
1346-21345
1）10000-19999 共出现10000次(10^4)对于五位数，不一定都是10000次，例如10000-12345次数为2345+1（所以应该分为最高位>1（1*10^(长度-1)）和最高位==1两种情况（除去最高位+1））
2）1346-21345分成 1346-11345 11346-21345两段，每一端剩下4位数，选择其中一位为1，其余三位0-9中任选 2*4*10^3
3）1-1345 可以递归求得
1 class Solution { 2 public: 3 int NumberOf1Between1AndN_Solution(int n) 4 { 5 if(n <= 0) 6 return 0; 7 char strN[50]; 8 sprintf(strN,"%d",n); 9 return NumberOf1(strN); 10 } 11 int NumberOf1(const char *strN) 12 { 13 //空或者不是正确数字 14 if(!strN || *strN <'0' || *strN >'9'|| *strN == ' ') 15 return 0; 16 int first = *strN - '0'; 17 unsigned int length = static_cast<unsigned int>(strlen(strN)); 18 if(length == 1 && first == 0) 19 return 0; 20 if(length ==1 && first >0) 21 return 1; 22 //计算最高位1的个数 23 int numFirstDigit = 0; 24 if(first > 1) 25 numFirstDigit = PowerBase10(length -1);//如果最高位大于1，那么最高位1的个数1*10^(长度-1) 26 else if(first == 1) 27 numFirstDigit = atoi(strN + 1) + 1;//除去最高位+1 28 //求除了最高位为1之外数字位中1的数目 29 int numOtherDigit = first * (length-1) * PowerBase10(length-2);//最高位*(除去最高位的位数)*10的(除去最高位-1)的次幂 30 //求1-1345 31 int numRecursive = NumberOf1(strN + 1); 32 return numFirstDigit + numOtherDigit + numRecursive; 33 } 34 int PowerBase10(unsigned int n) 35 { 36 int result = 1; 37 for(unsigned i = 0;i<n;i++) 38 result *=10; 39 return result; 40 } 41 };