ChunNote
0%

leetCode-233:Number of Digit One

发表于 分类于

问题描述

给定一个数字，要求找出从 0 到这个数字中间的每个数字里 1 出现的次数。题目链接：**点我**

样例输入输出

输入：13

输出：6

输入：1

输出：1

问题解法

最简单粗暴的做法就是遍历每个数字，获取每个数字里 1 的个数，然后累加。但是这样在 n 的值比较大的时候会超时。优化的做法分别求出每个数字位 1 的个数，然后进行相加，此种做法参考：https://leetcode.cn/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode-solution-zopq/。

在求每个位的数时，可以先由当前位的高位求出有多少个 10 ^ k 个 1，再求出当前位的地位的数出现 1 的个数，然后两者进行相加。

例如数字 34567，在求百进位数字 1 个数时，由于 0~1000 里百位数字出现的次数为 100（数字 100~199），所以 34567 百位的数字至少为 34 * 100 = 3400（34 由 34567 / 100 = 34 计算而来），此时已经将百位的高位计算剔除，剩下 34567 % 100 = 567 数字判断百位出现 1 的个数。此时分为三种情况：

  • 当前数小于 100，百位出现 1 的个数为 0
  • 当前数介于 100 ~ 199，那么出现 1 的个数即为当前剩下的数
  • 当前数大于 199 ，那么出现 1 的个数为 100

综合三种情况，可以用公式来表示 min(max(num - 100 + 1, 0), 100)，代入计算可以求得值是 100，所以 34567 的百位数结果为 3400 + 100 = 3500。依次类推即可求得每位的数量，最终相加就能得到答案。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countDigitOne(int n) {
        int result = 0;
        int pos = 1;
        while (pos <= n) {
            int temp = pos * 10;
            int modNum = n % temp;
            int quotient = n / temp;
            result += quotient * pos + Math.min(Math.max(0, modNum - pos + 1), pos);
            pos *= 10;
        }

        return result;
    }
}

参考资料

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