题目描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

解法：
从低到高遍历数字的每一位，分三种情况讨论
1.cur==0:统计高位数字倍数，如20，个位数上的1出现了2次
2.cur==1:在1的基础上加上了低位的个数，如13，十位上的一出现次数位 3+1次（10-13）
3.else

#include<vector>

using namespace  std;
class Solution {
public:
    int countDigitOne(int n) {
        int cnt = 0;
        long long i =1;
        //统计每一位的出现次数
        while(n/i){//n/i是当前数，根据当前数乘倍数可以恢复出原来的数
            int high = n/(10*i);
            int cur = (n/i)%10;
            int low =  n-(n/i)*i;
            if(cur==0){
                cnt+=(high*i);
            }else if(cur==1){
                cnt+=(high*i+low+1);//从0开始
            }else{
                cnt+=(high+1)*i;
            }
            i*=10;
        }
        return cnt;
    }
};