LeetCode 400. Nth Digit

LeetCode 400. Nth Digit

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:
3

Example 2:

Input:
11

Output:
0

Explanation:
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/problems/nth-digit
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路

  • 位数有 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

源代码文件在 这里 。


©本文是原创文章,欢迎转载,转载需保留 文章来源 ,作者信息和本声明.

Posted in LeetCode and tagged , .

花若盛開,蝴蝶自來. 分享学习,每天进步一点点

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.