Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example:
Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
思路一
class Solution:
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
k, count = 1, 0
while k <= n:
r = n // k #save previous num
m = n % k
print(count)
count += ((r + 8) // 10) * k + (m + 1 if r % 10 == 1 else 0)
print(count)
print('-----')
k *= 10
return count
思路二
class Solution:
def countDigitOne(self, n: 'int') -> 'int':
def r(s, k=0):
n = len(s)
if n == 1:
return (s != '0') + (int(s) + 1) * k
elif s[0] == '0':
return r(s[1:], k)
else:
nines = "9" * (len(s) - 1)
if s[0] == '1':
return r(nines, k) + r(s[1:], k + 1)
else:
return r(nines, k) * (int(s[0]) - 1) + r(nines, k + 1) + r(s[1:], k)
return r(str(n), 0) if n > 0 else 0
