剑指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%;
}