整数中1出现的次数.md

整数中1出现的次数(从1到n整数中出现1的次数)

知识点：

题目描述

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

解题思路

思路一

观察规律，以百位上出现1的次数为例说明，假设n大于等于100且百位上的数为k，则：

• k=0 比如12013，百位是0，那么从1到12013这些数中百位上出现1的有多少个数？ 应该是：100-199，1100-1199，2100-2199，。。。11100-11199，一共12100=1200个数，可以发现，这种情况下1出现的次数是由k的更高位决定的，这里是12，最终结果是k的最高位乘以k的当前位（100）即12100

• k=1 比如12113，百位是1，那么从1到12113这些数中百位上出现1的有多少个数？ 应该分为两部分： 第一部分：100-113一共114个数，可以发现这个数字由k的低位决定，算法是k的低位加1（13+1） 第二部分：100-199，1100-1199，...，11100-11199，和k=0时的情况一样，总数是更高位乘以当前位数即12*100个数

• k=2...9 比如12212，百位是2，那么从1到12212这些数中百位上出现1的有多少个数？ 应该是：100-199，1100-1199，...，11100-11199，12100-12199，总数是更高位乘以当前位数加一即（12+1）*100=1300个数

思路二

遍历所有数，然后数1出现了多少次，算法复杂度过高，不推荐。

代码

    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        strN = str(n)
        size = len(strN)
        sum = 0

        # 从个位开始
        for i in range(size - 1, -1, -1):
            curBit = int(strN[i])
            multiValue = pow(10, size - 1 - i)
            if i == 0:
                biggerValue = 0
            else:
                biggerValue = strN[0:i]
            if i == size - 1:
                smallerValue = 0
            else:
                smallerValue = strN[i + 1:]

            if curBit == 1:
                count = int(biggerValue) * multiValue + int(smallerValue) + 1
            elif curBit == 0:
                count = int(biggerValue) * multiValue
            else:
                count = (int(biggerValue) + 1) * multiValue

            sum += count

        return sum

这里