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

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

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

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

示例 1:


输入:n = 3

输出:3

示例 2:


输入:n = 11

输出:0

限制:

  • 0 <= n < 2^31

来源:力扣(LeetCode)

链接:力扣

一解

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 = 13n - 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])

找规律

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)
关闭