题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        //abcdef 判断c=1的个数：1. ab从00~ab-1，那么def任取，所以是ab*1000
        //                      2. ab=ab，if c=0的时候，个数为0
        //                      3. ab=ab，if c=1的时候，0~def 个数为def+1的时候   
        //                      4. ab=ab，if c>1的时候， def任取， 个数为1000
        if(!n) return n;

        //利用vector存储每一个位数
        vector<int> number;
        while(n) number.push_back(n % 10), n /= 10;
        int res = 0;

        //for循环遍历每一位是否为1的情况
        for(int i = number.size() - 1; i >= 0; i--)
        {
            //left 代表ab， right代表def，t表示def的进制数，如上面的1000
            auto left = 0, right = 0, t = 1;
            for(int j = number.size() - 1; j > i; j--) left = left * 10 + number[j];
            for(int j = i - 1; j >= 0; j--) right = right * 10 + number[j], t *= 10;

            //确定了ab 和 def后，分情况讨论c的情况

            //第一种
            res += left * t;

            //第二种 0个1 不用写

            //第三种
            if(number[i] == 1) res += right + 1;
            else if(number[i] > 1) res += t;

        }

        return res;
    }
};

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla