剑指44：数字序列中某一位的数字

传送门

nowcoder
leetcode

题目描述

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。
在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第 n 位对应的数字。

C++ 代码 - nowcoder

class Solution {
public:
    int findNthDigit(int n) {
        if (n == 0) return 0;
        return findNthDigitCore(n);
    }

    int findNthDigitCore(int n) {
        // 按位计数从 0 开始
        n --;

        // 枚举所有可能的位数
        for (int i = 1; i <= 11; i ++) {
            long firstNum = pow(10, i - 1);
            long lastNum = pow(10, i) - 1;
            long bitNums = lastNum - firstNum + 1;
            long totalNums = bitNums * i;
            // cout << "firstNum: " << firstNum
            //      << ", lastNum: " << lastNum
            //      << ", bitNums: " << bitNums
            //      << ", totalNums: " << totalNums << endl;
            if (n < totalNums) {
                int numTimes = n / i;
                int numIndex = n % i;
                int targetNum = firstNum +numTimes;
                string targetStr = to_string(targetNum);
                // cout << "n: " << n
                //      << ", numTimes: " << numTimes
                //      << ", numIndex: " << numIndex
                //      << ", targetNum: " << targetNum << endl;
                return targetStr[numIndex] - '0';
            }
            n -= totalNums;
        }

        return -1;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    int findKthNumber(int n) {
        if (n == 0) return 0;
        return findKthNumberCore(n);
    }
    
    int findKthNumberCore(int n) {
        // 按位计数是从 0 开始
        n --;

        for (int bit = 1; bit <= 11; bit++) {
            long firstNum = pow(10, bit - 1);
            long lastNum = pow(10, bit) - 1;
            long bitNums = lastNum - firstNum + 1;
            long totalNums = bitNums * bit;
            // cout << "firstNum: " << firstNum
            //      << ", lastNum: " << lastNum
            //      << ", bitNums: " << bitNums
            //      << ", totalNums: " << totalNums << endl;
            if (n < totalNums) {
                int numTimes = n / bit;
                int numIndex = n % bit;
                int targetNum = firstNum + numTimes;
                string targetStr = to_string(targetNum);
                // cout << "n: " << n
                //      << ", numTimes: " << numTimes
                //      << ", numIndex: " << numIndex
                //      << ", targetNum: " << targetNum << endl;
                return targetStr[numIndex] - '0';
            }
            n -= totalNums;
        }

        return -1;
    }

    // leetcode 400. 解法
    int findKthNumberCore2(int n) {
        int digit = 1; // 数位（个位, 十位2, 百位3, ...）
        long base = 1;  // 该数位的起始数（1, 10, 100, 1000, ...）
        long index_cnt = 9 * base * digit; // 该数位的索引个数（不是数字个数）

        while (index_cnt < n) {
            n -= index_cnt;
            base *= 10;
            digit ++;
            index_cnt = 9 * base * digit; 
            // cout << "n: " << n 
            //      << ", base: " << base
            //      << ", digit: " << digit
            //      << ", index_cnt: " << index_cnt << endl;
        }

        // 假设 base = 1000，说明 n 是 100~999 中某个三位数的某一位
        // 这个数，这样算：
        long val = base + (n - 1) / digit;
        // 这个数的第几位，这样算：
        int index = (n - 1) % digit;
        cout << "val: " << val 
            << ", index: " << index << endl;

        // val 第 index 位数字
        string valStr = to_string(val);
        return valStr[index] - '0';
    }
};