LeetCode 400. 第N个数字（数学）

示例 1:
输入:
3
输出:
3

示例 2:
输入:
11
输出:
0
说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 1--0--, 11, ... 里是0，它是10的一部分。

class Solution {
public:
    int findNthDigit(int n) {
        if(n < 10)
        	return n;
        long len = 9;
        int i = 2, k = 10, num=9;
        while(len+i*9*pow(10,i-1) < n)
        {
        	len += i*9*pow(10,i-1);
        	num += 9*pow(10,i-1);
        	i++;
        }
        if((n-len)%i)
            num += (n-len)/i + 1;
        else
            num += (n-len)/i;
        string s(to_string(num));
        return s[((n-len)%i + i -1)%i]-'0';
    }
};

class Solution {	//2020.2.24
public:
    int findNthDigit(int n) {
        if(n < 10)
            return n;
        int count = 9, i = 2, num = 9;
        while(count+9*pow(10,i-1)*i <= n)
        {
            count += 9*pow(10,i-1)*i;
            num += 9*pow(10,i-1);
            i++;
        }
        n -= count;//剩余的位数
        if(n%i != 0)//不等于0，下一个数的，第几位
            return fd(num+n/i+1,n%i);
        return fd(num+n/i,i);//否则，当前数的，最后一位
    }

    int fd(int num, int n)
    {
        int i = int(1e9);
        int bit;
        while(num/i == 0)
            i /= 10;
        while(n--)
        {
            bit = num/i;
            num -= bit*i;
            i /= 10;
        }
        return bit;
    }
};