剑指offer p225

思路：分析规律。
当数字位数为1时，表示的范围从0-9，总数为10，共10个数字；
当数字位数为2时，表示的范围从10-99，总数为90，共2x90=180个数字；
当数字位数为3时，表示的范围从100-999，总数为900，共3x900=2700个数字；
......
举例，若Index=1001，
1001>10，跳过一位数字的10个数，1001-10=991；
991>180,跳过两位数字的180个数，991-180=811；
811<2700,所以第811位是某个三位数中的一位。由于811=270*3+1，这意味着第811位是从100开始的第270个数字即370的中间一位，也就是7。

千万要注意的是：计算出了index是某个n位数的第几个数之后，还要加上n位数开始的数字。例如上例中，计算出了811是3位书中的第270个数，这个数的计算是从3位数的开始100加起来的，所以最终位数还得加上100才能代表整体的次序，100+270=370。

代码：

#include <iostream>
#include<algorithm>
#include<math.h>
#include<string>
using namespace std;


//计算digits位数的表达范围个数，例如1表达范围：0-9，10个数；2位数的表达范围10-99，90个数...
int countOfIntegers(int digits)
{
    if (digits == 1)
        return 10;
    else
        return 9 * pow(10, digits - 1);
}

//计算digits位数开始的第一位数，例如digit=1,开始数为0，digits=2,开始位为10.
int beginNumber(int digits)
{
    if (digits == 1)
        return 0;
    return pow(10, digits-1);
}
//确定index表示的是几位数
int digitIndex(int index)
{
    if (index < 0)
        return -1;
    if (index <= 9)
        return index;
    int digits = 0;
    while (index > 0)
    {
        digits++;
        index -= digits * countOfIntegers(digits);
    }
    index += digits * countOfIntegers(digits);    
    //numbers是在从0开始的数字中的次序，residual是index在数字numbers中的位置
    int numbers = beginNumber(digits)+index / digits, residual = index % digits;
    //将数字转化为string类型好取出其中的数字，但是要记得最后返回时将str类型的数字换成int型
    string str = to_string(numbers);    
    return str[residual] - '0';;
}
int main()
{
    int index = 99;
    cout << digitIndex(index) << endl;
    return 0;
}