通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

leetcode 剑指 Offer 44. 数字序列中某一位的数字

394人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/902

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。

请写一个函数,求任意第n位对应的数字。

示例 1:

输入:n = 3
输出:3

示例 2:

输入:n = 11
输出:0

限制:

  • 0 <= n < 2^31

难度:中等; 标签:数学;编程语言:C++


我的解法

class Solution {
public:
    // c++重写
    int findNthDigit(int n) {
        long num[11] = {0};
        num[1] = 9;
        for(int i = 2; i <= 10; i++){
            num[i] = num[i - 1] / (i - 1) * 10 * i; 
        }
        for(int i = 2; i <= 10; i++){
            num[i] += num[i - 1];
        }

        int i = 0;
        while(num[++i] < n);
        n -= num[i-1];
        
        int base = 1;
        for(int j = 2; j <= i; j++)base*=10;
        base += n / i - 1;
        int mod = n % i;
        if(mod != 0){
            base++;
        }else{
            mod = i;
        }

        int res = -1;
        while(mod++ <= i){
            res = base % 10;
            base /= 10;
        }

        return res;
    }
};

首先我们要知道,1位数1~9有9个,2位数10~99有90个,3位数100~999有900个,。。。。我们先确定是几位数,如7位数,减掉1~6位数产生的序列和,然后找到这个7位数是多少,即然都是7位数了,/7一下应该就差不多找到了(因为1位数实际有10个,还有一个0,要-1),然后%7就是这个7位数的第几位了,最后return一下


其它解法

class Solution {
public:
    int findNthDigit(int n) {
        long digit = 1,start = 1,count = 9;  //位数,起始数字,数位数量
        while(n > count){
            n -= count;
            start *= 10;
            digit++;
            count = 9 * digit * start;
        }
        //对应的数字:由start开始,位数为digit,第n/digit位
        long num = start + (n - 1)/ digit;
        int res = to_string(num)[(n - 1)% digit] - '0';
        return res;
    }
};

方法差不多,但写法很简洁, 有了上面的分析,这里就比较容易理解了


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告