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

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

示例

• 输入：n = 12

• 输出：5

限制

• 1 <= n < 2^31

方法：枚举

• 当 cur = 0 时，此位 1 的个数的计算公式为：high * digit；

• 当 cur = 1 时，此位 1 的个数的计算公式为：high * digit + low + 1；

• 当 cur > 1 时，此位 1 的个数的计算公式为：(high +1) * digit。

代码如下：

复杂度分析

• 时间复杂度 ： O(logn) 。

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

END

聪明出于勤奋，天才在于积累，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。