2023.8.26京东笔试
题目三：
给出题目总数 n 和总时间 t，每道题目有三个选择
放弃 F：花 0 时间，0 得分
最优解法 A：花 t1 时间，得 s1 分
暴力解决 B：花 t2 时间，得 s2 分
要求：在给定时间内做这些题目，如何得最高分？输出得最高分的情况下，对于每道题选择的策略
比如：三道题，发现放弃第一道、暴力解第二道、最优解第三道的策略得分最高，则返回 FBA
思路：动态规划
二维 dp[t + 1][n + 1]，第一维表示给的做题时间，第二维是题目，组合起来的 (i, j) 点表示：给 i 时间时，做 j 道题的最大得分
j = 1 时：最大得分就是，看时间 j 落在哪个范围，放弃or暴力or最优解法的得分
j > 1 时：分别计算对本道题的三种解法的得分，放弃时，得分等于上一道题（即 j - 1 题）在给时间 i 的得分，即 temp1 = dp[i][j - 1]；暴力解法时，此时要满足当前给的时间大于暴力解法的时间，即 i > t2，得分为 上一题减去本题暴力解法时间的得分 加上 本题暴力解法的得分，即 temp2 = dp[i - t2][j - 1] + s2；最优解法时，时间也要满足，即 i > t1，得分为 上一题减去本题最优解法时间的得分 加上 本题最优解法的得分，即 temp3 = dp[i - t1][j - 1]
三种解法的最大值赋值做状态转移，即 dp[i][j] = Math.max(Math.max(temp1, temp2), temp3)
注：正常求最大得分时只需要用两个 Math.max 取出并赋值最大值即可，但此处要记录每道题的操作，因此需要分开判断
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int t = in.nextInt();
int[][] dp = new int[t + 1][n + 1];
String[][] res = new String[t + 1][n + 1];
for (int i = 1; i <= n; ++ i) {
int t1 = in.nextInt();
int s1 = in.nextInt();
int t2 = in.nextInt();
int s2 = in.nextInt();
for (int j = 1; j <= t; ++ j) {
int temp1 = dp[j][i - 1]; // 放弃情况，i时间得分
int temp2 = -2;
int temp3 = -3;
if (j >= t2) temp2 = s2 + dp[j - t2][i - 1]; // 暴力解法，i时间得分
if (j >= t1) temp3 = s1 + dp[j - t1][i - 1]; // 正确解法，i时间得分
if (temp1 > temp2 && temp1 > temp3) { // 放弃最优
dp[j][i] = temp1;
res[j][i] = res[j][i - 1] == null ? "F" : res[j][i - 1] + "F";
}
if (temp2 >= temp1 && temp2 > temp3) { // 暴力最优
dp[j][i] = temp2;
res[j][i] = res[j - t2][i - 1] == null ? "B" : res[j - t2][i - 1] + "B";
}
if (temp3 >= temp1 && temp3 >= temp2) { // 正确最优
dp[j][i] = temp3;
res[j][i] = res[j - t1][i - 1] == null ? "A" : res[j - t1][i - 1] + "A";
}
}
}
System.out.println(res[t][n]);
}
}
题目二：
给出角色数 n 以及回合数 k
其中角色有两种：master 怪兽和 human 人类，会给出 1 - n 哪个编号是怪兽，哪个编号是人类，以及对应的攻击力 k
当发生攻击时（不管是 a 进攻 b 还是 b 进攻 a），攻击力高的一方会击杀攻击力低的一方，若攻击力相同则同归于尽。
每个回合给出相遇的两个角色编号，并分别给出他们会不会向对方透露身份：Y 会，N 不会，有以下几种情况：
若怪兽知道对方是人类，那么一定会攻击他；若人类知道对方是怪兽，那么会看自己的攻击力与对方的攻击力，若自己的攻击力大于怪兽则攻击它，否则不会行动；若是人类遇上人类或怪兽遇上怪兽，不会发生任何事情；若其中一方在之前的回合已经被击杀，则本回合也不会发生任何事情
问题：当回合结束后，每个角色的存活状态
思路：直接模拟
role[] 记录角色、k[] 记录角色的攻击力，下标为角色编号，值为 master 或 human，用一个 die[] 数组记录每个角色的存活状态
每一回合中，首先是 判断是否有一方已经死亡，如果有则不做任何操作；其次是 判断本次相遇是否会发生攻击事件，当人类遇到怪兽，且人类暴露身份 或 怪兽暴露身份且人类攻击力大于他的时候才会发生攻击事件；最后是 判断攻击发生之后鹿死谁手
这里只展示每回合如何处理（因为懒得再写一遍了）
本回合：n1 与 n2 角色相遇，攻击力分别为 k1 与 k2，是否透露身份分别为 m1 和 m2
if (die[n1] == 1 || die[n2] == 1) continue; // 有一方在之前回合已经被击杀，本次不会发生任何事情
// 找到会发生攻击的情况
if (role[n1].charAt(0) == 'h' && role[n2].charAt(0) == 'm' // n1为人类，n2为怪兽
&& (m1 == 'Y' || m2 == 'Y' && k[n1] > k[n2]) // 人类暴露身份或怪兽暴露身份且人类发现能够击杀怪兽
|| role[n2].charAt(0) == 'h' && role[n1].charAt(0) == 'm' // n2为人类，n1为怪兽，类似上述逻辑
&& (m2 == 'Y' || m1 == 'Y' && k[n2] > k[n1])) {
// 发生攻击了，开始判断谁为英雄谁为狗熊
if (k[n2] > k[n1]) die[n1] = 1;
else if (k[n2] > k[n1]) die[n2] = 1;
else {
die[n1] = 1;
die[n2] = 1;
}
}
题目一：
给一个数字 k，有一个数组 a，输出任意一个数组 b 满足 (ai + bi) % i == 0，且 b 数组的元素不能重复
思路：
public int[] solution(int[] a) {
HashSet<Integer> set = new HashSet<>();
int[] b = new int[a.length];
for (int i = 0; i < a.length; ++ i) {
int temp = i - a[i] % i;
while (true) {
if (set.contains(temp)) {
temp += i;
} else {
set.add(temp);
b[i] = temp;
break;
}
}
}
return b;
}
边学边写，如有错误，欢迎指正！
投递帆软软件等公司10个岗位 >