小雅同学认为6,8是她的幸运数字,而其他数字均不是,一个幸运数是指在十进制表示下只含有幸运数字的数。给定你一个区间(a,b)a和b之间(其中包括a和b幸)运数的个数。
小雅同学认为6,8是她的幸运数字,而其他数字均不是,一个幸运数是指在十进制表示下只含有幸运数字的数。给定你一个区间(a,b)a和b之间(其中包括a和b幸)运数的个数。
输入两个整数a和b,a的取值范围在1和1000000000之间(其中包括1和1000000000),b的取值范围在a和1000000000之间(其中包括a和1000000000)。
返回a和b之间的幸运数个数,如果入参不合法,请输出-1
1 10
2
6,8,6666,88888,6668888,68686688均为幸运数字,当a=1,b=10函数返回值为2。
//用字符串超时超内存,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; }
#include<iostream> using namespace std; bool judge(int n){ while(n>0){ int temp=n%10; if(n%10!=8&&n%10!=6) return 0; n/=10; } return 1; } int main(){ int a,b;//1-1000000000都还是属于2^31-1的范围内,所以用整数就OK cin>>a>>b; if(!((a<=1000000000&&a>=1)&&(b<=1000000000&&b>=1))) cout<<-1; else{ int count=0; for(int i=a;i<=b;i++){ if(judge(i)) count++; } cout<<count<<endl; } }
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; }由于长度比左边界大又比右边界小大所有幸运数字都可以,然后我们只需要计算与左右边界一样长的个数,2个相加,应用数学方法解题
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)); } }