233. Number of Digit One [思路]

https://leetcode.com/problems/number-of-digit-one/
想到一个优雅的解法还是不容易的

个人解答

class Solution:
    def countDigitOne(self, n: int) -> int:
        e = 1
        res = 0
        origin = n
        while n > 0:
            d = n % 10
            n //= 10
            if d == 0:
                res += n * e
            elif d == 1:
                res += n * e + origin % e + 1
            else:
                res += n * e + e
            e *= 10
        return res

题目思路

数出所有的，那么每一位出现的次数加起来即可，这一步想明白还是要花一番功夫的。
对每一位上的数字，分三种情况讨论，整体还是比较明确的：

if n = xyzdabc
(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1

编程上也要考虑一点技巧，让代码写的更简洁。

其它解法

最初写的笨笨的解法，找规律，打表，然后组合处理

class Solution:
    def countDigitOne(self, n: int) -> int:
        table = {}
        for i in range(1, 10):
            table[i] = 1
        for i in range(1, 20):
            table[10 ** i] = i * 10 ** (i - 1)
            table[10 ** i * 2] = table[10 ** i] + 10 ** i + table[10 ** i]
            for j in range(3, 10):
                table[10 ** i * j] = table[10 ** i * (j - 1)] + table[10 ** i]
        res = 0
        s = str(n)
        for i, d in enumerate(s):
            if d == '0':
                continue
            d = int(d)
            e = len(s) - i - 1
            large = d * 10 ** e
            res += table[large]
            if d == 1 and s[i+1:]:
                res += int(s[i+1:]) + 1
        return res