p400

发表于 | 分类于 |

LeetCode p400 Nth Digit 题解

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.

题意：

按顺序规律写数字，每个位置上只能放一位数字，求第n个位置上的数字。

2.解题思路:

数学规律计算推到
orz被边界条件折腾好久&注意溢出。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
public class Solution {
    public int findNthDigit(int n) {
        int len = 1;
		long count = 9; // 不然会溢出
		int start = 1;
		while (n - len * count > 0) {
			n = (int) (n - len * count);
			len++;
			count = count * 10;
			start = start * 10;
		}
		int i = start + (n - 1) / len;
		String s = i + "";
		return s.charAt((n - 1) % len) - '0';
	}
}

4.一些总结：