拼多多笔试2020 08 02 题目(含"色子种类")详解
前两题AC, 第三题90%. 分享前三题题目及代码
2020 08 03 更新: 更新了前三题的
题目思路代码注释. 第四题没看......
题目
第一题
掷色子走路. 给了离终点的距离. 给了接下来还能走几步和每一步的步数.(比如距离终点3, 下一步走5步, 则是走到终点再倒退2步). 如果中间某一步恰好停在终点. 返回 "paradox". 否则返回最后距离终点的距离以及折返的次数.
举例:
10 4 // 距离终点10, 还能走4步 6 3 3 3 // 每次分别走 6 3 3 3步 将返回 1 2 // 距离终点距离1, 往回走了2次. 第一次走6步距离4, 第二次走3步距离1, 第三次走1步回2步距离2, 第四次走2步回1步距离1
我的思路
题目简单, 看代码就能理解
第二题
每一颗色子都有六面. 给出色子的个数和每一个色子的上下前后左右方位的点数. 色子可以旋转. 问有多少种色子, 每种多少个(按照降序打印)
举例:
3 // 色子个数 1 2 3 4 5 6 // 上下前后左右点数 1 2 6 5 3 4 // 可旋转为上面这个 1 2 3 4 6 5 // 不可旋转成上面的形式 将返回 2 // 两种色子 2 1 // 每种分别是2个 1个
我的思路
- 一个色子共有24种状态, 遍历起来很复杂. 但是色子的分布有规律, 找到规律就迎刃而解.
- 我将每个色子转成1 B1 A2 B2 A3 B3的形式(A1 = 1, Ai<Bi). 直观上就是将1放在第一位, 然后每两个为一对, 三对都是升序. 每个色子在这个状态下是完全固定的.(动手将1 2 6 5 3 4转换体验一下) 此时判断是否是同一种就容易很多了.(这里存储状态使用的是hash方法, 后面5位依次乘以7, 7^2, 7^3, 7^4, 7^5. 将乘积的和当作hashMap的key)
- 具体将24种转换为固定1种的方法如下:
- 色子的旋转过程可以看成 Ai Bi Aj Bj 的一次变换(比如固定上下, 那么就是将色子左右在旋转, 只有四个面在交替变换).
- 沿左右旋转, 总共会有四种情况. Ai Bi Aj Bj, Aj Bj Bi Ai, Bj Aj Ai Bi, Bi Ai Bj Aj. 可以看到其实就是 升升 升降 降升 降降 四种情况. 碰到后面三种时转换为第一种.
- 先找到1的位置, 然后先通过旋转将1转换到第一个位置. 然后再去操作后面四个数, 转换为升 升的形式
- 代码中change_1是将1转到第一位, change_state是将后面三种状态转到第一种 Ai Bi Aj Bj 的状态.
第三题
食堂吃饭, 分中餐和晚餐, 每一餐又分若干种套餐. 每种套餐有热量和美味值两个属性. 每餐最多只能选一种套餐(可不吃). 问在满足能量值的情况下, 最少摄入的热量. 返回最少的热量, 如果不能达到美味值则返回-1. 50%的中餐晚餐不超过100000种, 100%的中餐晚餐不超过200000种.
举例:
3 3 10 // 中餐套餐数 晚餐套餐数 要求的美味值 1 1 // 热量 美味值 2 5 3 7 2 4 4 8 6 9 将返回 5 (中餐选3 7 晚餐选 2 4, 此时热量最少)
我的思路
这题写的不好, 使用动态规划存储美味值和最少热量, 有兴趣的朋友可以看看.
- 我的思路是使用两个二维数组分别存储中餐和晚餐的美味值和 获得该美味值的最少热量. 按照美味值从小到大排序. 最少热量是重点!!!
- 比如下面例子的中餐情况 lunch = [[1,1],[5,2],[7,3]] (这里热量刚好递增, 实际上可能出现7的热量更低, 此时7前面的热量都不应该超过7的热量. 比如出现美味12热量11, 美味10热量13. 则美味10对应的获得该美味值的最少热量为11).
- 具体构造要求数组的方法是从大到小遍历美味值, 然后一直更新此时的最少热量值. 当作当前美味值的最少热量值.
- 从小到大遍历中餐数组, 下标为 i 的中餐, 美味值是lunch[i][0], 最少热量是lunch[i][1]. 然后使用自定义的 binarySearch 寻找满足晚餐中满足 dinner[j][0] >= (target美味值 - lunch[i][0]) 的最小下标j. 然后更新最少热量 ans = Math.min(ans, lunch[i][1] + dinner[i][1]) 即可.
- 针对不能满足美味值和一顿餐食就能满足的情况容易判断, 就不赘述了, dai'm.
代码
第一题 AC
import java.util.Scanner;
public class T1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int distance = in.nextInt(); // 距离终点距离
int count = in.nextInt(); // 还能走多少步
if (distance == 0) {
System.out.println("paradox");
}
int ansCount = 0; // 折返次数
while (count-- > 0) {
int num = in.nextInt();
if (num < distance) { // 未到终点
distance -= num;
} else if (num > distance) { // 折返
ansCount++;
distance = num - distance;
} else {
distance -= num; // 最后一步到达终点则需要返回距离0和次数, 而不是paradox
if (count > 0) {
System.out.println("paradox");
return;
}
}
}
System.out.println(distance + " " + ansCount);
}
} 第二题 AC
import java.util.*;
public class T2 {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<>();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] base = calcuBase(); // 数组 7 7^2 7^3 7^4 7^5
while (n-- > 0) {
int[] arr = new int[6]; // 存储色子点数
int idx_0 = 0; // 点数1 所在的下标
for (int i = 0; i < 6; i++) {
arr[i] = in.nextInt();
if (arr[i] == 1) {
idx_0 = i;
}
}
if (idx_0 != 0) { // 1不在首位, 将其转到首位
change_1(arr, idx_0);
}
boolean flag1 = arr[2] < arr[3]; // 第二队是否升序
boolean flag2 = arr[4] < arr[5]; // 第三队是否升序
// 状态转换
if (!flag1 && flag2) {
changeState(arr, 2);
} else if (!flag1 && !flag2) {
changeState(arr, 3);
} else if (flag1 && !flag2) {
changeState(arr, 4);
}
int key = calcuHashKey(arr, base); // 计算hashMap的key
map.put(key, map.getOrDefault(key, 0)+1);
}
System.out.println(map.size());
int[] ans = new int[map.size()]; // 每种个数存储到数组里, 进行降序排列
int i = 0;
for (int num_map: map.values()) {
ans[i] = num_map;
i++;
}
Arrays.sort(ans);
for (i = ans.length-1; i > 0; i--) {
System.out.print(ans[i] + " ");
}
if (ans.length > 0) {
System.out.print(ans[0]);
}
}
// 构造数组 7 7^2 7^3 7^4 7^5
public static int[] calcuBase() {
int[] base = new int[6];
base[0] = 7;
for (int i = 1; i < 6; i++) {
base[i] = 7 * base[i-1];
}
return base;
}
// 计算hashMap中状态1 B1 A2 B2 A3 B3应该对应的key
public static int calcuHashKey(int[] arr, int[] base) {
int sum = 0;
for (int i = 0; i < 6; i++) {
sum += arr[i] * base[i];
}
return sum;
}
// 将1移到开头
public static void change_1(int[] arr, int idx_0) {
if (idx_0 == 1) {
swap(arr, 0, 1);
swap(arr, 2, 3);
} else if (idx_0 % 2 == 1){
swap(arr, 1, idx_0);
swap(arr, 0, idx_0-1);
swap(arr, 0, 1);
} else {
swap(arr, 0, idx_0);
swap(arr, 1, idx_0+1);
swap(arr, idx_0, idx_0+1);
}
}
// 剩余三种状态转到第一种状态
public static void changeState(int[] arr, int state) {
int i = 2, p = 4;
if (state == 2) {
swap(arr, i, p);
swap(arr, i+1, p+1);
swap(arr, p, p+1);
} else if (state == 3) {
swap(arr, i, i+1);
swap(arr, p, p+1);
} else if (state == 4) {
swap(arr, i, p);
swap(arr, i+1, p+1);
swap(arr, i, i+1);
}
}
public static void swap(int[] arr, int i, int j) {
int tem = arr[i];
arr[i] = arr[j];
arr[j] = tem;
}
} 第三题 90%
import java.util.*;
public class T3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), t = in.nextInt();
if (t == 0) {
System.out.println(0);
return;
}
// 美味值为key, 热量为value构造treemap, 按照key从大到下排序
TreeMap<Integer, Integer> beautyHotLunchMap= new TreeMap<>(((o1, o2) -> o2-o1));
TreeMap<Integer, Integer> beautyHotDinnerMap= new TreeMap<>(((o1, o2) -> o2-o1));
while (n-- > 0) {
int hot = in.nextInt();
int beauty = in.nextInt();
if (beautyHotLunchMap.containsKey(beauty) && beautyHotLunchMap.get(beauty) <= hot) {
continue;
}
beautyHotLunchMap.put(beauty, hot);
}
while (m-- > 0) {
int hot = in.nextInt();
int beauty = in.nextInt();
if (beautyHotDinnerMap.containsKey(beauty) && beautyHotDinnerMap.get(beauty) <= hot) {
continue;
}
beautyHotDinnerMap.put(beauty, hot);
}
// 构造数组 beautyHotLunch[i][0]表示此时的美味值. 美味值从后到前递减. beautyHotLunch[i][1] 表示获取该美味值的最少热量
// 最少热量是重点, 体现在 minHot 从后往前的更新上
int[][] beautyHotLunchArr = new int[beautyHotLunchMap.size()][2];
int i = beautyHotLunchArr.length-1;
int minHot = Integer.MAX_VALUE; // 当前最少热量
for (int beauty: beautyHotLunchMap.keySet()) {
minHot = Math.min(beautyHotLunchMap.get(beauty), minHot);
beautyHotLunchArr[i] = new int[]{beauty, minHot};
i--;
}
int[][] beautyHotDinnerArr = new int[beautyHotDinnerMap.size()][2];
i = beautyHotDinnerArr.length-1;
minHot = Integer.MAX_VALUE;
for (int beauty: beautyHotDinnerMap.keySet()) {
minHot = Math.min(beautyHotDinnerMap.get(beauty), minHot);
beautyHotDinnerArr[i] = new int[]{beauty, minHot};
i--;
}
// 如果两餐的最大热量不够, 返回-1
if (beautyHotLunchArr[beautyHotLunchArr.length-1][0] + beautyHotDinnerArr[beautyHotDinnerArr.length-1][0] < t) {
System.out.println(-1);
return;
}
int ans = Integer.MAX_VALUE;
// 如果第一餐的最大美味值超过t, 则判断一下只吃第一餐满足要求的最少热量
if (beautyHotLunchArr[beautyHotLunchArr.length-1][0] >= t) {
i = binarySearch_me(beautyHotLunchArr, t); // 自定义的二分查找
ans = Math.min(ans, beautyHotLunchArr[i][1]);
}
// 如果第二餐的最大美味值超过t, 则判断一下只吃第二餐满足要求的最少热量
if (beautyHotDinnerArr[beautyHotDinnerArr.length-1][0] >= t) {
i = binarySearch_me(beautyHotDinnerArr, t);
ans = Math.min(ans, beautyHotDinnerArr[i][1]);
}
for (i = 0; i < beautyHotLunchArr.length; i++) {
int beautyLunch = beautyHotLunchArr[i][0];
if (beautyLunch >= t) { // 中餐足够满足热量时可以退出了
break;
}
int j = binarySearch_me(beautyHotDinnerArr, t - beautyLunch);
// 更新热量值
ans = Math.min(ans, beautyHotLunchArr[i][1] + beautyHotDinnerArr[j][1]);
}
System.out.println(ans);
}
// 数组中满足美味值的最少热量摄入的下标
public static int binarySearch_me(int[][] a, int key) {
int low = 0;
int high = a.length - 1;
while (low < high) {
int mid = (low + high) >>> 1;
int midVal = a[mid][0];
if (midVal < key) {
low = mid + 1;
} else if (midVal >= key) {
high = mid;
}
}
return low;
}
} #拼多多笔试##内推##笔试题目##Java##拼多多#
