首页 > 考试 > 其他 >

【leetcode】400. Nth Digit(Python & C++)

2017-09-14

【leetcode】400 Nth Digit(Python & C++)。

【leetcode】400. Nth Digit(Python & C++)。

400.1 题目描述:

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.

400.2 解题思路:

思路一:分三步走,

第一步确定是在哪几位数之间 第二步确定是哪个数 第三步确定是这个数的哪一位数

举个例子,比如n=23456,在9+90*2+900*3和9+90*2+900*3+9000*4之间,所以说明,这个数在1000-9999之间,是一个四位数。

一位数时,9*1=9个
二位数时,90*2=180个,
三位数时,900*3=2700个,
。。。。

以此类推,

所以设置long型变量,base代表每位数的个数,9,90,900。。。,ith代表每位数开始的那个数,1,10,100。。。,digit代表几位数,1,2,3。。。这样,循环时,判断n与base*digit的大小,进入n、base、ith、digit的调整。

23456-9-90*2-900*3=20567,

也就是,从1000开始,数20567位,那到底是落在哪个数字上呢?

1000+(20567-1)/4=6141,

所以说,在6141的某一位上,就是第n=23456位数,那到底是哪一位呢?

(20567-1)%4=2,

这说明,在6141的第3位上,也就是4。

注意的是,这里最后计算是哪个数、哪一位时,要减去1,这是因为整除代表某个数的最后一位,所以需要减1。

400.3 C++代码:

1、思路一代码(3ms):

class Solution119 {
public:
    int findNthDigit(int n) {
        long digit = 1;//确定是哪一位
        long base = 9;//每位的数的个数
        long ith = 1;//起始值
        while (n>base*digit)
        {
            n = n - base*digit;
            digit++;
            ith = ith + base;
            base = base * 10;
        }
        return to_string(ith + (n - 1) / digit)[(n - 1) % digit] - &#39;0&#39;;
    }
};

400.4 Python代码:

1、思路一代码(52ms)

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        digit=1
        base=9
        ith=1
        while n>base*digit:
            n=n-base*digit
            digit=digit+1
            ith=ith+base
            base=base*10
        return ord(str(ith+(n-1)/digit)[(n-1)%digit])-ord(&#39;0&#39;)  

相关文章
最新文章
热点推荐