题目描述 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
思路： 1）首先算出 9，99，999，9999,…….之前的所有1个数，放在 base 中 2）把整数分解放在 number 里 3）从最低为开始计算1的个数，如果目前的数为1计算公式为： total = 前一数量级1的个数 + 1后的整数 + 1 + 前一次的 total 比如 139 ，则 total = 99中1的个数 + 39 + 1 +前一次的 total。 如果不为1，计算公式为： total = （当前数字-2）*base[j-1]+2*base[j-1]+k+total
class Solution { public: int NumberOf1Between1AndN_Solution(int n) { int num = 0; int number[20]; int base[20]; int i = 0; int total = 0; int k = 10; int flag; base[0] = 1; memset(number, 0, sizeof(number)); for(int i = 1; i <= 20; i++) { base[i] = base[i-1]*8+k+base[i-1]*2; k*=10; } cout<<endl; while(10 <= n) { number[i++] = n%10; n = n/10; } number[i] = n; num = number[0]; total = flag = number[0] == 0 ? 0:1; k = 10; for(int j = 1; j <= i; j++) { if(number[j] == 0) { continue; } if(number[j] == 1) { total = base[j-1] + num +1+total; } else { total = (number[j]-2)*base[j-1]+2*base[j-1]+k+total; } num = k*number[j] + num; k = k*10; } return total; } };