题目描述

输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。

例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5 次。

样例
输入： 12
输出： 5

算法1

(暴力枚举) $O((logn)^2)$

外层循环次数为n的位数，logn，内层循环 logn次

C++ 代码

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if(n == 0) return 0;
        int res = 0;
        vector<int> num;
        for(int i = n; i; i /= 10){
            num.push_back(i % 10);
        }

        for(int i = num.size() - 1; i >= 0; --i){
            int left = 0, right = 0, t = 1;
            for(int j = num.size() - 1; j > i; --j) left = left * 10 + num[j];   //计算12345，例如此次计算3这一位，left计算的是0-11,一共12个不同的数
                                                                            //当i = 1时，left计算结果为0，
            for(int j = i - 1; j >= 0; --j){
                right = right * 10 + num[j];
                t *= 10;
            } 

            res += t * left;
            if(num[i] == 1){
                res += right + 1;
            }
            else if(num[i] > 1){
                res += t;
            }
        }
        return res;

    }
};