本问题对应的 leetcode 原文链接:剑指 Offer 43. 1~n 整数中 1 出现的次数

问题描述

输入一个整数 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

解题思路

视频讲解直达: 本题视频讲解

代码实现

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;

    }
}

时间复杂度:O(logn)
额外空间复杂度:O(1)

Python

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

C++

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;
    }
};

Go

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)
}

JS

/**
 * @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;
}

发表回复

后才能评论