8月6日美团笔试题-后端AK代码
4 + 1 全部100%通过，但代码像shit一样，心情好时候再重构一下。
第一题，礼品盒分配
解题思路：分情况进行讨论，礼盒数取决于 A B 最小值 和 A B 间的差值
可以看做，先在每个礼盒中放入 一个 A 和 一个 B
max - min，就是在每个盒子中放入 1 A 和 1 B 后剩余的 sub
如果 sub >= min，那么所有礼盒都可以满足 3 个礼品
否则，不能将第一步中所有礼盒装满，直接返回 ( A + B) / 3即可
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int T = input.nextInt(); while (T-- > 0){ int num1 = input.nextInt(); int num2 = input.nextInt(); System.out.println(getAns(num1, num2)); } } public static int getAns(int x, int y){ int min = Math.min(x, y), max = Math.max(x, y), sub = max - min; if(sub >= min) return min; else return (max + min) / 3; } }第二题 实验结果
结题思路：
采用 left 数组保存 i 之前的小于等于0的数量
采用 right 数组保存 i 之后大于等于0的数量
遍历即可public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); while (input.hasNextLine()){ int n = Integer.parseInt(input.nextLine()); String[] line = input.nextLine().split(" "); int[] nums = new int[n]; for(int i = 0; i < n; ++i) nums[i] = Integer.parseInt(line[i]); int[] left = new int[n], right = new int[n]; int ans = n, count = 0; for(int i = 0; i < n; ++i){ if(nums[i] >= 0) ++count; left[i] = count; } count = 0; for(int i = n - 1; i >= 0; --i){ if(nums[i] <= 0) ++count; right[i] = count; } for(int i = 0; i <= n; ++i){ int l = i == 0 ? 0 : left[i - 1]; int r = i == n ? 0 : right[i]; ans = Math.min(ans, l + r); } System.out.println(ans); } } }
第三题，魔法石
- 首先根据第二行，进行预处理，对经过反转可以得到的数字进行统计
- 再对第一行数据，进行排序，排序的作用就是计算相同数字的最大数量
- 当 相同数字数量 + 反转数字可以得到的数量 >= (n + 1) / 2
- 记录最小的翻转次数 (n + 1) / 2 - count
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNextLine()){
int n = Integer.parseInt(input.nextLine());
int[][] arr = new int[n][2];
String[] line = input.nextLine().split(" ");
for(int i = 0; i < n; ++i) {
arr[i][0] = Integer.parseInt(line[i]);
}
line = input.nextLine().split(" ");
for(int i = 0; i < n; ++i) {
arr[i][1] = Integer.parseInt(line[i]);
}
Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]);
// map 记录由 第二行反转 每个数字 及由反转得到的最大数量
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < n; ++i){
if(arr[i][1] != arr[i][0]) map.put(arr[i][1], map.getOrDefault(arr[i][1], 0) + 1);
}
int count = 1, ans = -1;
for(int i = 1; i < n; ++i){
if(arr[i][0] == arr[i - 1][0]){
++count;
// 当 第一行数量 + 第二行反转数量 >= (n + 1) / 2，即满足要求
if(i == n - 1){
if(count + map.getOrDefault(arr[i][0], 0) >= (n + 1) / 2){
if(count >= (n + 1) / 2) ans = 0;
else{
if(ans == -1) ans = (n + 1) / 2 - count;
else ans = Math.min(ans, (n + 1) / 2 - count);
}
}
}
}else{
// 当 第一行数量 + 第二行反转数量 >= (n + 1) / 2，即满足要求
if(count + map.getOrDefault(arr[i - 1][0], 0) >= (n + 1) / 2){
if(count >= (n + 1) / 2) ans = 0;
else{
if(ans == -1) ans = (n + 1) / 2 - count;
else ans = Math.min(ans, (n + 1) / 2 - count);
}
}
count = 1;
}
}
if(ans == -1){
for(int val : map.values()){
if(val >= (n + 1) / 2) ans = (n + 1) / 2;
}
}
System.out.println(ans);
}
}
}
第四题 数学竞赛
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNextLine()){
String[] line = input.nextLine().split(" ");
int n = Integer.parseInt(line[0]), k = Integer.parseInt(line[1]);
int[] nums = new int[n];
line = input.nextLine().split(" ");
for(int i = 0; i < n; ++i) nums[i] = Integer.parseInt(line[i]);
Map<Integer, List<Integer>> map = new HashMap<>();
for(int i = 0; i < n; ++i){
List<Integer> temp = map.getOrDefault(nums[i], new ArrayList<>());
temp.add(i + 1);
temp.sort((o1, o2) -> o1 - o2);
map.put(nums[i], temp);
}
List<Integer> test = new ArrayList<>(), train = new ArrayList<>();
for(int key : map.keySet()){
List<Integer> arr = map.get(key);
int size = arr.size();
for(int i = 0; i < size; ++i){
if(i < (size + 1) / 2) train.add(arr.get(i));
else test.add(arr.get(i));
}
}
test.sort((o1, o2) -> o1 - o2);
train.sort((o1, o2) -> o1 - o2);
for(int num : train) System.out.print(num + " ");
System.out.println();
for(int num : test) System.out.print(num + " ");
}
}
}
附加题 第K个数字
字符串的表示为 [source][rever][wow]，三个部分
解题思路：使用字符串模拟，估计不是内存溢出，就是时间超时
采用 index，和 len 去模拟字符串，根据 index 和 len 的关系，不断去缩小范围知道 index 在MeiTuannauTieMwow 这个字符串长度内
如果 len - index < 3，那么刚坐标处于 "wow"结尾中
如果 index > (len - 3) /2 ，那么index 处于 rever 这个范围中
如果 index < (len - 3) / 2，那么index 处于 source这个返回中
如果 index < "MeiTuannauTieMwow".length，那么直接返回
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = Integer.parseInt(input.nextLine()); while (n -- > 0){ long target = Long.parseLong(input.nextLine()); String str = "MeiTuannauTieMwow"; long len = str.length(); long index = target; while (index > len){ len = len * 2 + 3; } while (true){ if(len - index < 3) { System.out.println("wow".charAt((int)(len - index))); break; }else if(index <= str.length()){ System.out.println(str.charAt((int)(index - 1))); break; }else if(index > (len - 3) / 2){ index = len - 3 - index + 1; len = (len - 3) / 2; }else{ len = (len - 3) / 2; } } } } }
