requirements
Give you an integer n, ask you in an infinite sequence of integers [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,…] Find and return the NTH digit.
Example 1:
Input: n = 3 Output: 3Copy the code
Example 2:
Input: n = 11 Output: 0 Explanation: 11th digit in sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11... It's 0, it's part of 10.Copy the code
The core code
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])
Copy the code
Timeout code
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])
Copy the code
We take n numbers and add them together, and then extract the NTH character of the string. Core code:
- Determine the number of digits in the NTH digit: 1-9 is a single digit and 10-99 is a two-digit number
9+ (99-10 + 1) * 2
… And so on, in the code, we can calculate how many digits up to the i-th digit, if greater than n, it means that n is in an I-digit - If n = 15 is the second place of the third 2-digit number (12), the 15th digit is 2.
I is the number of digits in the NTH digit
.Res indicates how many digits precede the i-1 digits
.N-res indicates how many bits there are in an i-digit number
.(n-res) divisible by I determines the number in which n is
.N-res mod I to determine what digit I is in that number
In self Understanding: Part I: We can see from the above while loop that when we add two digits, we add (99-10+1)*2 = 90 *2, which is when we add three digits, The number of bits we added is (999-100+1)*3 = 900 *3, so what we extract is flag * 10 ** (i-1)* I, very neat formula. Part II: Let’s say our number is 124, we go into the loop, I = 2,res=9,m =189>n, we jump out of the loop, we say I is the current two-digit number, n(124) -res (9) = 115, minus the space of the 1-digit number, and then we want to know in which digit, (n-res)// I yields the number in, (124-9)//2 = 57, assuming (n-res) % I == 0, the last digit of the current number, assuming (n-res) % I! Lambda is equal to 0, and we have to figure out what digit he is in, so that’s the interpretation of the scarlet letter up there.