233. 数字 1 的个数

Difficulty
Hard
Tags
数学
URL
https://leetcode.cn/problems/number-of-digit-one/
Star
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
  • 0 <= n <= 109

法 1 从个位开始数 ，各位十位百位

思路
参考 残酷刷题群群主讲解视频。
将个位十位百位。。。的1出现的个数分别计算出来。 以百位为例：
假设val = 345👩32, 👩为百位
分为三种情况考虑：
  1. 高位的三位小于 345， 此时百位👩可以定为 1， 然后 👩 前面的几位数字可以为任意数字xxx，但是不能超过345， 后面可以为任意数字yy。此时，总的 数字个数为 xxx 乘 yy . 具体 xxx 可以有 345 种不同的数字（将0包括进来），yy可以有 10 ** 2 种不同的数字（将0也包括进来）
  1. 高位 三位等于 345， 此时需要判断 👩 和1的关系：
    1. 👩 == ”1“ ： 此种情况下有：32 + 1 种可能， 因为需要把 0 包括进来
    2. 👩 < “1” , 0 种可能
    3. 👩 > 1, 10 ** 2 种可能。
题解
class Solution:
    def countDigitOne(self, n: int) -> int:
        s = str(n)[::-1]
        res = 0
        for i in range(1, len(s)+1):
            res += self.helper(n, s, i)
        return res
    
    def helper(self, n, s, i):
        """计算 i 位置上 1 的个数
        i = 1 是个位
        """
        res = 0 
    
        # 1. 判断小于 n 的所有数字中  该位置为 1 的个数
        # xxx 1 yyy, 看 xxx 和 yyy 各自有多少种排列，000 也算一种排列！ 
        # 计算 xxx 乘 yyy 就是此时的结果
        res += (n // pow(10, i)) * pow(10, i-1)

        # 判断 高位与 xxx 相同的所有数字中， 
        # xxx 正好等于 n的三位高位
        # 所以前面不能动 ，看后面可以有几种变化
        digit = s[i-1]
        if digit == "1":
            res += n % pow(10, i-1) + 1
        elif digit > "1":
            res += 1 * pow(10 , i-1)
        
        return res