剑指31-整数中1出现的次数（从1到n整数中1出现的次数）

Posted on | In |

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

效率低：把数字转换成字符串，统计字符串中符号1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n < 1:
            return 0
        mystr = ''
        for i in range(1,n+1):
            mystr += str(i)
        count = 0
        for i in range(len(mystr)):
            if mystr[i] == '1':
                count += 1
        return count

效率高。

首先三个概念：每个数位的round，base和former，以数532里的数字3来说，round是5，base=10，former是2。

  • 数从0累加1直到等于其自身，某个数字位上经过0-9的一次周期变换称为一个round。可知3所在的数字位经历了5次完整的round。
  • 一个round里，某个数字位的一个数字出现的次数称为base。3所在的数字位的每个数字，其实出现的次数相同，base=10。
  • 3的右邻的数字是former。

根据某个数位的round、base和former，有公式可以计算该数位上每个数字出现的次数。设该数位上的数是n，计算该数位上m出现的次数，有：

  • n<m时，有round*base，第round+1这个不完整的周期里，m在该数位上没出现。
  • n>m是，有(round+1)*base，第round+1这个不完整的周期里，m出现了，出现次数与一个完整周期相同。
  • n=m时，有round*base+former+1，处于前两者之间，出现次数用former+1表示。

另外，最高数字位的round=0。而最低数字位，即个位，的former+1这一项等于0，base=1：

  • n<m时，有round
  • n>=m时，有round+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        counts = []
        round = n
        base = 1
        while round:
            count = 0
            weight = round%10
            round = round/10
            former = n%base
            if weight < 1:
                count += round*base
            elif weight > 1:
                count += round*base + base
            else:
                count += round*base + former + 1 
            counts.append(count)
            base *= 10
        return sum(counts)