【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。对每一位求个总和即可。代码如下：

1. class Solution {
2. public:
3.   int countDigitOne(int n) {
4.     vector<int> a;
5.     while (n) a.push_back(n % 10), n /= 10;
6.     reverse(a.begin(), a.end());
7.     int res = 0;
8.     for (int i = 0; i < a.size(); i++) {
9.       int d = a[i];
10.       int l = 0, r = 0, p = 1;
11.       for (int j = 0; j < i; j++) l = l * 10 + a[j];
12.       for (int j = i + 1; j < a.size(); j++) {
13.         r = r * 10 + a[j];
14.         p = p * 10;
15.       }
17.       if (!d)
18.         res += l * p;
19.       else if (d == 1)
20.         res += l * p + r + 1;
21.       else
22.         res += (l + 1) * p;
23.     }
25.     return res;
26.   }
27. };

复制代码

时间复杂度                                   O                         (                                              log                               ⁡                                      2                                  n                         )                              O(\log^2n)                  O(log2n)，空间                                   O                         (                         log                         ⁡                         n                         )                              O(\log n)                  O(logn)。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。