关于京东笔试幸运数字

首先关于f(x)函数和g(x)函数，我是这样写的，效率肯定不高，但是反正能用

        // 定义f(x)函数
	public static int f(int x) {
		int sum = 0;
		int temp = x;
		while (temp != 0) {
			sum += temp % 10;
			temp /= 10;
		}
		return sum;
	}

	//定义g(x)函数
	public static int g(int x) {
		int sum = 0;
		int temp = x;
		while (temp != 0) {
			sum += temp % 2;
			temp /= 2;
		}
		return sum;
	}

然后我取了巧，题目中说明了，数组的组数T<10000，每组数n<100000

然后我之前每次提交的时候都是说我时间超限~~~估计这编译器要求要快吧。所以其实需要把幸运数字记录下来。

int[] record = new int[1000001];
//直接计算1到100000
luckyNumberCountBetweenXAndY(1,100000);
//从x到y之间的luckyNumber数量
public static void luckyNumberCountBetweenXAndY(int x,int y){
	for(int j=x;j<=y;j++){
		if(f(j)==g(j)){
			record[j] = true;
		}else{
			record[j] = false;
		}
	}
}

简单说就是直接计算1-100000的幸运数字，记录哪些是幸运数字，然后算的时候直接根据布尔数组统计就可以了，这样速度应该会快很多。

可惜我想到这个方法的时候还有几分钟的了~~~~

最后编译的结果是说我的结果错了（糟心的OJ，就只知道结果错误，不给具体的结果，真的不知道哪里错了啊~~~）

全部评论

推荐最新楼层

Jing0

郑州大学 Java

AC代码 import java.util.*; public class Main { static int f(int n) { int sum = 0; while (n != 0) { sum += n % 10; n /= 10; } return sum; } static int g(int n) { int sum = 0; while (n != 0) { sum += n & 1; n >>= 1; } return sum; } public static void main(String args[]) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); int max = 1; int[] buf = new int[1000020]; buf[1] = 1; for (int i = 0; i < t; ++i) { int n = sc.nextInt(); if (n <= max) { System.out.println(buf[n]); } else { for (; max <= n; ++max) { buf[max + 1] = buf[max]; if (g(max + 1) == f(max + 1)) { buf[max + 1]++; } } --max; System.out.println(buf[n]); } } } }

点赞回复分享

发布于 2016-09-06 01:26

Afly

阿里巴巴_杭州研究院_1688 AI工程负责人

import java.util.Map.Entry; import java.util.Scanner; import java.util.TreeMap; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); TreeMap<Integer,Integer> *** = new TreeMap<Integer,Integer>(); ***.put(1, 1); while(scan.hasNext()){ int t = scan.nextInt(); for(int i=0;i<t;i++){ int n = scan.nextInt(); Entry<Integer,Integer> last = ***.floorEntry(n); if(n==last.getKey()){ System.out.println(last.getValue()); continue; }else{ int count = last.getValue(); for(int x=last.getKey()+1;x<=n;x++){ if(f(x)==g(x)) count++; } ***.put(n, count); System.out.println(count); } } } scan.close(); } private final static int f(int x){ String str = String.valueOf(x); int sum = 0; for(int i=0;i<str.length();i++){ sum+=str.charAt(i)-'0'; } return sum; } private final static int g(int x){ int sum = 0; int flag = 1; while(x!=0){ sum += (x&flag); x>>=1; } return sum; } }

点赞回复分享

发布于 2016-09-05 23:36

Afly

阿里巴巴_杭州研究院_1688 AI工程负责人

用一个TreeMap记录之前的中间结果，每次计算前，找到离n最近的小于n的中间结果（floorEntry方法），记为last。每次只要计算n-last个数就好了。

点赞回复分享

发布于 2016-09-05 21:25