【算法题】自增自然数列组,求第N位的数字,数列如下112123123412345123456
首先,鄙视下出这个题目的人,人为增加难度,无聊。这个题目如果之前没见过,想短时间写出来还是需要一定的脑力的,一步一步抽丝剥茧吧:
①先把该数列看成如下形式:
1
12
123
12345
123456
……
这样我们可以将每个子串单独分析,可以看出来第i个子串比第i-1个子串多一个数i,数i的长度为log10(i)+1,也就是是说第i个子串比第i-1个子串的长度长log10(i)+1。
这样就可以知道第N个数是在哪一个子串里面了。
#define maxn 10000
int num[maxn];
void init()
{
num[0] = 0;
num[1] = 1;
for(int i = 2 ; i < maxn ; i ++)
{
num[i] = (num[i-1] + log10(i) + 1);
}
}
②在字串里面求出该位置对应的数字
这个问题可以简化为自然数列12345678910111213……第n位是什么数字,这个就简单了:
//分析:
/**
第一步:找出给定的 n 落在几位数的范围内
自然数序列中各个数的数字分布:
1-9: 1*9
10-99: 2*90
100-999: 3*900
……
即,i * 9 * 10^i
所以,总位数sum=sum+i*9*tens;(其中,i++; tens *= 10; )
比较即可知道 n 落在几位数范围内。
例如给定n = 150,
首先一位有9个数字,所以位数可以+1,这样n-9 = 141. 然后2位的数字有2*90= 180,大于141,所以目标数字肯定是2位的。
第二步:找到具体落在哪个数字
用10+(141-1)/2 = 80
第三步:找出具体在哪一位上
用(141-1)%2=0,求出该数字(80)的第0位(即8)
*/
好吧,这个其实是Leetcode上面第400题。
最近有时间,会逐渐把leetcode题目整理出来:https://github.com/cancoo/leetcode
class Solution {
public:
int findNthDigit(int n) {
int i=1;
long long tens=1;
long long sum=0;
while(sum<n)
{
sum+=i*9*tens;
++i;
tens*=10;
}
--i;
tens/=10;
sum-=i*9*tens;
//cal the gap with the lowest of this section
long long diff=n-sum;
long long resNum=tens+(diff-1)/i; //求出具体是哪个数字
int resBit=(diff-1)%i; //求出具体是这个数字的哪一位
//to string and return the resNum's resBit position
string s=to_string(resNum);
return s[resBit]-'0';
}
};
这里其实还是有些小坑的:首先是sum的类型,记得是long long,int太小了;然后是最后返回值,字符串记得要转换成数字(即减去'0')。
③接下来就简单了,①②组合下即可:
#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
using namespace std;
#define maxn 10000
int num[maxn];
void init()
{
num[0] = 0;
num[1] = 1;
for(int i = 2 ; i < maxn ; i ++)
{
num[i] = (num[i-1] + log10(i) + 1);
}
}
int findNthDigit(int n) {
int i=1;
long long tens=1;
long long sum=0;
while(sum<n)
{
sum+=i*9*tens;
++i;
tens*=10;
}
--i;
tens/=10;
sum-=i*9*tens;
//gap with the lowest of this section
long long diff=n-sum;
long long resNum=tens+(diff-1)/i;
int resBit=(diff-1)%i;
//return resBit;
//return resNum;
//to string and return the resNum's resBit position
string s=to_string(resNum);
int result = s[resBit]-'0';
cout<<result<<endl; // 这里会输出结果
return result;
//return s[resBit]-'0';
}
int main()
{
init();
int N=15, i=0, temp=-1;//这里的N就是需要求的第N位
long long total=0;
while(i<maxn)
{
i++;
if(N-num[i]>num[i])
{
temp=N-num[i];
break;
}
else
{
N-=num[i];
}
}
if(temp<0)
return -1; //error
else
findNthDigit(N);
}
有些小问题,极大数的边界问题,不改了。