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

本问题对应的 leetcode 原文链接:剑指 Offer 43. 1~n 整数中 1 出现的次数
对应打卡问题:【数学知识】剑指 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)

发表回复

后才能评论