leetcode_400 第 N 位数字

要求

给你一个整数 n ，请你在无限的整数序列[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并回来第n 位数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0
解说：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

中心代码

class Solution:
    def findNthDigit(self, n: int) -> int:
        flag,m = 9,9
        i = 1
        if n <= 9:
            return n
        while m < n:
            i += 1
            res = m
            m += flag * 10 ** (i -1) * i
        if (n - res) % i == 0:
            return int(str(10 ** (i - 1) + (n - res) // i -1)[-1])
        else:
            return int(str(10 ** (i - 1) + (n - res) // i)[(n - res) % i - 1])

超时代码

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n < 1:
            return 
        res = [str(i) for i in range(1,n + 1)]
        string = "".join(res)
        res = list(string)
        return int(res[n - 1])

解题思路：超时代码：思路较为简单可是会超时，咱们将n个数变成字符串加到一同，然后取出这个字符串的第n个字符。中心代码：

• 先确认第n个数字所在的数字是几位数的：1-9 是一位数、10-99是两位数（9+（99 - 10 + 1）* 2） … 以此类推、在代码中，能够核算出到第i位停止，共有多少位数字，假如大于n，说明n是在一个i位数中
• 在确认第n个数字在几位数的第几个数字的第几位即可，如ｎ＝15是2位数的第三个数字（12）的第二位，即第15个数字是2,i表明第n个数字的位数，res表明前i-1位共有多少位数字,n-res表明i位数字有几位，（n-res）整除i确认n在第几个数字，n-res对i求余确认i在该数字的第几位

自我了解中：榜首部分：从上面的while循环中咱们能看到一个规律，便是2位数时分，咱们加上的位数是(99-10+1)*2 = 90 * 2,便是3位数时分，咱们加上的位数是(999-100+1)*3 = 900 * 3,所以提取到的便是flag * 10 ** (i -1) * i,很简练的公式。第二部分：假定咱们的数字是124，咱们进入循环，i= 2,res=9,m =189>n,直接跳出循环，咱们i表明当时是两位数，n(124) – res(9) = 115,减去1位的数字的占位，然后咱们想要知道在第几个数字中，(n – res) // i 得到的是在的那位数字，(124 – 9)//2 = 57,假定(n – res) % i == 0，便是当时数字的最终一位，假定(n – res) % i != 0, 咱们还要找出来他在的那个数字的第几位，这个便是对上面的红字部分的解读。