[剑指Offer]整数中1出现的次数(从1到n整数中1出现的次数)

题目描述

输入一个整数n,求1~n这n个整数的十进制表示中1出现的次数。例如,输入12,1~12这些整数中包含1的数字有1、10、11和12,1一共出现了5次。

解题思路

  1. 直接遍历这些整数,转化为字符串,统计每个中1出现的次数。没有考虑时间效率。
  2. 数字规律法。对于一个整数,逐位分析它上面出现1的次数,然后加起来。以百位为例。
    1. 若百位数字为0,比如12024,则百位上可能出现1的有:100~199,1100~1199,……,11100~11199,共12*100个,可见等于其高位数字*当前位数
    2. 若百位数字为1,比如12124,则百位上可能出现1的有:100~199,1100~1199,……,11100~11199,12100~12124,共12*100+25个,可见等于高位数字*当前位数+低位数字+1
    3. 若百位数字大于1,比如12224,则百位上可能出现1的有:100~199,1100~1199,……,11100~11199,12100~12199,共(12+1)*100个,可见等于(高位数字+1)*当前位数

代码

Python(2.7.3)

无脑遍历法

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
res = 0
for i in range(n + 1):
res += str(i).count('1')
return res

运行时间:36ms
占用内存:5860k

数字规律法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
res = 0
s = str(n)
length = len(s)
for idx, i in enumerate(s):
place = length - idx # 当前位数(个位是1,十位是2……)
pre = n // (10 ** place) # 当前位数的高位数字
aft = n % (10 ** (place - 1)) # 当前位数的低位数字
if i == '0':
res += pre * 10 ** (place - 1)
elif i == '1':
res += pre * 10 ** (place - 1) + aft + 1
else:
res += (pre + 1) * 10 ** (place - 1)
return res

运行时间:23ms
占用内存:5744k