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; }
边学边写,如有错误,欢迎指正!