9.7 去哪网后端Java笔试
1.舞蹈选动作----01背包
public class Main1 {
public int maxScore(int energy, int[][] actions) {
// write code here action[0]体力 action【1】分数
int[] dp = new int[energy + 1];//dp[i]表示体力为i的最大得分
for (int[] action : actions) {
for (int i = energy; i >= action[0]; i--) {
if (i - action[0] >= 0) {
dp[i] = Math.max(dp[i], dp[i - action[0]] + action[1]);
}
}
}
return dp[energy];
}
} 2.解密----分治（a*b）%c =(a%c *b%c)%c 推导 令 a=n1*c+m1 ,b=n2*c+m2 ,(a*b)%c=(n1*n2*c^2+(n1m2+n2m1)*c+m1*m2)/c 取余数，显然多项式前两项可以整除，所以只剩下m1*m2,防止超过c，再去一次模，即(m1*m2)%c;
public class Main2 {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 解密
* @param encryptedNumber int整型 待解密数字
* @param decryption int整型 私钥参数D
* @param number int整型 私钥参数N
* @return int整型
*/
public int Decrypt (int encryptedNumber, int decryption, int number) {
// write code here
if(decryption==2||decryption==1) return ((int)Math.pow(encryptedNumber,decryption))%number;
return (Decrypt(encryptedNumber, decryption/2, number)*Decrypt(encryptedNumber, decryption-decryption/2, number))%number;
}
} 3.打牌 89% package quna_code;
import java.util.HashMap;
import java.util.HashSet;
public class Main3 {
public String showDown (String inHand) {
// write code here
String[] strings = inHand.split(" ");
int[][] pokes = new int[15][4];
int[] counts = new int[15];
int[] colors = new int[4];
HashMap<Integer, HashSet<Character>> map = new HashMap<>();
for (String string : strings) {
int order = getOrder(string.substring(1));
int color = getColor(string.charAt(0));
pokes[order][color]=1;
counts[order]++;
colors[color]++;
HashSet<Character> set = map.getOrDefault(order, new HashSet<>());
set.add(string.charAt(0));
map.put(order,set);
if(order==1){
pokes[14][color]=1;
counts[14]++;
HashSet<Character> set2 = map.getOrDefault(14, new HashSet<>());
set2.add(string.charAt(0));
map.put(14,set2);
}
}
int end = isShun(counts);
int colorCount=0;
for (int color : colors) {
colorCount= Math.max(colorCount,color);
}
int maxCount=0;
int count2=0;
for (int count : counts) {
maxCount= Math.max(maxCount,count);
if(count==2) count2++;
}
if( end>0){
if(isTonghua(pokes,end,map)){
if(end==14){
return "HuangJiaTongHuaShun";
}
return "TongHuaShun";
}
if(maxCount==4){
return "SiTiao";
} else if (maxCount==3&&count2==1) {
return "HuLu";
} else if (maxCount==3) {
return "SanTiao";
}
if(colorCount==5){
return "TongHua";
}
return "ShunZi";
}
if(colorCount==5){
return "TongHua";
}
if(maxCount==4){
return "SiTiao";
} else if (maxCount==3&&count2==1) {
return "HuLu";
}else if (maxCount==3) {
return "SanTiao";
}
if(count2==2){
return "LiangDui";
} else if (count2==1) {
return "YiDui";
}
return "GaoPai";
}
int isShun(int[] counts){
int count=0;
int end=0;
for (int i = counts.length-1; i >=0 ; i--) {
if(counts[i]>0){
if(count==0){
end=i;
}
count++;
if(count==5) return end;
}
if(counts[i]==0){
count=0;
}
}
return -1;
}
boolean isTonghua(int[][] pokes,int end,HashMap<Integer,HashSet<Character>> map){
boolean flag1=true;
boolean flag2=true;
boolean flag3=true;
boolean flag4=true;
char a='S';
char b='H';
char c='C';
char d='D';
for (int i = end-4; i <=end ; i++) {
if(!map.get(i).contains(a)){
flag1=false;
break;
}
}
for (int i = end-4; i <=end ; i++) {
if(!map.get(i).contains(b)){
flag2=false;
break;
}
}
for (int i = end-4; i <=end ; i++) {
if(!map.get(i).contains(c)){
flag3=false;
break;
}
}
for (int i = end-4; i <=end ; i++) {
if(!map.get(i).contains(d)){
flag4=false;
break;
}
}
return flag1||flag2||flag3||flag4;
}
int getColor(char a){
switch (a){
case 'S':
return 0;
case 'H':
return 1;
case 'C':
return 2;
case 'D':
return 3;
}
return 0;
}
int getOrder(String b){
if(b.length()==1){
char a=b.charAt(0);
if(Character.isDigit(a)) return a-'0';
switch (a){
case 'A':
return 1;
case 'J':
return 11;
case 'Q':
return 12;
case 'K':
return 13;
}
}
return 10;
}
}
华为二面45人在聊