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

标签: 剑指 Offer 发布于:2022-02-26 19:59:12 编辑于:2022-02-26 20:56:13 浏览量:889

概述

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;
    }
};

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