剑指Offer系列(java版,详细解析)44.数字序列中某一位的数字
题目描述
剑指 Offer 44. 数字序列中某一位的数字
难度中等114收藏分享切换为英文接收动态反馈
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。
请写一个函数,求任意第n位对应的数字。
示例 1:
输入:n = 3
输出:3
示例 2:
输入:n = 11
输出:0
限制:
0 <= n < 2^31
测试用例
- 功能测试(输入10、190、1000等)
- 边界值测试(输入0、1等)
题目考点
- 考察应聘者优化的激情和能力。最原始的方法大部分应聘者都能想到。当面试官提示还有更快的方法之后,应聘者千万不要轻易放弃尝试。必要的时候可以要求面试官给出提示。
- 考察应聘者面对复杂问题的分析能力,可以通过分析具体例子一步步找到通用的规律。
解题思路
以第1001位数字7为例
步骤1:首先确定该数字是属于几位数的;
如果是一位数,n<9;如果是两位数,n<9+902=189;如果是三位数,n<189+9003=2889;
说明是三位数。(这里有个循环)
步骤2:确定该数字属于哪个数。100+(1001-190)/3= 370。
步骤3:确定是该数中哪一位。1001-190-(370-100)*3 = 1,所以位于“370”的下标为1的位置,即数字7
自己解题
class Solution {
public int findNthDigit(int n) {
int digit = 1;
long start = 1;
long count = 9;
while (n > count) { // 1.
n -= count;
digit += 1;
start *= 10;
count = digit * start * 9;
}
long num = start + (n - 1) / digit; // 2.
return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
}
}
参考解题
见自己解题
补充
- 当发现利用各种名算法以及数据结构不能解题的时候,很久可能就是利用规律来解题了(考察逻辑思维以及数据思维)。