去哪儿网0907后端笔试
1、简单背包问题，动态规划
// dp[i][j]
// 1. actions[i][0] <= j: dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - actions[i][0]] + actions[i][1]);
// 2. else: dp[i][j] = dp[i - 1][j]
public int maxScore(int energy, int[][] actions) {
// write code here
int n = actions.length, dp[][] = new int[n + 1][energy + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= energy; j++) {
if (actions[i][0] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - actions[i][0]] + actions[i][1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][energy];
} 2、rsa非对称解码，乘积过程中进行模运算，此处循环相乘，也可使用快速幂
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* <p>
* 解密
*
* @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
p = number;
return pow(encryptedNumber, decryption);
}
int p;
public int pow(int x, int n) {
int ans = 0;
for (int i = 1; i <= n; i++) {
ans *= x;
ans %= p;
}
return ans;
} 3、德州扑克，模拟每种情况、不符合其他情况就是高牌，高牌输出仿照其他输出拼音即可 /**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* <p>
* 翻牌
*
* @param inHand string字符串 一组以单空格间隔的手牌(例如：SA HK H9 D8 C5 S5 H4)
* @return string字符串
*/
public String showDown(String inHand) {
// write code here
String ans;
String cs[] = inHand.split(" ");
if (cs.length < 5) {
return "GaoPai";
}
if (huangjiatonhuashun(cs)) {
ans = "HuangJiaTongHuaShun";
} else if (tonhuashun(cs)) {
ans = "TongHuaShun";
} else if (sitiaoa(cs)) {
ans = "SiTiao";
} else if (hulu(cs)) {
ans = "HuLu";
} else if (tonhua(cs)) {
ans = "TongHua";
} else if (shunzi(cs)) {
ans = "ShunZi";
} else if (santiao(cs)) {
ans = "SanTiao";
} else if (liangdui(cs)) {
ans = "LiangDui";
} else if (yidui(cs)) {
ans = "YiDui";
} else {
ans = "GaoPai";
}
return ans;
}
// 统计最多花色出现的次数和花色
// ans[0]为花色， ans[1]为次数
public String[] cntHua(String cs[]) {
Map<String, Integer> map = new HashMap<>();
String[] ans = new String[2];
int maxC = 0, v;
for (String c : cs) {
c = c.substring(0, 1);
map.put(c, map.getOrDefault(c, 0) + 1);
v = map.get(c);
if (v > maxC) {
maxC = v;
ans[0] = c;
ans[1] = v + "";
}
}
return ans;
}
// 统计数字出现的最多次数，和对应数字
// ans[0]为对应次数，ans[1]为对应数字字符
public String[] cntNum(String cs[]) {
Map<String, Integer> map = new HashMap<>();
int maxCnt = 0, cnt;
String[] ans = new String[2];
for (String num : cs) {
num = num.substring(1);
map.put(num, map.getOrDefault(num, 0) + 1);
cnt = map.get(num);
if (cnt > maxCnt) {
maxCnt = cnt;
ans[0] = maxCnt + "";
ans[1] = num;
}
}
return ans;
}
public void reverse(int nums[]) {
int i = 0, j = nums.length - 1;
while (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
// 判断是否存在顺子,并返回顺子最大值， 返回null为无顺子
public Integer isShunZi(String cs[]) {
// 1. a为14
int n = cs.length, nums[] = new int[n];
String c;
for (int i = 0; i < n; i++) {
c = cs[i].substring(1);
if (c.equals("A")) {
nums[i] = 14;
} else if (c.equals("K")) {
nums[i] = 13;
} else if (c.equals("Q")) {
nums[i] = 12;
} else if (c.equals("J")) {
nums[i] = 11;
} else {
nums[i] = Integer.parseInt(c);
}
}
Arrays.sort(nums);
reverse(nums);
//1.1 判断是否存在顺子
for (int i = 0; n - i >= 5; i++) {
int j;
for (j = i + 1; j < n; j++) {
if (nums[j] + 1 != nums[j - 1]) {
break;
}
if (j - i == 4) {
return nums[i];
}
}
}
// 2. a为1;
for (int i = 0; i < n; i++) {
c = cs[i].substring(1);
if (c.equals("A")) {
nums[i] = 1;
} else if (c.equals("K")) {
nums[i] = 13;
} else if (c.equals("Q")) {
nums[i] = 12;
} else if (c.equals("J")) {
nums[i] = 11;
} else {
nums[i] = Integer.parseInt(c);
}
}
Arrays.sort(nums);
reverse(nums);
//1.1 判断是否存在顺子
for (int i = 0; n - i >= 5; i++) {
int j;
for (j = i + 1; j < n; j++) {
if (nums[j] + 1 != nums[j - 1]) {
break;
}
if (j - i == 4) {
return nums[i];
}
}
}
return null;
}
public boolean huangjiatonhuashun(String cs[]) {
String[] cnt = cntHua(cs);
if (Integer.parseInt(cnt[1]) < 5) {
return false;
}
// 获取所有最大次数花色
List<String> list = new ArrayList<>();
for (int i = 0; i < cs.length; i++) {
if (cs[i].substring(0, 1).equals(cnt[0])) {
list.add(cs[i]);
}
}
String[] arr = list.toArray(new String[0]);
Integer shunZi = isShunZi(arr);
return shunZi != null && shunZi == 14;
}
public boolean tonhuashun(String cs[]) {
String[] cnt = cntHua(cs);
if (Integer.parseInt(cnt[1]) < 5) {
return false;
}
// 获取所有最大次数花色
List<String> list = new ArrayList<>();
for (int i = 0; i < cs.length; i++) {
if (cs[i].substring(0, 1).equals(cnt[0])) {
list.add(cs[i]);
}
}
String[] arr = list.toArray(new String[0]);
Integer shunZi = isShunZi(arr);
return shunZi != null;
}
public boolean sitiaoa(String cs[]) {
String[] strings = cntNum(cs);
return Integer.parseInt(strings[0]) >= 4;
}
public boolean hulu(String cs[]) {
String[] ans = cntNum(cs);
if (Integer.parseInt(ans[0]) != 3) {
return false;
}
// 获取对应三次的数字字符串
String rmNum = ans[1];
List<String> list = new ArrayList<>();
for (String c : cs) {
if (!c.substring(1).equals(rmNum)) {
list.add(c);
}
}
ans = cntNum(list.toArray(new String[0]));
return Integer.parseInt(ans[0]) >= 2;
}
public boolean tonhua(String cs[]) {
String[] cntHua = cntHua(cs);
return Integer.parseInt(cntHua[1]) >= 5;
}
public boolean shunzi(String cs[]) {
Integer shunZi = isShunZi(cs);
return shunZi != null;
}
public boolean santiao(String cs[]) {
String[] ans = cntNum(cs);
return Integer.parseInt(ans[0]) == 3;
}
public boolean liangdui(String cs[]) {
String[] ans = cntNum(cs);
if (Integer.parseInt(ans[0]) != 2) {
return false;
}
// 获取对应两次的数字字符串
String rmNum = ans[1];
List<String> list = new ArrayList<>();
for (String c : cs) {
if (!c.substring(1).equals(rmNum)) {
list.add(c);
}
}
ans = cntNum(list.toArray(new String[0]));
return Integer.parseInt(ans[0]) == 2;
}
public boolean yidui(String cs[]) {
String[] ans = cntNum(cs);
return Integer.parseInt(ans[0]) == 2;
}
类似资料：