剑指Offer44-数字序列中某一位的数字

兴趣爱好交流 每日一题
1

剑指Offer44-数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：


输入：n = 3

输出：3

示例 2：


输入：n = 11

输出：0

限制：

  • 0 <= n < 2^31

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof

一解

1.确定数字范围

数字范围 所有数字的位数和 count n -= count
1~9 9*1*1 n - 9
10~99 9*10*2 n - 9 - 180
100~999 9*100*3 n - 9 - 2700
1000~9999 9*1000*4 n - 9 - 360000

所有数字的位数和 count = 9 * start（数字范围的起始数字）* digit（每个数字位数），使用循环判断数字的范围：


count, start, digit = 9, 1, 1

while n > count:

    n -= count

    start *= 10

    digit += 1

    count = 9 * start * digit

n -= count用于计算 n 从 start 开始计数的第几位，比如n = 13， n - count = n - 9 = 4 ：

  • 180 > 13 > 9 表示处于数字范围 10(start)~99 内
  • 13 - 9 = 4 表示从 start 10 开始计数的第 4 位，10 11，也就是 1

2.确定所求数位所在数字

  • digit = 2
  • n = 4
  • strat = 10
  10 11 12
第几个数字 1 2 3

13 在从 10 起第二个数字，即 10 11，通过公式 (4 - 1) // 2可计算出 n 是第二个数字，即 11 ，num = start + (n - 1)//digit

3.确定所求数位在 num 的哪一位

  1 0 1 1 1 2
数字的第几位 1 2 3

13 在数字 11 的第二位，(4 - 1) % 2 = 1可计算在 11 的第二位。

res = int(str(num)[( n - 1) % digit])

答案


import math

class Solution:

    def findNthDigit(self, n: int) -> int:

        count, digit, start = 9, 1, 1

        while n > count:

            n -= count

            digit += 1

            start *= 10

            count = 9 * start * digit

        num = start + (n - 1)//digit

        return int(str(num)[(n - 1) % digit])
2

找规律

count=9
    wei=1
    start=1
    if n<10:
        return n
    while n>count:
        n=n-count
        start=10*start
        wei=wei+1
        count=9*start*wei
    if n%wei==0:
        number=n//wei+10**(wei-1)-1
    else:
        number=n//wei+10**(wei-1)
    res=(str(number))[(n%wei)-1]
    return int(res)