网龙 幸运数字 数据结构

题目描述

小雅同学认为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++;
    }
}