网龙 幸运数字 数据结构
题目描述
小雅同学认为6,8是她的幸运数字,而其他数字均不是,一个幸运数是指在十进制表示下只含有幸运数字的数。给定你一个区间(a,b)a和b之间(其中包括a和b幸)运数的个数。
输入描述:
输入两个整数a和b,a的取值范围在1和1000000000之间(其中包括1和1000000000),b的取值范围在a和1000000000之间(其中包括a和1000000000)。
输出描述:
返回a和b之间的幸运数个数,如果入参不合法,请输出-1
示例1
输入
1 10
输出
2
说明
6,8,6666,88888,6668888,68686688均为幸运数字,当a=1,b=10函数返回值为2。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
#define MAX 1000000000
int lucky[maxn];
int top;
void init();
int main()
{
init();
int a,b,ansa=0,ansb=0;
cin>>a>>b;
for(int i=0;i<top;++i)
{
if(a<lucky[i])
{
ansa=i;
break;
}
}
for(int i=0;i<top;++i)
{
if(b<lucky[i])
{
ansb=i;
break;
}
}
if(ansb-ansa>0) //合法
{
cout<<ansb-ansa<<endl;
}else //不合法
{
cout<<"-1"<<endl;
}
return 0;
}
void init() //求出从小到大保存幸运数的数组
{
int i=0;
top=2;
lucky[0]=6; //第一个是6
lucky[1]=8; //第二个是8
while(1) //剩下的通过二叉树发现的规律用队列模拟
{
if(i>512) break;
lucky[top++]=lucky[i]*10+6;
lucky[top++]=lucky[i]*10+8;
i++;
}
}