题目：

  1. 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
  3. 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
  7. 示例 1：
  9. 输入：n = 12
  10. 输出：5
  11. 示例 2：
  13. 输入：n = 13
  14. 输出：6
  17. 限制：
  19. 1 <= n < 2^31
  20. 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

方法一 暴力求解：

我们可以将这个问题简化为，给我一个数字，我去判断这个数字里出现了多少个1，就是依次除以10,100,1000等来看每个位数上的数字是否是1，那么这个求解算法的时间复杂度应该是：首先一层循环，从1计数到n 是O(N)，然后一层循环O(logn)级别的，差不多是O(nlogn)

方法二 优化一下

注意到这一题里，我们其实判断的时候，有很多重复的判断，例如判断21这个数字的时候，1-10 和 11-20 这里面的个位数中出现1的次数都被重复计算，所以我们可以怎么优化呢，首先，我们判断输入数字的数量级，是百位（3）还是千位（4）还是万位（5）还是k位。
我们可以计算得到 个位数循环中（0-9），每轮包含1个1 。十位循环中（0-99），每轮包含 个位循环10+110（10 11 ….19），百位循环中（0-999） 包含了 十位循环10 + 110*10（100,101….199）

在求解了每位循环之后，我们需要单独特殊处理一下最前面那一位的数字，因为可能会涉及到1的存在
如果是1 开头，那么包含了（0-999） 以及（1000-1xxx）之间的1
这个问题可以转换为一个递归求解的问题，而且考虑到时间优化可以增加暂存空间来保存关键位的包含1的数字数。

方法三 学习他人最优

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
大佬的思路是统计每个位上出现的1的次数，确实比我的更巧妙一点

代码

  1. class Solution {
  2. public:
  3.     int countDigitOne(int n) {
  4.         // mulk 表示 10^k
  5.         // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
  6.         // 但为了让代码看起来更加直观，这里保留了 k
  7.         long long mulk = 1;
  8.         int ans = 0;
  9.         for (int k = 0; n >= mulk; ++k) {
  10.             ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
  11.             mulk *= 10;
  12.         }
  13.         return ans;
  14.     }
  15. };

复杂度分析

O(logn)