31 整数中1出现的次数
题目描述
求出1~13的整数中1出现的次数，并算出100~1300的整数中1出现的次数。为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次，但是对于后面问题他就没辙了。请实现一个函数，求数字中1出现的次数。
解题思路
核心思想：按位分析，计算每一位上1出现的次数。
关键步骤：
- 从个位开始，逐位分析
- 设当前位的权重为10^i
- 将数字分为三部分：高位、当前位、低位
- 根据当前位的值计算该位1出现的次数
公式：
- 当前位 = 0：count += high × weight
- 当前位 = 1：count += high × weight + low + 1
- 当前位 > 1：count += (high + 1) × weight
时间复杂度：O(log n) 空间复杂度：O(1)
Python 实现
python
def number_of_1_between_1_and_n(n):
"""
计算1到n中1出现的次数
Args:
n: 正整数
Returns:
int: 1出现的次数
"""
if n <= 0:
return 0
count = 0
i = 1 # 当前位的权重（个位为1，十位为10，...）
while n // i > 0:
# 高位、当前位、低位
high = n // (i * 10)
current = (n // i) % 10
low = n % i
# 根据当前位的值计算count
if current == 0:
count += high * i
elif current == 1:
count += high * i + low + 1
else:
count += (high + 1) * i
i *= 10
return count
# 测试代码
if __name__ == "__main__":
test_cases = [1, 5, 10, 13, 20, 100, 1300]
for n in test_cases:
print(f"1到{n}中1出现的次数: {number_of_1_between_1_and_n(n)}")
# 输出:
# 1到1中1出现的次数: 1
# 1到5中1出现的次数: 1
# 1到10中1出现的次数: 2
# 1到13中1出现的次数: 6
# 1到20中1出现的次数: 12
# 1到100中1出现的次数: 21
# 1到1300中1出现的次数: 639图解
计算1到13中1的次数:
个位分析（i=1）:
n = 13
high = 13 // 10 = 1
current = (13 // 1) % 10 = 3
low = 13 % 1 = 0
current = 3 > 1
count += (1 + 1) * 1 = 2
解释: 0-9中个位1出现1次，10-19中个位1出现1次，共2次
十位分析（i=10）:
n = 13
high = 13 // 100 = 0
current = (13 // 10) % 10 = 1
low = 13 % 10 = 3
current = 1
count += 0 * 10 + 3 + 1 = 4
解释: 十位为1时，个位可以是0-3，共4个（10,11,12,13）
总计: 2 + 4 = 6
验证: 1,10,11,12,13 → 1出现6次 ✓