题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

这道题很中规中矩，大致思路就是求某个数中1的个数+迭代

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        def sumOf1(k):
            sum = 0
            while k > 0:
                sum += (1 if k % 10 == 1 else 0)
                k = int(k / 10)
            return sum

        f = 0
        for i in range(1, n + 1):
            f += sumOf1(i)
        return f

但上面的复杂度为nlogn级别，下面给出一种logn级别的方法。

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        origin = n
        total = 0
        k = 1
        while n > 0:
            # 首先加上保守的部分
            total += origin // (k * 10) * k
            # 待比较的数字
            to_cmp_num = origin % (k * 10)
            # 和基数对比，大于基数，就要加额外的部分，额外的部分取它和基数的差值，但最大为基数k
            if to_cmp_num >= k:
                total += min(to_cmp_num - k + 1, k)
            n = int(n / 10)
            k *= 10
        return total

拿328举例
1、先看个位数，此时基数k=1
首先保守部分个数为328//(1x10) x 1 = 32，也就是个位数为1的保守统计个数为32个，分别是001，011，021...，311。这时待比较数字为328%(1x10)=8，之所以没有把321放进去，是害怕万一这个数为320。你也看到了，当个位数为0（也就是to_cmp_num=0 < 1）的时候，我们是不需要放的。由于to_cmp_num=8大于基数1了，所以就把这个额外的值加上，加多少呢？只能加1，也就是321这个数字。
2、再看十位数，此时基数k=10
首先保守部分个数为328//(10x10) x 10 = 30，也就是十位数为1的保守统计个数为30个，分别是010-019，110-119，210-219。这时待比较数字为328%(10x10)=28，之所以没有把310-319放进去，是害怕万一这个数，比如为308。你也看到了，当十位数为0（也就是to_cmp_num=8 < 10）的时候，我们也是不需要放的。由于to_cmp_num=28大于基数10了，所以就把这个额外的值加上，加多少呢？只能加10，也就是310-319这几个数字；如果是316呢，其实只能加7个。所以应该加差值个数，但最多只能加基数个，即10个。
3、再看百位数，此时基数k=100
首先保守部分个数为328//(100x10) x 10 = 0，也就是百位数为1的保守统计个数为0个。这时待比较数字为328%(100x10)=328，之所以没有把100-199放进去，是害怕万一这个数，比如为099。你也看到了，当百位数为0（也就是to_cmp_num=99 < 100）的时候，我们也是不需要放的。由于to_cmp_num=328大于基数100了，所以就把这个额外的值加上，加多少呢？只能加100，也就是100-199这几个数字；如果是166呢，其实只能加67个。所以应该加差值个数，但最多只能加基数个，即100个。

最后总结一下，先加上保守的部分（一定不会出问题的），再看待比较值to_cmp_num，这个数字为当前及以下位数组成的值。当前在个位时，即个位数值；当前为十位时，即十位和个位组成的值，以此类推。此时看to_cmp_num是否大于基数，小于基数，不用加了；大于基数，就加上它和基数的差值，但最大加的数不超过基数。