题目描述
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
相关话题： 数学 难度： 困难
示例：
输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
-
解法1：暴力循环
两个循环，外循环for(int i = 1;i <= n;i++)，内循环对那个数做移位(十进制)统计1的个数。 -
解法2
一个纯数学的方法，
我们不需要循环每个数字，而是直接计算每个位为1时的数字个数。(最高可能的位肯定是数字n的位数) - 该方法用到三个变量
high，current，low分别表示数字的高位、当前位、低位。当前位有三种情况：1.current == 0；2.current == 1；current > 1
- 当
current == 0，例如数字123 0 56，百位为0，此时high = 123, current = 0, low = 56。百位数字为1的数字个数为high * 100。
核心思想：可以想象123056这个数是由100开始不断加1得到的，加的过程中其实是在向high高位进1，那么high == 000时，000100->000199有100个数；high == 001时，001100->001199有100个数。显然，当current == 0，high的范围是000 -> 122。- 当
current == 1时，例如数字123 1 56，百位为1，除了像current == 1那样有high * 100的部分(最后high == 123时，不满100个数)，后面还有low + 1个数。- 当
current > 1时，例如数字123 2 56，百位为> 1，这次high == 123时，可以加到123 1 99(满100个)，个数是(high+1)*100。- 其他位思路一样
class Solution {
public int countDigitOne(int n) {
if(n < 0) return 0;
long high = n, current = 0, low = 0;
int count = 0;
long bit = 10;
while(high != 0){
high = n / bit;
low = n % bit;
current = low / (bit / 10);
low = low % (bit / 10);
if(current == 0){
count += high * (bit / 10);
}else if(current == 1){
count += high * (bit / 10) + low + 1;
}else{
count += (high + 1) * (bit / 10);
}
bit *= 10;
}
return count;
}
}
