[剑指 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 位为 0 到 9，跳过，再从后面找 991 位；

2、后面 180 位为 10 到 99，因为一共 99-10+1=90 个数，每个数 2 位，所以 180 位； 跳过，再从后面找 811 位（1001-10-180=811）；

后面 2700 位为 100 到 999，因为 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/