面试题 17.06. 2出现的次数

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

示例:

输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)

提示：

• n <= 10^9

Python 解答：
1.递归

class Solution:
    def numberOf2sInRange(self, n: int) -> int:
        if n < 2:
            return 0
        elif n <= 10:
            return 1
        else:
            m = n
            count = 0
            while m > 0:
                m //= 10
                count += 1
            a = n // (10**(count-1))
            b = n - a*(10**(count-1))
            if a < 2:
                return a*self.numberOf2sInRange(10**(count-1)-1) + self.numberOf2sInRange(b)
            elif a == 2:
                return a*self.numberOf2sInRange(10**(count-1)-1) + self.numberOf2sInRange(b) + b+1
            else:
                return a*self.numberOf2sInRange(10**(count-1)-1) + self.numberOf2sInRange(b) + 10**(count-1)