• 周一. 6月 24th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

233. 数字 1 的个数 力扣(困难) 数位dp/数学 不会做

admin

11月 28, 2021

233. 数字 1 的个数

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

示例 1:

输入:n = 13
输出:6

题解:https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode-solution-zopq/

代码:

class Solution {
public:
    int countDigitOne(int n) {
    long long k=1;
    int res=0;                // 以 n=12345678为例,我们想要求百位上1的个数
    while(n%k<n)
    {
        k*=10; 
        int x=n/k;           //   也就是百位前有 12345
        int y=n%k;           //  后面是678
        res+=x*(k/10);    
        if(y<k/10) continue;
          else if (y<2*k/10) res+=y-k/10+1;
            else res+=k/10;
    }
    return res;
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注