233-Number_of_Digit_One-数字1的个数

233、数字1的个数

tag: python 、 数学

---

题目描述

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

示例

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

---

题目链接

233. 数字1的个数

---

题解

  暴力解法，循环每一个数计算每一个数中 1 的个数显然是可以的但是必然会超时。那么就要考虑有没有别的方法能够快速得得到结果，直观上这一定是一种数学的解法。

  我们可以考虑每一位上出现 1 的个数

• 个位时，1 出现了 n / 10 + (n % 10) != 0 ，每十个数个位会出现一次 1，末尾只要不是 0 便会出现一次 1

• 十位时，情况就较为复杂，我们考虑末两位的情况

  • [00, 09] ，没有出现

  • [10, 19] ，出现了 n % 100 - 10 + 1 次

  • [20, 99] ，出现了 [10, 19] 共10次

  那么整合这三种情况可以得到十位出现的个数为 n / 100 * 10 + min(10, max(n % 100 - 10 + 1, 0))

• 百位时，与十位类似

  • [000, 099] ，没有出现

  • [100, 199] ，出现了 n % 1000 - 100 + 1 次

  • [200, 999] ，出现了 [100, 199] 共100次

  ...

  最终可以得到第 i 位出现 1 的次数的公式

n / 10^i * 10^(i-1) + min(10^(i-1), max(n % 10^i - 10^(i-1) + 1, 0))

class Solution:
    def countDigitOne(self, n: int) -> int:
        i = 1
        s = 0
        while i <= n:
            s += n // (i*10) * i + min(i, max(n % (i*10) - i + 1, 0))
            i *= 10
        return s

  最终结果，运行时间32ms，超过76.90%；占用内存13.5MB，超过6.94%。