题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
示例:
- 输入: 25
- 输出: 9
- 解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
提示：
- n <= 10^9
题目思考
- 可否单独统计每一位上的 2?
解决方案
思路
- 一个最简单的思路是从 0 到 n 依次遍历, 然后统计各个数字的 2 的数目并累加, 但观察题目数据规模, 最大都到了 10^9, 这个做法肯定会超时
- 换个思路, 如果我们可以单独统计每一位上的 2 在多少个数中存在, 这样只需要遍历所有位数并累加结果即可
- 举个例子, 假如
n = 12x45, 现在要统计1~12x45在第 x 位上 2 的数目, 显然这里分为三种情况:x < 2: 此时要想这一位上有 2, 那么前两位的范围只能是0~11, 而后两位的范围则可以是0~99, 也即00200, 00201, ..., 11299这么多种可能性, 只考虑该位上的 2, 那么它的数目就是左右取值范围的乘积, 也即12*100x = 2: 此时显然仍包含第一种情况中的可能性, 但它有额外的部分, 也即前两位是 12, 然后后面的范围是 0~45, 加起来就是12*100 + 1*46个 2x > 2: 此时仍包含第一种情况中的可能性, 但对于前两位是 12 来说, 后面的取值范围就是 0~99 了, 因为12199 < 12x45, 所以加起来就是12*100 + 1*100个 2
- 综合这三种情况, 就能够计算出每一位上的 2 的数目, 最后累加起来就是总的 2 的数目
- 注意
x < 2的数目是所有情况下共享的, 所以可以先计算出这一部分, 然后针对x = 2和x > 2再额外计算剩余部分, 从而减少代码冗余 - 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(logN)- 只需要遍历 n 的每一位, 总位数是 logN
- 空间复杂度
O(1)- 不需要额外空间
代码
class Solution:
def numberOf2sInRange(self, n: int) -> int:
# 对每一位进行判断, 左右相乘, 分大于等于小于2三种情况
res = 0
# 将数字先转成字符串, 方便对每一位的处理
s = str(n)
for i, x in enumerate(s):
# 对应x<2时的左边部分的取值范围
# 注意对于最高位而言, 它的左边部分为0, 这是因为最高位不可能小于1, 所以这部分不应该有
left = 0 if i == 0 else int(s[0:i])
# 对应x<2时的右边部分的取值范围
right = 10**(len(s) - i - 1)
if x < '2':
# 当x<2时, 直接加上分析的左右部分乘积即可
res += left * right
elif x == '2':
# 当x=2时, 需要额外加上右边的计数, 对于例子12x45 (x=2)来说, 就是46
# 注意如果此时是最低位, 那么额外只有1种可能, 就是上限n本身, 所以最低位是2的话只需要加上1
extra = 1 if i == len(s) - 1 else int(s[i + 1:]) + 1
res += left * right + extra
else:
# 当x>2时, 需要额外加上1*right
res += (left + 1) * right
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号