- 前言
- 一、例题
- 1、题目
- 2、示例
- 二、题解
- 1、找规律
- 2、示例
- 3、Code
- 总结
- 参考文献
一、例题 1、题目找到问题中的规律，根据规律来完成代码。
2、示例数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3
输出：3
二、题解 1、找规律示例 2：
输入：n = 11
输出：0
| 范围数 | 多少个数 | 几位数（bitCount） | 共占多少位（多少个数 x 几位数） |
|---|---|---|---|
| 1~9 | 9 | 1 | 9 x 1 = 9 |
| 10~99 | 99 - 10 + 1 = 90 | 2 | 90 x 2 = 180 |
| 100~999 | 999 - 100 + 1 = 900 | 3 | 900 x 3 = 2700 |
第200个数，
=> 200 = 9 + 180 + 11，
=> bitCount = 3，surplus = 11，
=> data = 100 + (11 - 1) / 3 = 103，index = (11 - 1) % 3 = 1
=> result = "103".charAt(1) - '0' = '0' - '0' = 0;
public int findNthDigit(int n) {
int surplus = n;
int bitCount = 1;
long base = 1;
long count = 9;
while (surplus > count) {
surplus -= count;
base *= 10;
bitCount++;
count = bitCount * 9 * base;
}
long data = base + (surplus - 1) / bitCount;
int index = (surplus - 1) % bitCount;
return Long.toString(data).charAt(index) - '0';
}
总结
1）细心找到其中的规律，该题的规律就是如何定位？
参考文献[1] LeetCode 原题
[2] LeetCode用户评论
