劍指Offer（第二版）面試題44：數字序列中某一位的數字

劍指Offer（第二版）面試題18：删除連結清單的節點

題目：

數字按照0123456789101112131415161718192021…的順序排列。第5位（從0開始計數）為5，第13位為1，第19位為4…… 求任意第n位對應的數字。

思路

• 直覺方法做枚舉。每枚舉一個數字的時候，求出該數字是幾位數，并把數字的位數和前面的所有數字的位數相加。當累加的數位大于n時，那麼第n位數字一定在這個數字裡。
• 當然正确的思路是找出某些規律跳過若幹數字。例如：序列前十位是0~9。接下來180位數字是90個10~99的兩位數。接下來的2700位是900個100~999的三位數。

代碼

#include <iostream>
#include <cmath>

using namespace std;

int core(int num);
int getSizeOfDigit(int i);
int getResult(int digit,int num);

int main()
{
    int num = ;
    while(num != -)
    {
    cout << "type a size" << endl;
    cin >> num;
    int result = core(num);
    cout << result << endl;
    }

    return ;
}

int core(int num)
{
    if(num < )
        return -;

    int digit = ;
    while(true)
    {
        int numbers = getSizeOfDigit(digit);
        if(num < numbers * digit)
            return getResult(digit,num);

        num -= digit * numbers;
        ++digit;
    }

}

int getSizeOfDigit(int i)
{
    if(i == )
        return ;
    return *std::pow(,i-);
}

int getResult(int digit,int num)
{
    int beginNum = ;
    if(digit == )
        beginNum = ;
    else
        beginNum = (int) std::pow(,digit - );

    int resultNum = beginNum + num/digit;
    int countFromRight = digit - num % digit;
    for(int i = ; i < countFromRight - ; ++i)
        resultNum /= ;
    return resultNum%;
}