题目描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

样例

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

算法分析

计数问题

假设给定某个数 $\overline {abcdefg}$，求 0 到 $\overline {abcdefg}$中数字 1 出现的个数，枚举该数所有位取 1 时的所有情况，假设当前枚举到 d 数字的那一位，需要对 d 数字是什么进行分类讨论

1、如果 d = 0 时，该数是 $\overline {abc\underline{0}efg}$，左边 left 可以取 0 ~ $\overline {abc}$，共有 $\overline {abc} + 1$ 种情况；右边可以取right 可以取 0 ~ 999，共有 $1000$ 种情况
2、如果 d = 1 时，该数是 $\overline {abc\underline{1}efg}$

• 前几位不是 abc 时，左边可以取 0 ~ $\overline {abc} - 1$，共有 $\overline {abc}$ 种情况；右边right 可以取 0 ~ 999，共有 $1000$ 种情况
• 前几位是 abc 时，左边可以取 $\overline {abc} $，共有 1 种情况；右边 right 可以取 0 ~ $\overline {efg}$，共有 $\overline {efg} + 1$ 种情况

3、如果 d > 1 时，该数是 $\overline {abc\underline{2}efg}$，左边 left 可以取 0 ~ $\overline {abc} - 1$，共有
$\overline {abc}$ 种情况；右边 right 可以取 0 ~ 999，共有 $1000$ 种情况

时间复杂度 $O(s^2)$

s是n这个数字一共有多少位

Java 代码

class Solution {
    public int countDigitOne(int n) {
        if(n <= 0) return 0;
        List<Integer> nums = new ArrayList<Integer>();
        while(n != 0) 
        {
            nums.add(n % 10);
            n /= 10;
        }
        Collections.reverse(nums);

        int res = 0;
        for(int i = 0;i < nums.size();i ++)
        {
            int left = 0, right = 0, p = 1;
            for(int j = 0;j < i;j ++)
            {
                left = left * 10 + nums.get(j);
            }
            for(int j = i + 1;j < nums.size();j ++)
            {
                right = right * 10 + nums.get(j);
                p *= 10;
            }
            int d = nums.get(i);
            if(d == 0) res += left * p;
            else if(d == 1) res += left * p + right + 1;
            else res += (left + 1) * p;
        }
        return res;
    }
}