剑指offer——44. 数字序列中的某一位数字

44. 数字序列中的某一位数字

题目描述

数字以 0123456789101112131415… 的格式序列化到一个字符串中，求这个字符串的第 index 位。

解题思路

/*
0-9 ：一位数 10个数 一个循环
10-99：二位数 90个数 90x2位
100-999：三位数 900个数 900x3位
考虑摘除0 考虑一位数从1-9

例如第1000位，
1、判断几位数  1000-9-90*2=811位 < 900*3 证明在三位数的第911位
2、确定是几位数的第几个  811/3=270...1 证明是100+271 - 1=403的第一位3 （因为后面第304位 其实代表303）

例如第13位
1、判断几位数  13-9=4位 < 90*3 证明在二位数的第4位
2、确定是几位数的第几个  4/2=0 证明是10+2 - 1 =11的第最后一位（无余数）

***/

class Solution {
public:
    int digitAtIndex(int n) {
        //if(n == 0) return 0;
        //x:一位数有9个数 
        //num:循环得到n属于几位数  表示几位数
        //data:表示n指向的数值 404
        //index:循环得到n属于几位数的第几位 2
        long long x = 9;
        int num = 1, data = 0, index = 0;
        //1、判断几位数 n= 1000-9-90*2=911位 < 900*3 证明在三位数的第911位
        while(n > x*num)
        {
            n -= x*num;
            x *= 10;
            num ++;
        }
        //cout << n << " " <<num<< " "<< x <<endl;
        //2、确定是几位数的第几个  910/3=303...2 证明是100+304=404的第二位0
        index = n % num; //循环得到n属于几位数的第几位 2
        data = pow(10, num -1) + n / num -1 + ((index > 0)? 1 : 0); //index 如果有余数 则应该+1 
        cout << n << " "<< num << " " << x <<" "<< index <<" "<< data<< endl;
        //返回数据 404的第二位0 余数index=0，1，2  倒数num-index 
        if(index == 0) return data % 10; //无余数 返回最后一位
        else return (int)(data / pow(10, num - index)) % 10; //有余数 
    }
};