Java工程师丨面试真题（6）
【摘要】 一、生成格雷码描述在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。给定一个整数n，请返回n位的格雷码，顺序为从0开始。测试样例：1返回：["0","1"]题解：import java.util.*;public class GrayCode { public String[] ...
一、生成格雷码
描述
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
测试样例：
1返回：["0","1"]
题解：
import java.util.*;
public class GrayCode {
public String[] getGray(int n) {
// write code here
String[] ans = new String[(int) Math.pow(2, n)];
ans[0] = "0";
ans[1] = "1";
int len = 2, len2 = len << 1;
for(int i = 1; i < n; i++) {
for(int j = len; j < len2; j++) {
ans[j] = "1" + ans[len - 1 - j + len];
}
for(int j = 0; j < len; j++) {
ans[j] = "0" + ans[j];
}
len = len2;
len2 = len << 1;
}
return ans;
}
}
二、微信红包
描述
春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
数据范围： 1≤n≤1000 1 \le n \le 1000 \ 1≤n≤1000 ,红包金额满足 1≤gifti≤100000 1 \le gift_i \le 100000\ 1≤gifti≤100000
示例1
输入：
[1,2,3,2,2],5返回值：
2示例2
输入：
[1,1,2,2,3,3],6返回值：
0
题解：
import java.util.*;
public class Gift {
public int getValue(int[] gifts, int n) {
Map<Integer, Integer> m = new HashMap<>();
for(int i = 0; i < gifts.length; ++i){
if(m.containsKey(gifts[i])){
m.put(gifts[i], m.get(gifts[i]) + 1);
}else{
m.put(gifts[i], 1);
}
if(m.get(gifts[i]) > gifts.length/2){ //超过一半就返回
return gifts[i];
}
}
return 0;
}
}三、编码
描述
假定一种编码的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index为0，aa的Index为1，aaa的Index为2，以此类推。 编写一个函数，输入是任意一个编码，输出这个编码对应的Index.
输入描述：
输入一个待编码的字符串,字符串长度小于等于100.
输出描述：
输出这个编码的index
示例1
输入：
baca输出：
16331
题解：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Comparator;
class CodeComparator implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
return s1.compareTo(s2);
}
}
public class Main {
private static ArrayList<String> list = new ArrayList<>();
private static String[] strArr = new String[]{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y"};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println(getPos(in.nextLine()));
}
//装值
public static void setVal(){
//1个
ArrayList<String> list0 = new ArrayList<>();
for(int i=0; i<strArr.length; i++){
list0.add(strArr[i]);
list.add(strArr[i]);
}
//2个
for(int i=0; i<list0.size(); i++){
for(int i1=0; i1<list0.size(); i1++){
list.add(list0.get(i)+list0.get(i1));
}
}
//3个
for(int i=0; i<list0.size(); i++){
for(int i1=0; i1<list0.size(); i1++){
for(int i2=0; i2<list0.size(); i2++){
list.add(list0.get(i)+list0.get(i1)+list0.get(i2));
}
}
}
//4个
for(int i=0; i<list0.size(); i++){
for(int i1=0; i1<list0.size(); i1++){
for(int i2=0; i2<list0.size(); i2++){
for(int i3=0; i3<list0.size(); i3++){
list.add(list0.get(i)+list0.get(i1)+list0.get(i2)+list0.get(i3));
}
}
}
}
}
//排序
public static void sort(){
setVal();
Collections.sort(list, new CodeComparator());
}
//获取字符串位置
public static int getPos(String str){
sort();
return list.indexOf(str);
}
}
四、游戏任务标记
描述
游戏里面有很多各式各样的任务，其中有一种任务玩家只能做一次，这类任务一共有1024个，任务ID范围[1,1024]。请用32个unsigned int类型来记录着1024个任务是否已经完成。初始状态都是未完成。 输入两个参数，都是任务ID，需要设置第一个ID的任务为已经完成；并检查第二个ID的任务是否已经完成。 输出一个参数，如果第二个ID的任务已经完成输出1，如果未完成输出0。如果第一或第二个ID不在[1,1024]范围，则输出-1。
输入描述：
输入包括一行,两个整数表示任务ID.
输出描述：
输出是否完成
示例1
输入：
1024 1024输出：
1
题解：
import java.util.Scanner;
/**
* 用32个int记录1024个任务状态,任务ID为1~1024,任务初始状态都是未完成
* 函数功能：输入两个任务ID,将第一个任务设为已完成,并检测第二个任务是否已完成(完成返回1,未完成返回0)
*
* 32个int,每个int32位,共32*32=1024位,刚好每一位表示一个任务的状态
*/
public class T4GameTaskTag {
public static void main(String[] args) {
//tasks[0]:1~32号任务 tasks[1]:33~64号任务
int[] tasks = new int[32];
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) { // 注意 while 处理多个 case
int id1 = in.nextInt();
int id2 = in.nextInt();
System.out.println(setAndCheck(tasks, id1, id2));
}
}
public static int setAndCheck(int[] tasks, int id1, int id2) {
if (!checkInParams(id1, id2)) {
return -1;
}
//任务在tasks[n] 0~31
int n = (id1 - 1) / 32;
//设置id1的任务为已完成
int bit = (id1 - 1) % 32;
tasks[n] = tasks[n] | (1 << bit);
//检查id2的任务是否已完成
int n2 = (id2 - 1) / 32;
int bit2 = (id2 - 1) % 32;
//使用无符号右移:由于java没有无符号数
return (tasks[n2] & (1 << bit2)) >>> bit2;
}
private static boolean checkInParams(int id1, int id2) {
boolean b1 = id1 >= 1 && id1 <= 1024;
boolean b2 = id2 >= 1 && id2 <= 1024;
return b1 && b2;
}
}
五、素数对
描述
给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）
输入描述：
输入包括一个整数n,(3 ≤ n < 1000)
输出描述：
输出对数
示例1
输入：
10输出：
2
题解：
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Integer> v = new ArrayList<>();
for(int i = 2; i < n; ++i) if(f(i)) v.add(i);//先求出1~n之间的所有素数
int r = 0;
boolean[] visit = new boolean[v.size()];//标记该素数是否已访问
for(int i = 0; i < v.size(); ++i){
if(!visit[i] && v.contains(n - v.get(i))){//做差，另一个也是质数
r++;
visit[i] = true;
visit[v.indexOf(n - v.get(i))] = true;//把这俩都标记已访问
}
}
System.out.println(r);
}
static boolean f(int n){//求素数的函数，可以用欧拉筛法加速
if(n <= 1) return false;
if(n == 2) return true;
for(int i = 2; i < n; ++i){
if(n%i == 0) return false;
}
return true;
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）