本文主要是介绍《剑指offer第二版》题44:找寻数字序列中某一位的数字笔记记录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。请写一个函数,求任意第n位对应的数字。题目链接
1.解题步骤
解题步骤主要分为三步:
①求出第n位对应的数number的位数
②求出第n位对应的数number
③求出第n位对应数number的哪一个数字
2.数字,位数,位数数量之间的关系
通过列表格的形式来找到这几个关键点之间的联系:
数字范围 | 位数digit | 数字数量 | 位数数量count |
1-9 | 1 | 9 | 9 |
10-99 | 2 | 90 | 180 |
100-999 | 3 | 900 | 2700 |
start-end | n | 9 x start | 9 x start x end |
通过表格就可以看出第n位和位数数量之间存在范围关系:如果1<n<9,说明number位数为1位,如果9<n<189(180+9,n为累加),说明number位数为2位,以此类推。所以可以通过判断n的大小范围,得到位数。
3. 确定位数digit的代码实现
digit, start, count = 1, 1, 9
while n > count:n -= countdigit += 1start *= 10count = 9 *start * digit
通过while循环得到的digit就是第n位对应的数字number的位数。
4.确定对应的数字number的代码实现
number = start + (n-1) // digit
start对应的就是位数为digit的第一个数字,只要确定number是start开始的第几个数字,就能确定number的值。注意:while循环结束后的n已经为从start开始计算的下标:
number(每一格表示一位) | 1 | 0 | 1 | 1 | 1 | 2 | 1 | 3 |
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
n-1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
(n-1)//digit | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
(n-1)//digit刚好表示了自strat开始的第几个数字。
5. 确定n表示number的第几个数字代码实现
巧妙点:通过将number字符串化,使得number每一位都有了位置下标可以直接寻找到
sing = str(number)
res = int(sing[(n-1) % digit])
6.整体代码
class Solution:def findNthDigit(self, n: int) -> int:digit, start, count = 1, 1, 9while n > count:n -= countdigit += 1start *= 10count = 9 * start * digitnum = start + (n-1) // digitsing = str(num)res = int(sing[(n-1)%digit])return res
这篇关于《剑指offer第二版》题44:找寻数字序列中某一位的数字笔记记录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!