剑指 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)。
分段 + 递归
对于数字 2356,f(0001, 2356) = f(0001, 0999) + f(1000, 1999) + f(2000, 2356)
其中:
- f(0001, 0999) = f(001, 099) * 10 + 100
- f(1000, 1999) = 1000
- 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