leetcode 233. 数字 1 的个数

2024-10-19 18:51:16

问题描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13

输出: 6

解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

问题分析

这道题可以换一个思路，即[0,n]中有多少个小于n的第i位为1的数，例如n = 12345时，我们要找百位数为1时，存在多少数m小于12345，我们分为两部分,设\(m = p1q\),

如果\(p\in[0,11]\)时，\(q\)可以取\([0,99]\)之间任意一个数，共100个，
如果\(p = 12\)时，因为百位数字为\(3>1\)，因此我们还是可以取\([0,99]\)之间任意一个数，共\(100\)个，但是假如\(n=12045\),这样的数是不存在的，因为任意\(121q>12045\),假如\(n=12145\),则只能取\([0,45]\)之间的数，共46个。

综上我们可以总结规律如下：我们统计从左到右的第i位为1小于n的数量时

首先可以确定有\(\lfloor \frac{n}{10^{i+1}}\rfloor\times 10^i\)个数
下面考虑第i位的数\(x = \lfloor\frac{n}{10^{i}}\rfloor\%10\),若\(x > 1\),则还会有\(10^i\)个数小于n,如果\(x = 1\),则会有\(n \% 10^i + 1\)个数小于n, 如果\(x = 0\),则不会有新的满足条件的数了

代码

class Solution {

public:

    int countDigitOne(int n) {

        int count=0,x;

        long div = 1;

        while(n>=div)

        {

            count += (n / (div*10))*div;

            x = (n/div)%10;

            if(x == 1)count += (n%div + 1)*x;

            else if(x > 1) count += div;

            div *= 10;

        }

        return count;

    }

};

最新文章

热门文章