题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
解题思路：
分析每一位出现等于0、等于1、大于1的情况。
case1 ：为0的情况：
对于250这个数字，个位为0时，个位可能出现1的情况是25种，如1、 11、 21 ... 101、 111、121 ... 201、211... 241 ，其实可以看出是0前面的25*1的结果。
对于205这个数字，十位为0时，那么十位可能出现1的情况为20种，如10、 11、 12 ...110、111、112..119 ，其实可以看出是0前面的2*10的结果。
case2： 大于1的情况：
对于22这个数字，个位大于1时，个位可能出现1的情况有3种，如1、 11、 21，其实可以看出是前面的2*1+1的结果。
对于224这个数字，十位大于1时，十位可能出现1的情况有30种，如10、11、12...19、110、111、112... 119、210、211、212...219，其实可以看出是前面的(2+1)*10的结果。
case3：等于1的情况：
对于21这个数字，个位等于1时，个位出现1的情况有3种，如1、11、21，其实可以看做是2*1+(0+1)
对于212这个数字，十位等于1时，十位出现1的情况有23种，如10、11、12...19、110、111、112...119、210、211、212，其实可以看做2*10+(2+1)的结果。2*10的2表示212在百位上可以取值0—1，而(2+1)中则表示当百位为2，十位为1时，后面的个位可取的范围为0—2一共3个数字。
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
int vsum = 0;
int nn = n;
int Md = 1;
while(n != 0){
int pv = n%10;
int prev = n/10;
Md *= 10;
n /= 10;
if(pv == 0){
vsum += (nn/Md) * Md/10;
}else if(pv == 1){
if(Md == 10){
//特判当个位为1的情况
vsum += (nn/Md)* Md/10 + 1;
}else{
vsum += (nn/Md)* Md/10 + (nn%(Md/10)+1);
}
}else{
vsum += ((nn/Md) + 1) * Md/10;
}
}
return vsum;
}
};