草庐IT

LeetCode-400. 第N位数字

Garrett_Wale 2023-04-16 原文

题目来源

400. 第 N 位数字

题目详情

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

示例 1：

输入： n = 3
输出： 3

示例 2：

输入： n = 11
输出： 0
解释： 第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

提示：

  • 1 <= n <= 231 - 1

题解分析

本题的解题关键是如何定位到指定字符所在的数字。通过仔细观察序列数字串，可以发现，位数为1的数字个数为9，位数为2的数字个数为90，位数为3的数字个数为900，依次类推。

按照上述规律，可以进一步每种位数中包含的字符个数，它们是数字个数与位数的乘积。通过这种模拟法，可以首先求出所述字符是哪种位数的，进而根据除余运算可以计算出这个数字的具体指。最后，问题就转换为了求解某个具体数字的某位上的字符。

算法实现

class Solution {
    public int findNthDigit(int n) {
        // 9 * 1, 90 * 2, 900 * 3, 9000 * 4
        int bit = 1;
        long cnt = 9;
        while (bit * cnt < n) {
            n -= bit * cnt;
            bit++;
            cnt = cnt * 10; 
        }
        // rest表示在bit位数集中的第几字符位，减一是为了下标从0开始计算
        int rest = (int) (n - 1);
        // start表示bit位数集中的起始元素
        int start = (int) Math.pow(10, bit-1);
        // n是bit位数集中的第几个元素
        int pt = rest / bit;
        // num表示第n个字符所在的元素
        int num = start + pt;
        // seq表示对应元素的第几个字符（从左往右）
        int seq = rest % bit;

        // 后续问题转换为求num数字的第seq个字符是什么，1203

        // 去除第seq个字符后面数字后的结果
        int left = num / (int) Math.pow(10, bit - seq -1);
        return left % 10;
    }
}
LeetCode400strongcodeintJava

有关LeetCode-400. 第N位数字的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby-on-rails - 为什么用户必须输入 7 位数的 Twitter PIN 才能授予我的应用程序访问权限？ - 2

    我正在为我的用户实现一些ruby​​onrails代码推特内容。我正在创建正确的oauth链接...类似http://twitter.com/oauth/authorize?oauth_token=y2RkuftYAEkbEuIF7zKMuzWN30O2XxM8U9j0egtzKv但在我的测试帐户授予对twitter的访问权限后，它会弹出一个页面，上面写着“您已成功授予对.我不知道用户应该在哪里输入此PIN以及他们为什么必须这样做。我认为这不是必要的步骤。Twitter应该将用户重定向到我在应用程序设置中提供的回调URL。有谁知道为什么会这样？更新我找到了thisarticle声明我需

  3. ruby - 格式化数字以每隔三位数拆分一次 - 2

    我想在格式化数字时每隔三个字符放置一个空格。根据这个规范:it"shouldformatanamount"dospaces_on(1202003).should=="1202003"end我想出了这段代码来完成这项工作defspaces_onamountthousands=amount/1000remainder=amount%1000ifthousands==0"#{remainder}"elsezero_padded_remainder='%03.f'%remainder"#{spaces_onthousands}#{zero_padded_remainder}"endend所以我

  4. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  5. ruby - ruby 中的 400 个错误请求但不是 curl - 2

    我正在尝试在ruby​​中发出https发布请求，它在curl中工作，但我在ruby​​中收到400错误请求，我无法弄清楚原因。这是ruby代码:require'rubygems'require'net/https'require'uri'require'json'uri=URI.parse("https://api.parse.com/1/push")http=Net::HTTP.new(uri.host,uri.port)http.use_ssl=truehttp.verify_mode=OpenSSL::SSL::VERIFY_NONEreq=Net::HTTP::Post.ne

  6. ruby - 融合表 : Why do I keep getting a "400 Bad Request" error when trying to update a table style via Ruby's RestClient gem - 2

    我正在尝试使用RubygemRestClient为我的一个FusionTables更新样式。这是我的代码:require'rest_client'tableId=''styleId=''key=''table_url="https://www.googleapis.com/fusiontables/v1/tables/#{tableId}/styles/#{styleId}?key=#{key}"update='{"polygonOptions":{"strokeColor":"#ffffff"}}'token='STRINGCONTAININGAUTHORIZATIONTOKEN'R

  7. ruby - 不转换成字符串，一个Fixnum有多少位数？ - 2

    我想找到Fixnum的长度,num，而不将其转换为String。也就是说，在不调用.to_s()方法的情况下，num有多少位:num.to_s.length 最佳答案 putsMath.log10(1234).to_i+1#=>4您可以像这样将它添加到Fixnum:classFixnumdefnum_digitsMath.log10(self).to_i+1endendputs1234.num_digits#=>4 关于ruby-不转换成字符串，一个Fixnum有多少位数？，我们在Sta

  8. ruby - 生成一个7位数的随机数 - 2

    如何生成100万到1000万之间的随机数？rand(10)有效，我尝试了rand(1..10)但没有成功。 最佳答案 取你的基数1,000,000并添加一个从0到你的最大值的随机数-起始数:1_000_000+Random.rand(10_000_000-1_000_000)#=>3084592 关于ruby-生成一个7位数的随机数，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/

  9. ruby - 读取 400 响应的正文？ - 2

    我正在尝试使用rest-clientgem读取400响应的主体。问题是rest-client通过将其作为错误抛出来响应400，因此我想不出任何方法来获取正文。这是一个激励人心的例子。考虑对facebook图形API的调用:JSON.parse(RestClient.get("https://graph.facebook.com/me?fields=id,email,first_name,last_name&access_token=#{access_token}"))如果access_token过期或无效，facebook会做两件事:返回400BadRequestHTTP响应在响应正文

  10. ruby - 如何在 ruby 中将一位数字变成两位数字？ - 2

    Time.new.month返回10月之前任何月份的一位数表示(例如6月是6)，但我想要一个2位数格式(即而不是6我想要06)。我写了下面的解决方案，我想看看其他/更好的解决方案。s=6.to_s;s[1]=s[0];s[0]='0';s#=>'06' 最佳答案 为了你的需要我觉得最好的还是Time.strftime("%m")如前所述，但对于一般用例，我使用的方法是str=format('%02d',4)putsstr根据上下文，我也使用这个做同样事情的:str='%02d%s%04d'%[4,"astring",56]putss

随机推荐