剑指Offer 44：数字序列中某一位的数字

Leetcode 400. Nth Digit

先想了一个蠢办法，一个个数过去，果然超时了，代码见最后
优化一下，依次判断是否在0-9,10-99,100-999等等，判断出范围在进行偏移量计算，解法如下：

class Solution:
    def findNthDigit(self, n: int) -> int:
        def f(x):
            return  10 ** (x - 1) * x * 9
        
        if n <= 9:
            return n
        n -= 9
        digit = 2
        while n - f(digit) > 0:
            n -= f(digit)
            digit += 1
        x, y = n // digit, n % digit
        if y == 0:
            return (10 ** (digit - 1) + x - 1) % 10
        
        return ((10 ** (digit - 1) + x) // 10 ** (digit - y)) % 10

暴力法，超时了

class Solution:
    def findNthDigit(self, n: int) -> int:
        import math
        m = -1
        for i in range(n + 2):
            m += len(str(i))
            if m == n:
                return int(i % 10)
            elif m > n:
                break
        t = m - n
        return int((i // math.pow(10, t)) % 10)