难度: Hard
编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
示例:
输入: 25 输出: 9 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
提示：
n <= 10^9
Submission
运行时间: 27 ms
内存: 16.1 MB
class Solution:
def numberOf2sInRange(self, n: int) -> int:
count = 0
factor = 1
while n // factor > 0:
curr = (n // factor) % 10
low = n - (n // factor) * factor
high = n // (factor * 10)
if curr < 2:
count += high * factor
elif curr == 2:
count += high * factor + low + 1
else:
count += (high + 1) * factor
factor *= 10
return count
Explain
这个题解采用了数位分析的方法来统计数字2的出现次数。首先，对于给定的数字n，算法逐位考察（从个位开始到最高位），并计算每一位上数字2出现的总次数。具体来说，对于每一位，算法分别计算这一位上的数字（curr）、其低位组成的数字（low）和高位组成的数字（high）。然后根据当前位的数字分三种情况处理：1) 当前位数字小于2时，2的数量由高位数字决定；2) 当前位数字等于2时，2的数量由高位和低位共同决定；3) 当前位数字大于2时，高位数字增加一的情况也需要计入2的总数。这种方法利用数学分割和模运算来避免直接的枚举，从而提高效率。
时间复杂度: O(log(n))
空间复杂度: O(1)
class Solution:
def numberOf2sInRange(self, n: int) -> int:
count = 0 # 用于统计2的总数
factor = 1 # 表示当前正在处理的数位（个位开始，逐渐向高位移动）
while n // factor > 0: # 从低位到高位逐位处理
curr = (n // factor) % 10 # 当前位的数字
low = n - (n // factor) * factor # 当前位下面的所有低位组成的数字
high = n // (factor * 10) # 当前位以上的所有高位组成的数字
if curr < 2:
count += high * factor # 当前位是0或1，2的出现只依赖于高位
elif curr == 2:
count += high * factor + low + 1 # 当前位是2，2的出现由高位和低位共同决定
else:
count += (high + 1) * factor # 当前位是大于2的数，高位数字+1的情况也要计算进去
factor *= 10 # 移动到下一位
return count
Explore
在算法中，`factor`变量起着关键作用，其初始值为1，表示最低位（个位）。通过逐次乘以10，`factor`依次表示十位、百位、千位等，确保了从个位开始，逐位向高位处理。在每次循环中，通过计算`(n // factor) % 10`可以得到当前位的值。循环的继续条件是`n // factor > 0`，意味着只要除以`factor`的结果大于0，就表示还有更高的位需要处理。这样，算法从个位开始，一直处理到最高位。
当当前位的数字等于2时，除了考虑高位数字能形成的所有可能组合外，还需要考虑低位数字能形成的所有可能性。例如，假设数字为`XYZ2ABC`，其中`2`是我们正在处理的位，`XYZ`是高位，`ABC`是低位。在这种情况下，所有`XYZ`高位的组合已经计算（即`XYZ * factor`），但对于每一种`XYZ`的组合，低位可以从`000`到`ABC`（包括`ABC`本身），因此需要加上`ABC + 1`（即低位的数字总数）。这样我们就能确保包含了所有以2为当前位的数字组合。
`factor`变量在算法中表示当前处理的数位的基数（例如个位的基数是1，十位是10，百位是100等）。通过不断地将`factor`乘以10，可以移动到下一个更高的数位。在计算当前位的数字时使用`(n // factor) % 10`，这样便能得到从个位开始逐位的数值。同时，`factor`也用于计算高位和低位的数值，高位用`n // (factor * 10)`计算，而低位则是`n - (n // factor) * factor`。这样，`factor`帮助算法理解并分析每一位数的值及其对最终数位中2的出现次数的贡献。