拼多多笔试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个

我的思路

  1. 一个色子共有24种状态, 遍历起来很复杂. 但是色子的分布有规律, 找到规律就迎刃而解.
  2. 我将每个色子转成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)
  3. 具体将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##拼多多#
全部评论
厉害,大佬
点赞 回复
分享
发布于 2020-08-02 21:46
厉害
点赞 回复
分享
发布于 2020-08-02 21:48
饿了么
校招火热招聘中
官网直投
猛呀猛呀
点赞 回复
分享
发布于 2020-08-02 21:52
大佬问下,把输入的n个数存到数组里面,在用数组计算,这样会导致数组越界吗
点赞 回复
分享
发布于 2020-08-02 21:54
不是有4道题吗?
点赞 回复
分享
发布于 2020-08-02 21:56
666
点赞 回复
分享
发布于 2020-08-02 21:59
第二题每种扔法次数是无穷的,怎么判断几种组合的扔法无法满足条件呢
点赞 回复
分享
发布于 2020-08-02 22:00
第一题为什么num=distance时候要让distance -= ansCount不直接输出呢
点赞 回复
分享
发布于 2020-08-03 07:51
大佬 第三题能不能够给一个解题思路
点赞 回复
分享
发布于 2020-08-03 09:46
第二种状态判断是降升,你转换成了降降,是应该转为升升吗?是我理解错了吗?
点赞 回复
分享
发布于 2020-08-03 11:08
我知道你第三题10%差在哪,最前面加个特判如果t是0,返回0,一顿也不吃。
点赞 回复
分享
发布于 2020-08-03 11:45
楼主做的思路很清晰了,比我写的垃圾代码好太多。不过我有一个问题:就是如果美味值是10,样例中有 2   10, 1   11两个,二分的时候找到的是2  10这种餐,但明显选美味值为11的这种热量更少而且满足美味值啊,漏掉了这餐。题目好像没有说要达到正好的美味值。
点赞 回复
分享
发布于 2020-08-03 12:07
🐂 是我不想回忆起来的伤痛(老网抑云了
点赞 回复
分享
发布于 2020-08-03 12:14
666
点赞 回复
分享
发布于 2020-08-03 12:17
第一道题目的 输入: 3 2 4 6 输出: 5 2 这个该怎么解释呢 ?😥
点赞 回复
分享
发布于 2020-08-03 13:13
太强了吧
点赞 回复
分享
发布于 2020-08-03 13:55
tql
点赞 回复
分享
发布于 2020-08-03 23:24
感谢老铁,整理得这么完整。
点赞 回复
分享
发布于 2020-08-10 09:55

相关推荐

17 66 评论
分享
牛客网
牛客企业服务