标题: 【Leetcode】233. Number of Digit One [打印本页] 作者: 徐锦洪 时间: 2024-8-8 00:39 标题: 【Leetcode】233. Number of Digit One 题目地点：
https://leetcode.com/problems/number-of-digit-one/description/
给定一个非负整数 n n n，求从 1 ∼ n 1\sim n 1∼n这些正整数中各个位统共有多少个 1 1 1。
先将 n n n的每一位求出来然后从左到右分列。接下来思量每一位为 1 1 1的小于便是 n n n的数有多少个。假设 n = a b c d e f g ‾ n=\overline{abcdefg} n=abcdefg，我们思量 d d d这一位，有多少个数能取 1 1 1。假如 d = 0 d=0 d=0，那么其左边的方案是 0 ∼ a b c ‾ − 1 0\sim \overline{abc}-1 0∼abc−1，右边的方案为 0 ∼ 999 0\sim 999 0∼999；假如 d = 1 d=1 d=1，那么除了上面那个方案之外，左边是可以取 a b c ‾ \overline{abc} abc的，而此时右边可以取 0 ∼ e f g ‾ 0\sim \overline{efg} 0∼efg；假如 d > 1 d>1 d>1，那么其左边的方案数是 0 ∼ a b c ‾ 0\sim \overline{abc} 0∼abc，右边的方案为 0 ∼ 999 0\sim 999 0∼999。对每一位求个总和即可。代码如下：
class Solution {
public:
int countDigitOne(int n) {
vector<int> a;
while (n) a.push_back(n % 10), n /= 10;
reverse(a.begin(), a.end());
int res = 0;
for (int i = 0; i < a.size(); i++) {
int d = a[i];
int l = 0, r = 0, p = 1;
for (int j = 0; j < i; j++) l = l * 10 + a[j];
for (int j = i + 1; j < a.size(); j++) {
r = r * 10 + a[j];
p = p * 10;
}
if (!d)
res += l * p;
else if (d == 1)
res += l * p + r + 1;
else
res += (l + 1) * p;
}
return res;
}
};
复制代码
时间复杂度 O ( log 2 n ) O(\log^2n) O(log2n)，空间 O ( log n ) O(\log n) O(logn)。