leetcode [面试题43] 1～n整数中1出现的次数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

来自题解:

一个数中1的个数包括三部分：

• 最高位 * 少一位的数量，如2234包括 2 * 999内的数量
• 除去最高位的数量，如2234中234的数量
• 如果最高位大于1，有完整的最高位数量个1，否则只有除去最高位数量的1，如1234包括235个1xxx，而2234包括1000个1xxx。

class Solution:
    def countDigitOne(self, n: int) -> int:
        def dfs(n):
            if n <= 0: return 0
            ns = str(n)
            high = int(ns[0])
            power = 10**(len(ns) - 1)
            last = n - high * power
            common = high * dfs(power - 1) + dfs(last)

            if high == 1: 
                return common + last + 1
            else:
                return common + power

        return dfs(n)