题目描述
数字序列中某一位的数字
样例
输入:13
输出:1
算法1
怎么说呢,先表明是抄答案的,但是思路都能对上,就是写不对,一些边界条件拿不准,代码写的很乱,一直写不对。这里应该算是一种技巧吧,功能函数化,感觉有些东西很乱的话,就将其功能独立成一个函数,自己再调用函数,防止主程序代码过于乱,疏忽边界条件。下面就是这种情况,我自己写总是写不对,剑指offer书上,对其进行函数功能独立化,很简洁。
主要的思路是想到了,但是就是做不对,主要的功能就是求出n位数的个数和其实数,具体详情看下述代码
时间复杂度
参考文献
C++ 代码
int countLength(int count)
{
if(count == 1)
return 10;
return pow(10,count-1) * 9;
}
int beginNumber(int count)
{
if(count == 1)
return 0;
return pow(10,count-1);
}
int digitAtIndex(int index,int digit)
{
int number = beginNumber(digit) + index/digit;
return to_string(number)[index % digit]-'0';
}
int digitAtIndex(int index) {
if(index < 0)
return -1;
int digit = 1;
while(1)
{
long number = countLength(digit);
if(index < number * digit)
return digitAtIndex(index,digit);
index -= digit * number;
digit++;
}
return -1;
}