当前位置: 首页 > news >正文

剑指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.
    }
}

参考解题

见自己解题

补充

  1. 当发现利用各种名算法以及数据结构不能解题的时候,很久可能就是利用规律来解题了(考察逻辑思维以及数据思维)。

相关文章:

  • 剑指Offer系列(java版,详细解析)45.把数组排成最小的数
  • 剑指Offer系列(java版,详细解析)46.把数字翻译成字符串
  • 剑指Offer系列(java版,详细解析)47.礼物的最大价值
  • 剑指Offer系列(java版,详细解析)48.最长不含重复字符的子字符串
  • 剑指Offer系列(java版,详细解析)49.丑数
  • 剑指Offer系列(java版,详细解析)50.第一个只出现一次的字符
  • 剑指Offer系列(java版,详细解析)51.数组中的逆序对
  • 剑指Offer系列(java版,详细解析)52.两个链表的第一个公共节点
  • 剑指Offer系列(java版,详细解析)53.在排序数组中查找数字
  • 剑指Offer系列(java版,详细解析)54.二叉搜索树的第K大的节点
  • 剑指Offer系列(java版,详细解析)55.二叉树的深度
  • 剑指Offer系列(java版,详细解析)56.数字中数字出现的次数
  • 剑指Offer系列(java版,详细解析)57.和为s的数字
  • 剑指Offer系列(java版,详细解析)58.翻转字符串
  • 剑指Offer系列(java版,详细解析)59.队列的最大值
  • [case10]使用RSQL实现端到端的动态查询
  • 【React系列】如何构建React应用程序
  • 【前端学习】-粗谈选择器
  • canvas 五子棋游戏
  • CentOS7 安装JDK
  • express如何解决request entity too large问题
  • HTML-表单
  • JDK9: 集成 Jshell 和 Maven 项目.
  • MySQL主从复制读写分离及奇怪的问题
  • Python 使用 Tornado 框架实现 WebHook 自动部署 Git 项目
  • React的组件模式
  • seaborn 安装成功 + ImportError: DLL load failed: 找不到指定的模块 问题解决
  • 后端_MYSQL
  • 基于Mobx的多页面小程序的全局共享状态管理实践
  • 离散点最小(凸)包围边界查找
  • 实战:基于Spring Boot快速开发RESTful风格API接口
  • 数据可视化之 Sankey 桑基图的实现
  • 《码出高效》学习笔记与书中错误记录
  • ​HTTP与HTTPS:网络通信的安全卫士
  • #Linux(make工具和makefile文件以及makefile语法)
  • ( 用例图)定义了系统的功能需求,它是从系统的外部看系统功能,并不描述系统内部对功能的具体实现
  • (NO.00004)iOS实现打砖块游戏(十二):伸缩自如,我是如意金箍棒(上)!
  • (仿QQ聊天消息列表加载)wp7 listbox 列表项逐一加载的一种实现方式,以及加入渐显动画...
  • *_zh_CN.properties 国际化资源文件 struts 防乱码等
  • .axf 转化 .bin文件 的方法
  • .equals()到底是什么意思?
  • .libPaths()设置包加载目录
  • .NET BackgroundWorker
  • .Net core 6.0 升8.0
  • .NET HttpWebRequest、WebClient、HttpClient
  • .net6Api后台+uniapp导出Excel
  • .NET版Word处理控件Aspose.words功能演示:在ASP.NET MVC中创建MS Word编辑器
  • .net中的Queue和Stack
  • [20150321]索引空块的问题.txt
  • [3D基础]理解计算机3D图形学中的坐标系变换
  • [bzoj4240] 有趣的家庭菜园
  • [C#] 基于 yield 语句的迭代器逻辑懒执行
  • [C/C++]_[初级]_[关于编译时出现有符号-无符号不匹配的警告-sizeof使用注意事项]
  • [DP 训练] Longest Run on a Snowboard, UVa 10285
  • [EFI]DELL XPS13 9360电脑 Hackintosh 黑苹果efi引导文件