[数据结构与算法]数字1的个数——每日一题第五天

老规矩，先看题目：
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。n <= 2的九次方
例如：16 answer = 9；
解：1 、10 、 11 、 12、 13 、14 、15 、16
注意11里面有两个1。
来源：力扣（LeetCode）
应该理解了，下面看题解

1、暴力解
枚举所有小于n的数，再对每个数里的1做统计。代码：

class Solution {
    public int countDigitOne(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int count = 0;
            int num = i;
            while (num != 0) {
                // 从个位数开始一位一位的和1比较
                if (num % 10 == 1) {
                    count++;
                }
                num /= 10;
            }
            ans += count;
        }
        return ans;
    }
}

显然，太复杂，题目中n最大为2的九次方。计算过程耗时太长，不可取，也不是优秀的程序猿采用的方法。

2、计数模拟
举例：n = 54321，要求的就是把每一位上出现1的次数加起来，就是答案，不如我们拿百位举例，百位上如果要有1，那就必须在区间 [–100,54100] 内，并且，100~199，百位都是1，都满足条件，所以由乘法定律可得有54×100个数百位上是1，同时，扣除54000，还有321，百位上也有1，所以最后答案应该是（54+1）× 100个1在百位上。
千位上同理，应该有（5+1）×1000个1。
以此类推，看代码：

class Solution {
public:
    int countDigitOne(int n) {
        long long _k = 1;//10的k次方
        int ans = 0;//记录总的有多少个1
        for(int k = 0;_k <= n;++k)
        {        
            ans += (n / (_k * 10)) * _k + min(max(n % (_k * 10) - _k + 1, 0LL), _k);
            _k *= 10;//位数增加
        }
        return ans;
    }
};

还有其他解题办法，例如递归、动态规划，不过都是基于第二种办法的公式来的，就不再写了，在剑指offer里有原题，有兴趣可以去看看。

我是Pico。