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

class Solution {
public:
    int digitAtIndex(int n) {
        int digit = 1;
        int start = 0;
        long long cnt = 10;
        while (n >= cnt) {
            n -= cnt;
            digit++;
            if (start == 0) start = 10;
            else start *= 10;
            cnt = digit * start * 9LL;
        }

        int num = start + n / digit;
        int r = n % digit;
        for (int i = 0; i < digit - 1 - r; i++)
            num /= 10;
        return num % 10;
    }
};