剑指 Offer 43. 1～n 整数中 1 出现的次数

输入：n = 12
输出：5

class Solution {
    public int countDigitOne(int n) {
        // 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
        // 几个公示
        // cur > 1 => (high + 1) * bit
        // cur == 1 =>  (high * bit) + (1 + low)
        // cur = 0 => high * bit

        long bit = 1;
        long sum = 0;
        while(bit <= n){
            long cur = (n/bit)%10;
            long low = n % bit;
            long high = n / bit / 10;

            if(cur > 1){
                sum += (high + 1) * bit;
            }else if(cur == 1){
                sum += (high * bit) + (1 + low);
            }else{
                sum += high * bit;
            }
            bit  = bit * 10;
        }

        return (int)sum;

    }
}

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
        # 几个公示
        # cur > 1 => (high + 1) * bit
        # cur == 1 =>  (high * bit) + (1 + low)
        # cur = 0 => high * bit

        bit = 1
        sum = 0
        while bit <= n:
            cur = (n // bit) % 10
            low = n % bit
            high = n // bit // 10

            if cur > 1:
                sum += (high + 1) * bit
            elif cur == 1:
                sum += high * bit + low + 1
            else:
                sum += high * bit
            bit *= 10

        return sum

class Solution {
public:
    int countDigitOne(int n) {
        // 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
        // 几个公式
        // cur > 1 => (high + 1) * bit
        // cur == 1 =>  (high * bit) + (1 + low)
        // cur = 0 => high * bit

        long long bit = 1;
        long long sum = 0;
        while(bit <= n){
            long long cur = (n / bit) % 10;
            long long low = n % bit;
            long long high = n / bit / 10;

            if(cur > 1){
                sum += (high + 1) * bit;
            }else if(cur == 1){
                sum += high * bit + low + 1;
            }else{
                sum += high * bit;
            }
            bit *= 10;
        }

        return sum;
    }
};

func countDigitOne(n int) int {
    // 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
    // 几个公式
    // cur > 1 => (high + 1) * bit
    // cur == 1 =>  (high * bit) + (1 + low)
    // cur = 0 => high * bit

    var bit, sum int64 = 1, 0
    for bit <= int64(n) {
        cur := (int64(n) / bit) % 10
        low := int64(n) % bit
        high := int64(n) / bit / 10

        if cur > 1 {
            sum += (high + 1) * bit
        } else if cur == 1 {
            sum += high*bit + low + 1
        } else {
            sum += high * bit
        }
        bit *= 10
    }

    return int(sum)
}

/**
 * @param {number} n
 * @return {number}
 */
function countDigitOne(n) {
    // 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
    // 几个公式
    // cur > 1 => (high + 1) * bit
    // cur == 1 =>  (high * bit) + (1 + low)
    // cur = 0 => high * bit

    let bit = 1;
    let sum = 0;
    while (bit <= n) {
        let cur = Math.floor((n / bit) % 10);
        let low = n % bit;
        let high = Math.floor(n / bit / 10);

        if (cur > 1) {
            sum += (high + 1) * bit;
        } else if (cur == 1) {
            sum += (high * bit) + (1 + low);
        } else {
            sum += high * bit;
        }

        bit = bit * 10;
    }

    return sum;
}