233. Number of Digit One
老规矩,上来先暴力破解,一眼看上去非常简单,1分钟写出答案,最后Time Limit Exceeded.

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            res += cal_digit(i);
        }
        return res;
    }
private:
    int cal_digit(int n){
        int cnt = 0;
        while(n)
        {
            if(n % 10 == 1)
                cnt++;
            n /= 10;
        }
        return cnt;
    }
};

运行结果:

36 / 40 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago

这种题需要分析1出现的规律(实际上对其它数字道理一样),否则暴力破解运行时间超时。

class Solution {
public:
    int countDigitOne(int n) {
        int counter = 0;
        for(long long i = 1;i <= n;i *= 10)
        {
            long long divider = i * 10;
            counter += (n / divider) * i + min(max(n % divider - i + 1,0LL),i);
        }
        
        return counter;
    }
};

运行结果:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number of Digit One.
Memory Usage: 6.5 MB, less than 5.58% of C++ online submissions for Number of Digit One.

官方详细解法:
number of digit one solution
这里有一点值得注意的是,min max如果两个参数类型不一致会提示错误:no matching function for call to min/max