Description
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3
Output:
3Example 2:
Input:
11
Output:
0Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.
描述
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 中找到第 n 个数字。
注意:
n 是正数且在 32 为整形范围内 (n < 231)。
示例 1:
输入:
3
输出:
3示例 2:
输入:
11
输出:
0 说明:
第 11 个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 0，它是 10 的一部分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
- 位数有 1 位的数有 9 个（1-9）；位数有 2 位的有 90 个（10-99）；位数有 3 位的有 900 个（100-999）；
- 我们先确定 n 对应的数应该是几位数，假设确定了 n 对应的数的位数为 t；我们再确定 n 在有 t 位的所有数中的位置 p；
- t 位数的第一个数位 x，则通过 x，p，t 可以确定题意所求；
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-09-02 07:41:16
# @Last Modified by: 何睿
# @Last Modified time: 2019-09-02 07:55:03
class Solution:
def findNthDigit(self, n: int) -> int:
a, b, start = self.__find_index(n)
return str(start + a - 1)[-1] if not b else str(start + a)[b - 1]
def __find_index(self, n: int) -> (int, int, int):
# cnt_digit：数字占用的位数
# cnt_zone：有 cnt_digit 个位的数的个数
# start：有 cnt_digit 个位的数的第一个数
cnt_digit, cnt_zone, start = 1, 9, 1
while n > cnt_zone * cnt_digit:# cnt_zone 消耗的总位数
n -= cnt_zone * cnt_digit
cnt_digit += 1
cnt_zone *= 10
start *= 10
a, b = divmod(n, cnt_digit)
return a, b, start 源代码文件在 这里。·
©本文首发于 何睿的博客，欢迎转载，转载需保留 文章来源，作者信息和本声明.