题目如下:
- 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(object):
- def countDigitOne(self, n):
- """
- :type n: int
- :rtype: int
- """
- if n <= 0:
- return 0
- res = 0
- sn = str(n)
- length = len(sn)
- inx = len(sn) - 1
- while inx>= 0:
- lower = sn[inx+1:]
- current = sn[inx]
- higher = sn[:inx]
- if int(current) == 0:
- if len(higher)> 0:
- res += int(higher) * (10 ** (length - inx - 1))
- elif int(current) == 1:
- if len(higher)> 0:
- res += int(higher) * (10 ** (length - inx - 1))
- if len(lower)> 0:
- res += int(lower)
- res += 1
- else:
- if len(higher)> 0:
- res += (int(higher)) * (10 ** (length - inx - 1))
- res += 1 * (10 ** (length - inx - 1))
- inx -= 1
- return res
来源: http://www.bubuko.com/infodetail-3075455.html