jz043.1~n整数中1出现的次数

题目链接

这个题，很容易想到一个思路就是累加1-n中每个整数1出现的次数，我们每次可以通过对10求余判断整数的个位数字是不是1，如果这个数字大于10，则除以10以后再判断个位数是不是1。基于这种思路，我们很容易写出方法1，但是由于该算法需要对每个数字做除法与求余，那么如果输入数字n，n有O（logN）位，我们需要判断每一位是不是1，那么改算法的时间复杂度为O（NlogN），运算效率过低。

所以我们可以考虑从数字规律入手。首先对于一个数，如123456，我们定义digit为位数，比如3在1000位上，并且如果我们在考察在1000位上的数字3，那么将改位数字定义为cur，cur之前对数字如12则被定义为high，cur后面的数字如456则被定义为low。我们利用这些定义来促进问题的分析。接下来，考虑三种情况：

• cur位上的数字为0: 我们以数字2304并且考察digit为10的例子，我们注意到，从1到2304的数字中能符合cur上是1的范围是从0010到2219（注意到由于cur为0，所以high要退一位，既high要减一），所以，这个问题就变成了计数，从000到229有几个数字的问题（将high和low相连组成的数，因为每有一个数字，cur上都会出现一次1），总之，cur出现1的次数为229 - 000 + 1 = 230 （可以表示成high * digit）。
• cur位上的数字为1：此时我们以2314为例子，同样的，考察从1到2314的数字中能使得cur为1的数字范围（为0010 - 2314），此时问题变成了000到234有几个数字，我们以计算出为235，我们可以将该计算总结成high * digit + low + 1。
• cur位上的数字为除0和1外的其他数字：此时我们以2324为例，从1到2324点数字中能使得cur为1的数字范围是0010 - 2319，此时我们又可以相似地计算出000到239的数字个数为240，我们可以将这一条概括成（high + 1）* digit。

分了这三种情况后，我们容易求出在某位上的数字为1的所有出现次数，但是我们还要处理每一位，此时我们用low += digit * cur来更新low（因为要把位数往前1位，要把cur加入low里），用cur = high % 10来更新cur（因为high的最后一位就是下一个cur），并且用high //= 10来更新high（去掉末尾到数字（即新的cur）），并且，再将digit更新为上一步的十倍。最后再把每一步得到的值相加即为所求。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。

class Solution:
    def countDigitOne1(self, n: int) -> int:
        res = 0
        for i in range(n):
            res += self.countEach(i+1)
        return res

    def countEach(self, num):
        tmp = 0
        while num:
            if num % 10 == 1:
                tmp += 1
            num = num // 10
        return tmp

    def countDigitOne2(self, n: int) -> int:
        res = 0
        digit = 1
        high, cur, low = n // 10, n % 10, 0
        while high != 0 or cur != 0:
            if cur == 0:
                res += high * digit
            elif cur == 1:
                res += high * digit + low + 1
            else:
                res += (high + 1)* digit
            low += digit * cur
            digit *= 10
            cur = high % 10
            high //= 10
        return res