幸运数字

//用字符串超时超内存,int取余就好.
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int start=sc.nextInt();
            int end=sc.nextInt();
            if(start<1||end>1000000000||start>end){
                System.out.println(-1);
                return;
            }
            int count=0;
            for(int i=start;i<=end;i++){
                int temp=i;
                while(temp>10&&(temp%10==6||temp%10==8)){
                    temp=temp/10;
                }
                if(temp==6||temp==8){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

/**
 * f[i][j]表示长度为i, 以j为开头的幸运数字个数
 * 如f[1][0] = 0, f[1][6] = 1, f[1][8] = 1
 * 转移方程如下：
 * f[i][0] = f[i-1][6] + f[i-1][8] + f[i-1][0];
 * f[i][6] = f[i-1][6] + f[i-1][8];
 * f[i][8] = f[i-1][6] + f[i-1][8];
 *
 * 时间复杂度为数字的位数log(10, n)
 */
class Solution {

    private static int[][] f = new int[11][10];

    static {
        f[1][6] = 1;
        f[1][8] = 1;
        for (int i = 2; i <= 10; i++) {
            f[i][0] = f[i-1][6] + f[i-1][8] + f[i-1][0];
            f[i][6] = f[i-1][6] + f[i-1][8];
            f[i][8] = f[i-1][6] + f[i-1][8];
        }
    }

    public int numOfLuckNumber(int n) {
        if (n <= 0) return 0;
        int[] b = new int[10];
        int m = 0;
        while (n > 0) {
            b[m++] = n % 10;
            n /= 10;
        }

        int ans = f[m][0];
        boolean tag = true;
        for (int i = m-1; i >= 0; i--) {
            for (int j = 1; j < b[i]; j++) {
                ans += f[i+1][j];
            }
            if (b[i] != 8 && b[i] != 6) {
                tag = false;
                break;
            }
        }
        if (tag) ans++;
        return ans;
    }
}

#这个代码比较乱，但可以顺序输出结果。已AC
while True:
    try:
        a, b = map(int, input().split())
        if 1 <= a <= 1000000000 and a <= b <= 1000000000:
            res = [0]         #保存幸运数个数
            temp = list(str(a))
                 
            #找出范围内最小的幸运数
            for i in range(len(temp)):
                if temp[i] == '6' or temp[i] == '8':
                    continue
                if temp[i] == '9':
                    temp[i] = '6'
                    for j in range(i - 1, -1, -1):
                        if temp[j] == '6':
                            temp[j] = '8'
                            break
                    else:
                        temp.insert(0, '6')
                elif temp[i] == '7':
                    temp[i] = '8'
                else:
                    temp[i] = '6'
                temp[i + 1: len(temp)] = ['6'] * (len(temp) - (i + 1))
                break
           #此时temp保存着最小的幸运数十进制位数的数组            

            #递归查找结果函数
            def pathThrought(index):
                if index == len(temp) - 1:
                    nowNum = int(''.join(temp))     #此时得到一个幸运数
                    if nowNum <= b:
                        res[0] += 1                 #可在此处输出nowNum
                        if temp[-1] == '6' and nowNum + 2 <= b:
                            res[0] += 1             #nowNum + 2也为一个幸运数
                else:
                    pathThrought(index + 1) #进来的时候temp[index]为6，递归一次
                    temp[index] = '8'       
                    pathThrought(index + 1) #置为8再递归一次
                    temp[index] = '6'       #赋值回去6
            
            #调用递归的过程
            while int(''.join(temp)) <= b:
                pathThrought(len(temp) - 1)
                for i in range(len(temp) - 2, -1, -1): #从末尾位数开始
                    if temp[i] == '8':       #当前位数不能再增大，跳过
                        continue
                    temp[i] = '8'            #本为6，增大为8，然后将右边位数置为6
                    temp[i + 1:] = ['6'] * (len(temp) - i - 1)
                    if int(''.join(temp)) > b:
                        break
                    pathThrought(i + 1)        #进行递归
                
                temp = ['6'] * (len(temp) + 1) #当前位数循环结束，增加位数继续
            print(res[0])

        else:   # a > b的情况
            print(-1)
    except ValueError:  #参数不正确的情况
        print(-1)
    except Exception:
        break

#include <bits/stdc++.h>

using namespace std;

bool F(int n){     while(n){         int t = n%10;         if(t!=8 && t!=6)             return false;         n /= 10;     }     return true;
}

int main()
{     int a,b,cnt=0;     cin>>a>>b;     if(a<1 || a>1000000000 || b<1 || b>1000000000 || a>b)          cout<<-1<<endl;     else{         for(int i=a;i<=b;i++)             if(F(i))                 cnt++;         cout<<cnt<<endl;     }     return 0;
}

l = []
def ran(a,x):
    if a == 0:
        l.append(int(x))
        return
    ran(a-1,x+'6')
    ran(a-1,x+'8')
lucky = '68'
for i in range(1,10):
    ran(i,'')
a,b = map(int,input().split())
if a>=1 and a<=1000000000 and b>=1 and b<=1000000000:
    index1,index2 = -1,-1
    for i in range(len(l)):
        if l[i]>=a:
            index1 = i
            break
    for i in range(len(l)):
        if l[i]>=b:
            index2 = i
            break
    if index1==-1:
        print(0)
    elif index2 == -1:
        print(len(l)-index1)
    else:
        print(index2-index1)
else:
    print(-1)

//DFS + string 写法， 思路相当于是枚举，枚举幸运数的过程中，记录可行的（当然不是全部枚举）
//分别从6 和 8 开始每次从尾部开始分别 +“6” 或者 +“8”
#include <iostream>
#include <string.h>
using namespace std;
int ans = 0;    //全局的，所有在程序内的对ans的操作都会被记录下来
string a = "";      //上下界均为string类型的，操作的时候也好操作，比较的时候需要注意下
string b = "";

void DFS(string temp_str)
{
    if (temp_str.length() > b.length() || (temp_str.length() == b.length() && temp_str.compare(b) > 0))
    return;    //出口条件为 当前的temp_str大于上界b的时候，就要跳出
    else
    {
        if (temp_str.length() > a.length() || (temp_str.length() == a.length() && temp_str.compare(a) >= 0))
        ans++;   //满足上面的非出口条件就一定小于上界，然后满足大于等于下界，这个幸运数就可计
        DFS(temp_str + "6");       //从尾部+“6”进行递归
        DFS(temp_str + "8");      //从尾部+“8”进行递归
    }
}

int main()
{
    cin >> a >> b;
    if (a.length() > b.length() || a.compare(b) >= 0)  //输入异常情况
    cout << "-1";
    else
    {
        DFS("6");      //起始为“6”的递归
        DFS("8");      //起始为“8”的递归
        cout << ans;     //最后输出结果
    }
    return 0;
} 

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main()
{
    string n,m;
    cin>>n>>m;
    int o=n.size(),o2=m.size();
    int s=0,u=pow(2,o+1);
    for (int i=o+1;i<o2;i++)
    {
        s+=u;
        u*=2;
    }
    u=1;
    for (int i=0;i<o;i++)
    {
    	if (n[i]<'6')
    	{
    		u=pow(2,o-i);
    		break;
		}
		if (n[i]>'8')
		{
			u=0;
			break;
		}
	}
	s+=u;
	u=1;
    for (int i=0;i<o;i++)
    {
    	if (m[i]>'8')
    	{
    		u=pow(2,o-i);
    		break;
		}
		if (m[i]<'6')
		{
			u=0;
			break;
		}
	}
	s+=u;
    cout<<s;
    return 0;
}

a, b = list(map(int, input().split()))
if a < 1 or a > 1e+9 or b < a or b > 1e+9: print(-1)
else:
    sa, sb = "", ""
    while a > 0:
        a, c = a // 10, a % 10
        if c == 6 or c == 8: sa += str(int(c == 8))
        else:
            sa = '0' * len(sa) + str(int(c == 7))
            if c == 9: a += 1
    while b > 0:
        b, c = b // 10, b % 10
        if c == 6 or c == 8: sb += str(int(c == 8))
        else:
            sb = '1' * len(sb) + (str(int(c != 7)) if b > 0 else (str(int(c == 9)) if c > 6 else ''))
            if b > 0 and c < 6: b -= 1
    print(int(sb[:: -1], 2) - int(sa[:: -1], 2) + 1 + 2 ** len(sb) - 2 ** len(sa))

/**
 * 算法思想：
 *      幸运数字与定长二级制数对应（6->0, 8->1）
 *      所以求出a，b的长度区间[min, max]
 *          记区间内的数字i 2^i 为对应长度的幸运数字的个数
 *      然后扣除min中小于a的和max中大于b的
 * 运行时间：2ms
 * 占用内存：376k
*/

#include <iostream>

using namespace std;

class Solution {
private:
    int out;

public:
    Solution(const int& a, const int& b);
    ~Solution();
    friend ostream& operator<<(ostream& os, const Solution& s);

    // 求出数字的长度
    static int length(int n);

    // 将数字（二进制）转化为对应的幸运数字（0->6, 1->8）
    static int number2lucky(int n, int length);

    // 长度为length中的额幸运数字小于 n 的有多少个
    static int lessNumber(int n, int length);

    // 长度为length中的额幸运数字小于等于 n 的有多少个
    static int lessEqualNumber(int n, int length);
};

Solution::Solution(const int& a, const int& b)
{
    if (a > b) {
        out = -1;
        return;
    }
    int min = this->length(a);
    int max = this->length(b);
    this->out = 0;
    for(int i = min; i < max; ++i) {
        this->out += long(1 << i);
    }

    // 扣除min中不符合规则的
    this->out -= Solution::lessNumber(a, min);
    this->out += Solution::lessEqualNumber(b, max);
}

Solution::~Solution()
{
}

int Solution::length(int n)
{
    int ret = 0;
    while (n != 0) {
        ret++;
        n /= 10;
    }
    return ret;
}

int Solution::number2lucky(int n, int length) 
{
    int ret = 0;
    for (int i = 0, e = length; i < e; i++) {
        ret *= 10;
        if ((1<<i) & n == 0) {
            ret += 6;
        } else {
            ret += 8;
        }
    }
    
    return ret;
}

int Solution::lessNumber(int n, int length) {
    int ret = 0;
    for(int i = 0, end = ((1 << (length+1)) - 1); i < end; i++) {
        int tmp = Solution::number2lucky(i, length);
        if(tmp < n) {
            ret++;
        } else {
            break;
        }
    }
    return ret;
}
int Solution::lessEqualNumber(int n, int length) {
    int ret = 0;
    for(int i = 0, end = ((1 << (length+1)) - 1); i < end; i++) {
        int tmp = Solution::number2lucky(i, length);
        if(tmp <= n) {
            ret++;
        } else {
            break;
        }
    }
    return ret;
}

ostream& operator<<(ostream& os, const Solution& s)
{
    os << s.out;
    return os;
}

int main(int argc, char* argv[])
{
    int a, b;
    cin >> a >> b;
    Solution s(a, b);

    cout << s << endl;
    return 0;
}

//dfs算法
#include <iostream>

using namespace std;

int result = 0;

void dfs(int x, int a, int b){


    if(x>b){
        return;
    }
    if(x>=a && x<=b){
        result++; //这里不要return
    }

    dfs(10*x+6, a, b);
    dfs(10*x+8, a, b);

    return;
}

int main(){

    int a, b;
    while(cin >> a >> b){

        dfs(0, a, b);

        cout << result << endl;
    }
    return 0;
}

package com.hhdd.offer.wanglong;

import java.util.Scanner;

public class LuckyNum {


    public static boolean isLuckNum(int num) {
        if (num == 0) {
            return false;
        }
        while (num != 0) {
            if ((num % 10) != 6 && (num % 10) != 8) {
                return false;
            }
            num /= 10;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int count = 0;
        for(int i = a;i<=b;i++){
            if(isLuckNum(i)){
                count++;
            }
        }
        System.out.println(count);
    }

}

//复杂度只与b的位数有关系，以b=9977为例，可以先算出1000以内符合要求的个数，
//对于[1001,9977]的个数，可以遍历9977的每一位如果在<6范围，K * = 0，
//如果在([6,8) K *=1,如果在 [8, )范围K*=2。

 int getKind(int num){
    string str = to_string(num);
    int d = str.size() - 1;
    
    int ans = 0;
    for(int i=1;i<=d;++i){
        ans += (1<<i);
    }
    
    int k = 1;
    for(int i=0;i<str.size();++i){
        if(str[i] - '0' <6){
            k *= 0;
        }else if (str[i] - '0'>=6&&str[i] - '0'<8){
            k *= 1;
        }else if (str[i] - '0' >=8){
            k *= 2;
        }
    }
    ans += k;
    return ans;
}

import java.util.*;

public class Main{
static void f(int n,int cnt,char[] s,ArrayList ss){
if(cnt==n){
s[cnt]='\0';
ss.add(new String(s));
return ;
}else{
s[cnt]='6';
f(n,cnt+1,s,ss);
s[cnt]='8';
f(n,cnt+1,s,ss);
}
}
public static void main(String[] args){
ArrayList ss=new ArrayList();
for(int i=1;i<=9;i++){
char[] s=new char[i+1];
f(i,0,s,ss);
}
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int count=0;
for(int i=0;i<ss.size();i++){
int xx=Integer.parseInt(ss.get(i).trim());
if(xx>=n&&xx<=m) count++;
}
System.out.println(count);
input.close();
}
}

先用递归把所有的结果储存起来，然后再根据输入的时候查找基数

//回答提交的代码格式总是出问题...难道是个bug?
import java.util.*;
public class Main{
 public static int help(Long l){  int len = l.toString().length();  int res = (int) (Math.pow(2, len)-2);  for (int i = 0; i < l.toString().length(); i++) {  int t = l.toString().charAt(i) - '0';  len--;  if (t > 8)  return res+(int)(Math.pow(2, len+1));  else if (t < 6)  return res;  else if (t == 8)  res=+(int) Math.pow(2, len);  else if (t == 6)   continue;  else return res+(int)Math.pow(2, len);  }  return res;
   }
    public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    Long a=sc.nextLong();
    Long b=sc.nextLong();
    System.out.print(help(b)-help(a));
    }
}