难度: Hard
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13 输出：6
示例 2：
输入：n = 0 输出：0
提示：
0 <= n <= 109
Submission
运行时间: 18 ms
内存: 16.1 MB
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n)
l = len(s)
i = 0
ans = 0
while i<l:
now = int(s[i])
pre = 0 if i==0 else int(s[:i])
suf = 0 if i+1==l else int(s[i+1:])
mul = 10 ** (l-i-1)
if now==0:
ans += pre * mul
elif now==1:
ans += pre * mul + suf + 1
else:
ans += (pre+1) * mul
i += 1
return ans
'''
逐位枚举.如对于百位,
37049:00100-36199,即0000-3699,37*100个
37149:00100-37149,即0000-3749,37*100+(49+1)个
37549:00100-37199,即0000-3799,(37+1)*100个
'''
Explain
这个题解采用了逐位枚举的思路。对于给定的整数n,我们将其转为字符串s,然后从高位到低位逐个分析每一位上1出现的次数。对于第i位,我们将数字分为三部分:第i位之前的部分(记为pre)、第i位(记为now)以及第i位之后的部分(记为suf)。根据now的值,我们可以分三种情况统计第i位上1出现的次数:1)now=0时,ans+=pre*mul;2)now=1时,ans+=pre*mul+suf+1;3)now>1时,ans+=(pre+1)*mul。最后,将每一位统计的结果累加即可得到最终答案。
时间复杂度: O(m),其中m为整数n的位数
空间复杂度: O(m),其中m为整数n的位数
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n) # 将整数n转为字符串s
l = len(s) # 获取字符串s的长度
i = 0 # 初始化指针i
ans = 0 # 初始化答案
while i<l: # 逐位分析
now = int(s[i]) # 获取第i位的值
pre = 0 if i==0 else int(s[:i]) # 获取第i位之前部分的值
suf = 0 if i+1==l else int(s[i+1:]) # 获取第i位之后部分的值
mul = 10 ** (l-i-1) # 计算第i位的权重
if now==0: # 情况1
ans += pre * mul
elif now==1: # 情况2
ans += pre * mul + suf + 1
else: # 情况3
ans += (pre+1) * mul
i += 1 # 指针前移
return ans # 返回最终结果
Explore
在计算第i位上数字1的出现次数时，将数字分为pre、now和suf三部分有助于我们从不同的角度考虑这一位数的贡献。具体来说，pre代表第i位之前的数字，这影响了第i位上1可以出现的次数；now是当前考察的位数，它的具体值决定了后续计算的方式；suf则是第i位之后的数字，它的值决定了当now为1时，后续位置上可能出现的所有数字组合。这种分割使得我们可以精确计算每一位对总1的个数的贡献，从而逐位累加得到最终答案。
当now=1时，表示当前位（第i位）为1。此时，1的总出现次数由两部分组成：1) pre部分决定了前面可以形成多少个完整的100...000到199...999之间的数（即从100...000到199...999总共pre个这样的区间），每个区间贡献了mul个1；2) suf部分表示，当前位为1时，后面的数字可以取0到suf的所有值，这样就有suf+1种可能（包括0这一个数）。因此，总的1的个数就是前面的区间数乘以每个区间的1的个数加上后面的数的可能性，即pre * mul + suf + 1。
对于now=0的情况，当前位为0意味着1只能出现在pre定义的范围内的数字中，且仅当pre形成的数字在前面时第i位才可能为1，因此这部分的贡献是pre * mul。对于now>1的情况，当前位大于1意味着无论suf是什么，当前位都能取到1，即从0到now-1的任何数，在now为1时，suf可以取0到999...（l-i-1个9），因此贡献是(pre+1) * mul。这样的计算确保了无论now的值是多少，第i位上1的出现次数都能被正确计算。
变量`mul`代表的是10的l-i-1次幂，其中l是数字n的位数，i是当前考察的位数的索引（从0开始）。`mul`实际上是一个权重，表示当第i位上的数字变化时，对整个数字表示的影响。例如，如果i是1（即第二位），mul就是10的l-2次幂，反映了在这一位上每变化一个单位，数字总体变化了10^(l-2)。这个权重帮助我们在计算1的出现次数时，正确计算出因当前位的变化引起的所有可能的1的数量。