京东幸运数。超时，求解更好算法。

这是笔试时自己写的代码： import java.util.Scanner; publicclass Main { public static void findLuckNum(int location){ //找出location打印的是几位数 int temp=location+2; int yushu=0; int jiweishu=0; for(int i=1;i<100;i++){ if(temp-Math.pow(2, i)==0){ yushu=0; jiweishu=i; break; } if(temp>Math.pow(2, i)&&temp<Math.pow(2, i+1)){ yushu=(int) (temp-Math.pow(2, i)); jiweishu=i; break; } } if(yushu==0){ for(int k=1;k<jiweishu;k++){ System.out.print("7"); } } if(yushu!=0){ //这个数为第jiweishu层的第yushu数 int record=jiweishu-1; int tem=yushu; for(int k=record;k>=0;k--){ tem=(int)(tem-Math.pow(2,k)); if(tem>0){ System.out.print("7"); }else{   tem=(int)(tem+Math.pow(2,k));   System.out.print("4"); } } } System.out.println(); } public static void main(String[] args) { Scanner input=new Scanner(System.in); while(input.hasNext()){ int n=input.nextInt(); int[] tem=new int[n]; for(int i=0;i<n;i++){ tem[i]=input.nextInt(); } for(int j=0;j<n;j++){ Main.findLuckNum(tem[j]); } } } } //下面这种是考完写的简单代码 import java.util.Scanner; publicclass Main { public static void findLuckNum(int location){ int n=location+1; String s=Integer.toBinaryString(n); for(int i=1;i<s.length();i++){ if(s.charAt(i)=='0'){ System.out.print(4); }else{ System.out.print(7); } } System.out.println(); } public static void main(String[] args) { Scanner input=new Scanner(System.in); while(input.hasNext()){ int n=input.nextInt(); int[] tem=new int[n]; for(int i=0;i<n;i++){ tem[i]=input.nextInt(); } for(int j=0;j<n;j++){ Main.findLuckNum(tem[j]); } } } }

保存中间结果，不要重复计算，ac

这一题我是用的队列的思想，我觉得不管最后结果怎么样，只要有这种思想的就可以算过，有用一样的队列思想的么

楼主是怎么知道超时的，反正我是本地全部通过，然后提交，就是0%

package ojtest; import java.util.Scanner; public class Jd2 { int[] dp=new int[100001]; int index=1; public int f(int n){ int sum=0; while(n!=0){ sum+=n%10; n=n/10; } return sum; } public int g(int n){ int sum=0; while(n!=0){ sum+=n&1; n>>>=1; } return sum; } public int countNumber(int n){ if(index>n) return dp[n]; for(;index<=n;index++) { dp[index]=dp[index-1]; if(f(index)==g(index)){ dp[index]++; } } return dp[n]; } public static void main(String[] args) { Jd2 test=new Jd2(); Scanner input=new Scanner(System.in); int N=input.nextInt(),n; for(int i=1;i<=N;i++){ n=input.nextInt(); System.out.println(test.countNumber(n)); } } }

看来大家都是同样的问题。本地通过，上面为0%。我就放心了。

幸运数代码本地例子都过了，自己的测试用例也过了，提交AC 0%。 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int count=0; for(int i=1; i<=n; i++){ int f =0; \\十进制位数和 int g = 0; \\二进位数和 int temp=i; int temp1=i; if (temp<10) f+=temp; while(temp/10>0){ f+=temp%10; temp=temp/10; } f+=temp; while(0!=temp1){ g++; temp1=temp1&(temp1-1); } if(g==f){ count++; } } System.out.println(count); } } }

#include <cstdio> #include <cstring> #include <iostream> using namespace std; int t, n, m; int dp[100006]; int main() {     dp[1] = 1;     for(int i = 2; i <= 100000; i++) {         int x = 0, y = 0;         n = i;         while(n) {             x += n%10;             n /= 10;         }         n = i;         while(n) {             y += n%2;             n /= 2;         }         if(x == y) {             dp[i] = dp[i-1]+1;         }         else {             dp[i] = dp[i-1];         }     }     scanf("%d", &t);     while(t--) {         scanf("%d", &n);         printf("%d\n", dp[n]);     }     return 0; }

谁还有题目截图吗？输入范围是多少啊

我的ac代码 http://www.nowcoder.com/discuss/8552?toCommentId=208679

我突然想，会不会用 位运算 能好一点

直接先求出1~1000000中的幸运数的个数，并保存在数组中，之后就不用再求了。

同之前楼上说的，中间结果保存起来，不要重复计算

你们的幸运数题目是9楼那个题目吗？

做法是对的，暴力离线操作存答案，因为它的T比较大，在线O1查询

#include <iostream> using namespace std; int f[] = {1,20,21,122,123,202,203,222,223,230,231,302,303,410,411,502,503,1130,1131,1150,1151,1202,1203,1212,1213,1230,1231,1300,1301,1402,1403,1502,1503,1510,1511,2006,2007,2032,2033,2102,2103,2200,2201,3006,3007,3012,3013,3050,3051,3070,3071,3102,3103,3110,3111,3300,3301,4014,4015,5000,5001,5010,5011,5020,5021,6002,6003,6012,6013,6102,6103,7000,7001,7102,7103,8110,8111,10006,10007,10032,10033,10050,10051,10060,10061,10070,10071,10112,10113,10132,10133,10170,10171,10234,10235,10310,10311,10410,10411,10430,10431,11012,11013,11050,11051,11070,11071,11114,11115,11134,11135,11150,11151,11214,11215,11240,11241,11250,11251,11260,11261,11300,11301,11502,11503,11710,11711,12006,12007,12024,12025,12112,12113,12142,12143,12204,12205,12214,12215,12250,12251,13012,13013,13050,13051,13200,13201,13230,13231,14014,14015,14020,14021,14102,14103,14330,14331,15002,15003,15010,15011,15020,15021,15030,15031,15210,15211,15230,15231,15310,15311,16010,16011,16030,16031,16102,16103,16120,16121,16300,16301,16310,16311,20004,20005,20040,20041,20050,20051,20060,20061,20112,20113,20142,20143,20206,20207,20230,20231,20312,20313,20320,20321,20340,20341,20414,20415,20420,20421,21002,21003,21022,21023,21030,21031,21112,21113,21202,21203,21212,21213,21220,21221,21302,21303,21400,21401,22006,22007,22030,22031,22120,22121,22130,22131,22140,22141,22210,22211,22220,22221,22230,22231,22302,22303,22310,22311,22500,22501,23004,23005,23012,23013,23110,23111,23210,23211,23230,23231,24002,24003,24012,24013,24022,24023,24100,24101,24302,24303,24510,24511,26100,26101,30006,30007,30042,30043,30050,30051,30060,30061,30070,30071,30104,30105,30112,30113,30132,30133,30150,30151,30210,30211,30220,30221,30230,30231,30320,30321,30400,30401,30420,30421,30500,30501,30702,30703,31004,31005,31012,31013,31120,31121,31150,31151,31214,31215,31300,31301,31400,31401,31410,31411,31420,31421,31610,31611,31710,31711,32002,32003,32012,32013,32022,32023,32112,32113,32212,32213,32250,32251,32302,32303,32410,32411,32502,32503,32700,32701,40002,40003,40012,40013,40022,40023,40122,40123,40200,40201,40210,40211,40220,40221,40400,40401,40430,40431,40510,40511,40700,40701,41210,41211,42100,42101,43004,43005,44000,44001,44020,44021,45000,45001,45010,45011,45020,45021,47100,47101,50002,50003,50012,50013,50020,50021,50300,50301,51010,51011,51020,51021,51030,51031,51130,51131,52010,52011,52030,52031,52110,52111,52200,52201,52210,52211,52220,52221,53102,53103,53210,53211,54010,54011,60002,60003,60012,60013,60022,60023,60102,60103,60120,60121,60200,60201,60210,60211,60220,60221,60300,60301,60310,60311,60400}; bool solve(int n) {     int t = n;     int result1 = 0;     int result2 = 0;     while(t) {         t = t & (t - 1);         result1++;     }     while(n) {         result2 += (n % 10);         n /= 10;     }     if(result1 == result2) {         return true;     } else {         return false;     } } int main() {     int T;     int n;     cin>>T;     for(int k = 0; k < T; k++) {         cin>>n;         int result = 0;         for(int i = 0; i < 483; i++) {             if(f[i] <= n) {                 result++;             } else {                 break;             }         }         cout<<result<<endl;     }     return 0; } AC率为0。。。

import java.util.ArrayList; import java.util.List; import java.util.Scanner; /**  * Created by robin on 16/9/5.  */ public class Maind {     public static void main(String[] args){         Scanner scanner=new Scanner(System.in);         int cnt=scanner.nextInt();         List<String> list=new ArrayList<String>();         for(int i=0;i<cnt;i++){             int num=scanner.nextInt()+1;             String str=Integer.toBinaryString(num);             StringBuffer sb=new StringBuffer();             for(int j=1;j<str.length();j++){                 if(str.charAt(j)=='1')                     sb.append(7);                 else                     sb.append(4);             }             list.add(sb.toString());         }         for(String s:list){             System.out.println(s);         }     } }

你们的幸运数题目不一样吗？

怎么知道是超时的？