【剑指offer系列】43. 从1到n整数中1出现的次数

这里是剑指offer系列的延续，作者将利用C++实现继续完成该系列的学习，剑指offer，喜欢的话可以点赞关注＋收藏，加油更新中ing。

---

题目43. 从1到n整数中1出现的次数

输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。

例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5 次。

数据范围
1≤n≤10^9

样例

输入： 12
输出： 5
1
2

【题解】-- 按位数

一个数字： abcdef
求解 1 出现的次数即为各个位为1时其次数总和。(分别讨论各个位为 1 时，这个数字的变化范围，也就得到了总个数)

• 讨论 f 位，则其高位的范围可以为 0 ~ abcde-1，低位只能为 1
  f = 0 时，1, 11, 21, …, abcd(e-1)1。共计 abcde 个 1
  f = 1 时，abcde1 也符合，共计 abcde + 1
  f > 1 时，其高位范围可以为 0 ~ abcde
• 讨论 e 位，则其高位范围可以为 0 ~ abcd-1, 低位可以为 0 ~ 9
  e = 0, 10, 110, 210, …, abc(d-1)10。共计 abcd 个 0 ~ 9
  e = 1, abcd1f 也符合，共计 abcd 个 0 ~ 9 + 1 个 0 ~ f
  e > 1, 则其高位可以为 0 ~ abcd
  … 以此类推

复杂度分析：

一个n位数一共有ln(n) / ln(10)位, 所以复杂度是 O(logn)级。
1

C++代码实现：

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {

        int res = 0;
        for (int m = 1; m <= n; m *= 10) {
            int left = n / (10 * m);
            int right = n % m;
            res += left * m;
            if ((n / m) % 10 == 1) res += right + 1;
            if ((n / m) % 10 > 1) res += m;
            //cout << left << " " << right << " " << res << endl;
        } 
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指offer系列将后续持续更新，有帮助的话，欢迎点赞👍、收藏⭐️＋关注✌️哟~

---