剑指 Offer 43 1～n 整数中 1 出现的次数

概述

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

https://leetcode.com/problems/number-of-digit-one/

这是一道 Hard 题。

暴力遍历

注意，0 <= n <= 10^9，必超时。

每个数字 O(logn)，n 个数字因此总的时间复杂度 O(nlogn)。

分段 + 递归

https://leetcode.com/problems/number-of-digit-one/discuss/64426/Easy-to-understand-C%2B%2B-0ms-solution-with-detailed-explanation

对于数字 2356，f(0001, 2356) = f(0001, 0999) + f(1000, 1999) + f(2000, 2356)

其中：

1. f(0001, 0999) = f(001, 099) * 10 + 100
2. f(1000, 1999) = 1000
3. f(2000, 2356) = f(001, 356)

对于数字 1356，f(0001, 1356) = f(0001, 0999) + f(1000, 1356)

搞了好久啊，烦死了。

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0) return 0;
        if(n <= 9) return 1;
        int c = 0;
        int d = digitNum(n);
        int firstDigit = n / (pow(10, d - 1));
        if (firstDigit == 1) {
            c += fn9(d - 1);
            cout << c << endl;
            c += n - pow(10, d - 1) + 1;
            cout << c << endl;
        } else {
            c += firstDigit * fn9(d - 1);
            cout << c << endl;
            c += pow(10, d - 1);
            cout << c << endl;
        }
        c += countDigitOne(n % int(pow(10, d - 1)));
        cout << c << endl;
        return c;
    }
    
    int fn9(int n) {  // 9999... (n=4)
        if (n == 1) return 1;
        return fn9(n-1) * 10 + pow(10, n-1);
    }
    
    int digitNum(int n) {
        int i = 0;
        while (n > 0) {
            i ++;
            n /= 10;
        }
        return i;
    }
};

Links: sword-offer-43

未经允许，禁止转载，本文源站链接：https://iamazing.cn/