专栏首页专知关关的刷题日记90 – Leetcode 400. Nth Digit

关关的刷题日记90 – Leetcode 400. Nth Digit

关关的刷题日记90 – Leetcode 400. Nth Digit

题目

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个数字是多少。

思路

思路:我们可以把这些数字写出来找下规律,每个数由一个数字构成的数有9个,每个数由2个数字构成的数有90个,每个数由3个数字构成的数有900个,每个数由n个数字构成的数有9*10n-1个。我们首先要找出第n个数字落在几位数上,然后找到具体落在哪个数上,然后找到落到这个数的第几位上,最后锁定是哪一个数字。每一步都需要细心耐心。

class Solution {
public:
    int findNthDigit(int m) {
        int digit=1,flag;
        long c=1, target=0, n=m;
        //求出数字n落在digit位数上
        while(n>0)
        {
            n-=c*digit*9;
            digit++;
            c*=10;
        }

        //求出数字n是digit位数的第几个数字
        n+=(--digit)*(c/10)*9;

        //求出数字n是落在哪一个数上
        target=(n-1)/digit+c/10;  //

        //求出数字n是落在target左数第flag个数字上
        flag=(n-1)%digit+1;

        //求出target的右数第digit-flag+1数字
        return target/(int)pow(10,digit-flag)%10;       
    }
};

人生易老,唯有陪伴最长情,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

本文分享自微信公众号 - 专知(Quan_Zhuanzhi),作者:关关

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器人取代工人?没那么夸张

    WZEARW
  • 【干货】追本溯源:5种受生物启发的人工智能方法

    【导读】1月15日,机器学习研究人员Luke James(简介见文末)发布一篇博文,介绍了5种受到生物启发的人工智能方法,包括人工神经网络(人脑神经元)、遗传算...

    WZEARW
  • 【干货】深度学习中的数学理解— 教你深度学习背后的故事

    【导读】如今,深度学习在各项任务中所向披靡,比如图像识别,语音处理和自然语言处理。但是,深度学习的理论探讨却比应用滞后好几个数量级,一方面是做应用马上能见效,然...

    WZEARW
  • Luhn算法检验和验证

    Zoctopus
  • 第38章 用访问控制列表实现包过滤

    版权声明:本文为博主-姜兴琪原创文章,未经博主允许不得转载。 https://blog.csdn.net/jxq0816/article/details/180...

    week
  • 在windows下配置sendmail服务器

    终于还是成功了,差点没放弃。由于之前在做一个异常处理的时候用到了邮件提醒功能,所以顺便研究了一下在php下如何发送邮件。

    梁规晓
  • 如何理解 RESTful 的幂等性

    HTTP幂等方法,是指无论调用多少次都不会有不同结果的 HTTP 方法。不管你调用一次,还是调用一百次,一千次,结果都是相同的。

    芋道源码
  • Asp.Net WebApi核心对象解析(一)

        生活需要自己慢慢去体验和思考,对于知识也是如此。匆匆忙忙的生活,让人不知道自己一天到晚都在干些什么,似乎每天都在忙,但又好似不知道自己到底在忙些什...

    彭泽0902
  • 基于Django的电子商务网站开发(连载4)

    安装完毕Python,接下来来安装Django,关于Django安装有以下四种方法。

    小老鼠
  • Microsoft® .NET Micro Framework简介

    MF全称Microsoft® .NET Micro Framework,是微软推出的一个微型.Net框架,微型到什么程度呢?它自身就可以是一个操作系统OS,它...

    大石头

扫码关注云+社区

领取腾讯云代金券