剑指 Offer 43. 1～n整数中1出现的次数

题目描述

做题链接：剑指 Offer 43. 1～n整数中1出现的次数

解题思路

递归

参考：python递归

可以分为两种情况，第一种情况是最高位为1，第二种情况是最高位非1

• 最高位为1

• 最高位非1

代码

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0: return 0
        num_s = str(n) 
        high = int(num_s[0])  
        pow_ = 10**(len(num_s)-1) 
        last = n - high * pow_

        if high == 1:
            return self.countDigitOne(pow_ - 1) + last + 1 + self.countDigitOne(last)
        else:
            return self.countDigitOne(last) + pow_ + high * self.countDigitOne(pow_ - 1)