剑指offer44-数字序列中某一位的数字

原题(来源Leetcode)

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

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

示例 1:

输入: n = 3
输出: 3

示例 2:

输入: n = 11
输出: 0

限制:

  • 0 <= n < 2^31

注意:本题与主站 400 题相同:https://leetcode-cn.com/problems/nth-digit/

解法

思想

  1. 确定下标处在几位数区间(10,11...99两位数区间,100,101...999三位数区间,...)
  2. 确定下标在该区间的第几个数上(如:101是三位数区间的第2个数)
  3. 计算下标所处的实际数字以及在第几位

代码

class Solution {
    public int findNthDigit(int n) {
        if(n < 10) return n;
        // 防止溢出
        long base = 10;
        long k = 90;
        long num_n = 2;
        while(n>=base){
            long newBase = k*num_n+base;
            if(n<=newBase){
                long count = (n-base)/num_n;
                long in_count = (n-base)%num_n;
                long num = (long)Math.pow(10,num_n-1)+count;
                return (int) (long) (String.valueOf(num).charAt((int) in_count) - '0');
            }
            base = newBase;
            k = k*10;
            num_n+=1;
        }
        return 0;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer44-%e6%95%b0%e5%ad%97%e5%ba%8f%e5%88%97%e4%b8%ad%e6%9f%90%e4%b8%80%e4%bd%8d%e7%9a%84%e6%95%b0%e5%ad%97/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月14日
下一篇 2020年6月16日

相关推荐

  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    0110
  • 剑指offer45-把数组排成最小的数

    原题(来源Leetcode) 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" …

    算法 2020年6月11日
    0140
  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例1: 输入: 2.00000, 10 输出: 1024.00000 示例2: 输入: 2.10000, 3 输…

    算法 2020年1月5日
    0190
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0470
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    090
  • leetcode1013-将数组分成和相等的三个部分

    原题 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] +…

    算法 2020年3月11日
    0560
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0140

发表回复

登录后才能评论