一、题目描述

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

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

示例 1：

输入：n = 12

输出：5

示例 2：

输入：n = 13

输出：6

限制：

1 <= n < 2^31

二、思路讲解

本题采用的思路为，按位逐一找到每一位上1出现的个数，然后加起来即可，关于每一位1的个数，有三种情况：

1、当前位上为0

以n=2705为例，假设我们要找十位上1出现的次数，那么当前位上是0，高位上是27，低位上是5；那么要找十位为1的数字范围是 0010~2619，就相当于固定了十位为1，然后任意修改其他位的数字，可能的情况为000~269，共有270中情况，270其实等于 高位 * 位权值  ，即27*10+1；

2、当前位上为1

以n=2715为例，假设我们要找十位上1出现的次数，那么要找的数字是 0010~2715，就相当于固定了十位为1，然后任意修改其他位的数字，可能的情况为000~275，共有276中情况，276其实等于 高位* 位权值 + 低位 + 1 ，即26*10+9+1；

3、当前位上为2~9

以n=2755为例，假设我们要找十位上1出现的次数，那么要找的数字是 0010~2719，就相当于固定了十位为1，然后任意修改其他位的数字，可能的情况为000~279，共有280中情况，280其实等于 （高位+1）* 位权值 ，即(27+1)*10；

然后逐位计算1的次数之后，相加即可。

三、Java代码实现

class Solution {
    public int countDigitOne(int n) {
        int digit = 1;  //位因子，个位为1，十位为10，百位为100……
        int res = 0;    //总次数     
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0){   //如果当前位上为0
                res += high * digit;
            } 
            else if(cur == 1){  //如果当前位上为1
                res += high * digit + low + 1;
            } 
            else {  //如果当前位为 2~9
                res += (high + 1) * digit;
            }
            //更新高位、当前位、低位
            low += cur * digit;
            cur = high % 10;
            high = high / 10;
            digit = digit * 10;
        }
        return res;
    }
}

四、时空复杂度分析

时间复杂度 O(log n)： 循环内的计算操作使用 O(1) 时间；循环次数为数字 n 的位数，即 log10_n，因此循环使用 O(log n)时间。

空间复杂度 O(1)： 几个变量使用常数大小的额外空间。