233.md

233 Number of Digit One

Description

link

---

Solution

以24071为例，如果我们想计算百位上1出现的次数，具体思路如下：

获取百位的高位为24，获取百位的低位为71，当前百位数字为0。 从高位出发来分析，百位出现的次数有：0010000190,0110001190,0210002190,…,2310023190。总共有(24100)个1出现。 这是百位为0的情况，如果百位为1的时候，那除了上述的(24100)个1之外，还包括：24100～24171，共(71 + 1)个1，即总共：24 * 100 + 71 + 1。

如果百位大于1例如为6的时候，那除了最开始的(24*100)个1之外，还包括了：24100~24199，共100个1，即总共：(24 + 1)*100。

总结规律

其实通过上面的分析，我们就可以归纳出一个规律如下。

要求第i位1出现的次数，并且i的高位数为highN，低位数为lowN，当前第i位的数字为cdigit，则当前i位1出现的次数分三种情况：

• cdigit == 0, count = highN * factor.
• cdigit == 1, count = highN * factor + lowN + 1.
• cdigit > 1, count = (highN + 1) * factor.

其中，factor为当前的乘积因子，例如百位的factor为100，十位的乘积因子为10。

有了规律，代码只要按照规律写出来即可。

---

Code

class Solution:
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        # runtime: 38ms
        if n <= 0: return 0
        if n == 1: return 1
        
        res, i, q = 0, 1, n
        while i <= n:
            prefix = n // (i * 10)
            current = q % 10
            suffix = n % i
            res += prefix * i
            if current > 1:
                res += i
            elif current == 1:
                res += suffix + 1
            q //= 10
            i *= 10
        
        return res