1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 44 题] “数字序列中某一位的数字”做题记录

[剑指 Offer 第 2 版第 44 题] “数字序列中某一位的数字”做题记录

第 44 题:数字序列中某一位的数字

传送门:数字序列中某一位的数字

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中,第 5 位(从 0 开始计数)是 5 ,第 13 位是 1 ,第 19 位是 4 ,等等。

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

样例:

输入:13

输出:1

Python 代码:参考了 LeetCode 第 400 题讨论区代码

  class Solution(object):
        def digitAtIndex(self, n):
            """
            :type n: int
            :rtype: int
            """

            # 如果 n 小于 10 ,直接返回就可以了
            if n < 10:
                return n

            # 计算前缀部分

            base = 9
            digits = 1
            # 2 位数,从 10 到 99 一共 ( 99 - 10 + 1) * 2 = 90 * 2 = 180 位
            # 3 位数,从 100 到 999 一共 ( 999 - 100 + 1) * 2 = 900 * 3 = 2700 位
            # 4 位数,从 1000 到 9999 一共 ( 9999 - 1000 + 1) * 2 = 9000 * 4 = 3600 位

            while n - base * digits > 0:
                n -= base * digits
                base *= 10
                digits += 1


            index = n % digits
            if index == 0:
                # 计算出 num 是多少
                # 例如:192,有 1 个位移的偏差
                num = 10 ** (digits - 1) + n // digits - 1
                # 返回个位就可以了
                return num % 10
            else:
                # 不能整除,那个偏移就不用算了
                # 例如 194 = 189 + 5
                # 100 + 2 = 102
                num = 10 ** (digits - 1) + n // digits
                # 从左边向右边数,第 2 位
                for i in range(index, digits):
                    num //= 10
                return num % 10

参考资料:

1、https://www.acwing.com/activity/content/code/content/20758/

2、https://blog.csdn.net/Koala_Tree/article/details/79536284

[站外图片上传中…(image-a760ae-1558582697894)]

思路:跳过不同位数的数字,在相应位数中寻找。

以序列中第 1001 位为例:

1、序列前 10 位为 09,跳过,再从后面找 991 位;

2、后面 180 位为 1099,因为一共 99-10+1=90 个数,每个数 2 位,所以 180 位; 跳过,再从后面找 811 位(1001-10-180=811);

后面 2700 位为 100999,因为 811<2700,所以 811 位是某个三位数中的一位; 由于811=270*3+1,这就是说811位是从100开始的第270个数字即370的中间一位,即7。(注意,这里都是从第0位开始计数的)


作者:Koala_Tree 来源:CSDN 原文:https://blog.csdn.net/Koala_Tree/article/details/79536284 版权声明:本文为博主原创文章,转载请附上博文链接!

Java 代码:

  class Solution {  // 9*1  9*10*2  9*10*10*3
        public int digitAtIndex(int n) {
            int len = 1;
            long count = 9;
            int start = 1;

            while (n > len * count) {  //13  n=n-9=4 len=2 count=90 start=10 
                n -= len * count;      //start=10+3/2=11   答案是11的第二个1
                len += 1;
                count *= 10;
                start *= 10;
            }
            // start 记录当前循环区间的第一个数字,当 n 落到某一个确定的区间里了,
            // 那么 (n-1)/len 就是目标数字在该区间里的坐标,加上 start 就是得到了目标数字
            start += (n - 1) / len;
            String s = Integer.toString(start);
            return Character.getNumericValue(s.charAt((n - 1) % len));

        }
    }

参考资料:这篇简书上的文章有详细步骤。https://www.jianshu.com/p/0bbf1fcbe070。

同 LeetCode 第 400 题:400. 第 N 个数字

说明:只不过 LeetCode 第 400 题从 1 开始,传送门:400. 第 N 个数字

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。

注意: n 是正数且在32为整形范围内 ( n < 231)。

示例 1:

``` 输入: 3

输出: 3 ```

示例 2:

``` 输入: 11

输出: 0

说明: 第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是0,它是10的一部分。 ```

Python 代码:

  class Solution:
        def findNthDigit(self, n):
            """
            :type n: int
            :rtype: int
            """
            # 特判:如果 n 小于 10 ,直接返回就可以了
            if n < 10:
                return n

            # 表示几位数
            # 2 位数,从 10 到 99 一共 ( 99 - 10 + 1) * 2 = 90 * 2 = 180 位
            # 3 位数,从 100 到 999 一共 ( 999 - 100 + 1) * 2 = 900 * 3 = 2700 位
            # 4 位数,从 1000 到 9999 一共 ( 9999 - 1000 + 1) * 2 = 9000 * 4 = 3600 位

            # 步骤1:calculate how many digits the number has

            # 计算前缀部分
            length = 0
            base = 9
            digits = 1

            # n = 1001 时,9 过,180 过,剩下 812

            # 不越界才加,要清楚这一点
            while length + base * digits < n:
                length += base * digits
                base *= 10
                digits += 1

            n -= length

            # step 2. calculate what the number is
            # 到这里,num 是 "digits 位数" 中的某一个数字
            # 以 digits = 3 为例,n 是 100 - 999 中的一位,num 表示是哪个数字

            index = n % digits

            if index == 0:
                # 如果整除,就是那个数字的最后一位
                num = 10 ** (digits - 1) + n // digits - 1
                return num % 10
            else:
                num = 10 ** (digits - 1) + n // digits
                for i in range(index, digits):
                    num //= 10
                return num % 10


    if __name__ == '__main__':
        solution = Solution()
        n = 190
        result1 = solution.findNthDigit(n)
        print(result1)


作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 44 题] “数字序列中某一位的数字”做题记录

链接:https://www.javajike.com/article/3290.html

« [剑指 Offer 第 2 版第 42 题] “连续子数组的最大和”做题记录
[剑指 Offer 第 2 版第 45 题] “把数组排成最小的数”做题记录»

相关推荐

QR code