原文地址

题目描述

求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

算法

(数位计算) $O(logn)$

（1）计算每一位上的1出现的个数（从1到n）
（2） 总共循环 $logn$次，即n的位数

算法思路图解

时间复杂度是$O(logn)$：下面代码时间复杂度是 $O(log^2n)$，但其中一个是不会大于32的；另外我们还可以预处理left和right

空间复杂度是$O(logn)$：需要answer数组存数位信息

C++代码1

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if (!n) return 0;
        // n = 123 answer = [3, 2, 1]
        vector<int> answer; 
        while(n) answer.push_back(n % 10), n /= 10;

        int res = 0;
        for (int i = answer.size() - 1; i >= 0; i --) {
            int left = 0, right = 0, t = 1;
            for (int j = answer.size() - 1; j > i; j --) left = left * 10 + answer[j];
            for (int j = i - 1; j >= 0; j --) right = right * 10 + answer[j], t *= 10;

            res += left * t;
            if (answer[i] == 1) res += right + 1;
            if (answer[i] > 1) res += t;
        }

        return res;
    }
};

C++ 代码2 暴力做法

class Solution {
public:
    int countOne(int n) {
        int ans = 0;
        while(n) {
            if (n % 10 == 1) ans ++;
            n /= 10;
        }

        return ans;
    }
    int numberOf1Between1AndN_Solution(int n)
    {
        int res = 0;
        for (int i = 1; i <= n; i ++) {
            res += countOne(i);
        }
        return res;
    }
};