leetcode 233. 数字1的个数

题目描述

给定一个整数 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;
    }
}