美团笔试8.15开发笔试题解

开发一共五个题，四个编程，一个附加题。我的第四题打车题只过了27％，剩下的都A了，下面是题干和代码

第一题：小美的序列检查
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美给小团一个n个数字构成的数字序列，问小团能不能经过重新排列后形成1到n的排列。

        举例：

        小美给小团[2, 1, 3]，则可以经过重新排列后构成[1, 2, 3]，这是可行的。

        小美给小团[4, 4, 1, 3]，则无法经过重新排列后构成[1, 2, 3, 4]，这是不可行的。

        为了防止小团靠运气碰对答案，小美会进行多组询问。



        输入描述
        第一行是一个数T，表示有T组数据。

        对于每组数据：

        第一行一个数字n表示小美给出的序列由n个数字构成。

        接下来一行n个空格隔开的正整数。

        输出描述
        对于每组数据，如果可以重新排列后得到1到n的排列，回答一行Yes，如果不可以，回答No

        请注意大小写。

思路：暴力即可

import java.util.*;
class Solution {
    public boolean check(int[] nums){
        Set<Integer> set = new HashSet<>();
        for(int it : nums) {
            if(set.contains(it) || it < 1 || it > nums.length) {
                return false;
            }
            set.add(it);
        }
        return true;
    }
}
class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Solution so = new Solution();
        int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            int[] nums = new int[n];
            for(int i = 0; i < nums.length; i++) {
                nums[i] = in.nextInt();
            }
            if(so.check(nums)) {
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
}

第二题：小美的回文串构建
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美现在有一个字符串，小美现在想知道能不能通过在字符串的尾端增加若干字符使得整个字符串变成一个回文串。

        回文串的定义：若一个字符串，对他正序遍历和倒序遍历得到的结果是完全一致的，就称它是一个回文串。例如 abcba 就是一个回文串，因为无论正序还是倒序都是一样的。



        对于字符串 abaaca，显然在该字符串末尾继续补上三个字符 aba 就可以构成 abaacaaba，就可以把原字符串变成回文串。换句话说，最少补上三个字符。

        你的任务就是找到使得原来的字符串变成回文串所需要的最少字符数量。

        * 本题数据保证没有空串，因此不考虑空串是否为回文串。

        保证输入的字符串仅包含小写字母。

        输入描述
        一行一个字符串，代表小美交给你的字符串。

        输出描述
        一行一个整数，表示将小美给出的字符串变成回文字符串所需要添补的最少字符数量。


        样例输入
        abaaca
        样例输出
        3

        提示
        输入样例2

        aba

        输出样例2

        0

        数据范围和说明

        对于40%的数据，字符串长度小于等于10

        对于60%的数据，字符串长度小于等于1,000

        对于100%的数据，字符串长度小于等于1,000,000

思路：暴力即可，从字符串中间开始判断，如果一开始是回文串则不需要补充，否则指针往右移动继续判断，直到找到右侧与左侧满足回文则返回结果。

import java.util.*;
class Solution {
    public boolean check(String str, int center, boolean isOdd){
        int l = center - 1;
        int r = center;
        if(isOdd) {
            r++;
        }
        while (r < str.length()) {
            if(str.charAt(r) == str.charAt(l)) {
                l--;
                r++;
            }else {
                return false;
            }
        }
        return true;
    }
}
class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Solution so = new Solution();
        while (in.hasNext()){
            String str = in.nextLine();
            int center = str.length() / 2;
            int res = 0;
            boolean isOdd = (str.length() % 2) != 0;

            while (!so.check(str, center, isOdd)) {
                if(isOdd) {
                    isOdd = false;
                    center++;
                }else {
                    isOdd = true;
                }
                res++;
            }
            System.out.println(res);
        }
    }
}

第三题：小美的机器人
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美在数轴上放置了若干个机器人，这些机器人每到整数时刻，就会检查是否和其他机器人重合。如果重合，它就会原地爆炸。

        这些机器人的移动速度均为 1 。举例来说，如果一个机器人初始位于点3，然后它的方向是向右的，则时刻1会位于点4，时刻2会位于点5。

        小美现在给小团这样一个任务：小美将给出所有机器人的初始位置和初始朝向。小团的任务是判断每个机器人的爆炸时刻。当然，如果有一些机器人永远不会爆炸，则输出-1。

        小团向你求助。你能帮帮小团吗？

        注意事项1：一个机器人爆炸了之后，就不会再继续存在在这个数轴上。

        举例来说，如果有三个机器人，一个位于位置0，向右，一个位于位置2，向右，一个位于位置4，向左。则时刻1的时候，后两个机器人会在位置3相遇并发生爆炸，此后第一个机器人和第三个机器人不会在时刻2继续爆炸（因为此时已经不存在第三个机器人了）

        注意事项2：请注意，只有整数时刻机器人才会检查重合。

        举例来说，如果有两个机器人，一个位于位置1，向右，一个位于位置2，向左，则它们并不会在整数时刻重合。因此它们两个不存在相遇爆炸。

        注意事项3：保证机器人初始时刻不会重叠。换句话说，不存在在时刻0就立刻爆炸的机器人。



        输入描述
        第一行一个正整数 n 表示有 n 个机器人。

        接下来 n 行，每行一个正整数和一个字符，以空格分隔。正整数代表机器人的坐标，字符为大写字母 L 和 R 的其中一个，分别表示机器人向左运动 和 向右运动。

        输出描述
        输出 n 行，每行一个数字，对应表示每个机器人的答案：

        若该机器人会爆炸，输出爆炸时间；若该机器人不会爆炸，输出-1。


        样例输入
        10
        94 R
        74 L
        90 L
        75 R
        37 R
        99 R
        62 R
        4 L
        92 L
        44 R
        样例输出
        -1
        6
        23
        -1
        -1
        -1
        6
        -1
        -1
        23

        提示
        数据范围和说明

        对于所有数据都保证机器人的坐标处于[1, 1e9]的正整数范围内。

        其中，对于30%的数据，保证机器人数量 n <= 10

        对于100%的数据，保证机器人数量 n <= 1,000

思路：依然是暴力法，暴力法万岁。用一个哈希表存机器人，key是机器人位置，value是机器人的初始序号以及初始方向。然后每次选择两个即将相撞的机器人，选择方法是遍历所有机器人对，如果这对机器人相向而行，并且距离为奇数，即可相撞，选择所有会相撞的机器人对的距离最小值minDis。然后所有机器人移动minDis，把相撞的机器人从哈希表去掉，并更新结果数组即可。

import java.util.*;
class Bot{
    Boolean isLeft = true;
    int seq = 0;
    public Bot(boolean isLeft, int seq) {
        this.isLeft = isLeft;
        this.seq = seq;
    }
}
class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        Arrays.fill(nums, -1);
        Map<Integer, Bot> map = new HashMap<>();
        int time = 0;
        in.nextLine();
        for(int i = 0; i < n; i++) {
            String[] str = in.nextLine().split(" ");
            boolean isLeft = str[1].equals("L");
            map.put(Integer.valueOf(str[0]), new Bot(isLeft, i));
        }
        while(true) {
            int minDis = Integer.MAX_VALUE;
            for(Map.Entry<Integer, Bot> bot1 : map.entrySet()) {
                for(Map.Entry<Integer, Bot> bot2 : map.entrySet()) {
                    if(bot1.getKey() != bot2.getKey() && bot1.getValue().isLeft && !bot2.getValue().isLeft
                    && bot2.getKey() < bot1.getKey() && (bot1.getKey() - bot2.getKey() + 1) % 2 != 0) {
                        minDis = Math.min(minDis, bot1.getKey() - bot2.getKey() + 1);
                    }
                }
            }
            if(minDis == Integer.MAX_VALUE) {
                break;
            }
            int dis = minDis / 2;
            time += dis;
            Map<Integer, Bot> tmap = new HashMap<>();
            for(Map.Entry<Integer, Bot> bot : map.entrySet()) {
                int index = bot.getKey();
                if(bot.getValue().isLeft) {
                    index -= dis;
                }else {
                    index += dis;
                }
                if(tmap.containsKey(index)) {
                    nums[bot.getValue().seq] = time;
                    nums[tmap.get(index).seq] = time;
                    tmap.remove(index);
                }else {
                    tmap.put(index, bot.getValue());
                }
            }
            map = tmap;
        }
        for(int it : nums) {
            System.out.println(it);
        }
    }
}

第四题：小美的最快到达时间
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美现在临时接到一个会议通知，需要立刻赶往对应地点开会。

        不妨将小美所在的地点抽象成一个图。小美位于节点x的位置，将要赶往节点y开会。

        小美启动了打车软件，该打车软件可以将起点定位在任何一个节点开始叫车。但是，叫车是需要时间的，不同位置叫车的等车时间不同。

        这就意味着，考虑到叫车的时间，小美可以不选自己所在的节点叫车，而选择一个附近的点叫车，在等车时间内自行走路到对应的节点以缩短综合时间，更快地赶到目的地开会。

        请注意：小美的叫车终点只能是开会处，即此题不考虑通过多次打车来缩短时间，只考虑更改起点带来的时间减少。



        下面给出一个简单的例子来帮助你理解：

        小美位于节点1，开会的地点位于节点3

        节点1和节点2之间有一条汽车通行时长为1，步行通行时间为2的通路；

        节点2和节点3之间有一条汽车通行时长为2，步行通行时间为5的道路；

        节点1的打车等候时间为10，节点2的打车等候时间为1，节点3的打车等候时间为5



        此时，显然小美有如下几种方案：

        第一种方案：小美在节点1打车，此时小美需要先等时间10上车，之后花费3的时间抵达节点3，共计花费时长13；

        第二种方案：小美在节点2打车，此时小美需要步行时长2抵达节点2，此时汽车司机已经等候在节点2，小美直接上车，通行时长2后抵达节点3。共计花费时长为4。

        第三种方案：小美直接步行到节点3（因为节点3是开会地点，显然在节点3打车无意义），此时花费的时长为7。



        以上三种方案中，应选第二种方案能最快抵达开会地点。共计花费时长为4。



        注意：实际打车过程中，司机会存在客人太久没来上车自行取消的可能，这里为了简化问题，我们假设司机耐心是充分的，可以无限制等候乘客。



        输入描述
        第一行四个正整数n,m,x,y，空格隔开，其中 n 表示点的数量，点的序号依次表示为 1 到 n；m表示边的数量；x表示小美当前的节点位置，y表示小美开会的节点位置。

        接下来 m 行，每行四个正整数，空格隔开，x, y, p, q，表示节点 x 和节点 y 之间有一条汽车通行时长 p，步行通行时长 q 的双向道路。

        接下来一行 n 个空格隔开的正整数，第 i 个正整数表示在第i个节点打车所需要花费的等车时间。

        输出描述
        输出一行一个正整数表示小美最快抵达开会地点的时间。


        样例输入
        3 2 1 3
        1 2 1 2
        2 3 2 5
        10 1 5
        样例输出
        4

        提示
        数据范围和说明

        对于全体数据保证p和q（即汽车通行时间和步行时间）都是[1, 50]内的正整数，保证每个点打车的等候时间都是[1, 1000]内的正整数

        对于n和m，对于60%的数据，保证 1<= n <= 10, 1 <= m <= 30, 对于100%的数据，保证 1<= n <= 50, 1 <= m <= 200，数据保证没有重复的边。

思路： 这个题我只过了百分之27，不知道哪里错了，可能最后时间不够有些细节问题或者一开始思路就错了，讲一下我的思路吧。先计算出始发地到所有地点的最短步行距离minSteps（最短路径可以用dfs或者迪杰斯特拉），在计算所有地点到终点的最短汽车距离minBuses,然后遍历所有地点i，选择Math.max(minSteps[i], waitTime[i]) + minBuses[i]中的最小值。因为我没过完，就不贴代码了。

第五题：小美的水洼地冒险
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美现在想要经过一个总距离长为n的水洼地。其中一些地块是水坑，另一些是地面。初始的时候小美位于这段水洼地的首个地块的位置。

        很显然小美不想自己的鞋湿掉。于是小美想出一个办法：小美每次可以跳到非水坑的地方。不过小美的力气有限，每一步都至多跳距离p。换句话说，小美当前位置在第i个地块上，那么小美下一步可以位于[i+1, i+p]之间的非水坑的地块上。

        但小美每跳一步都会消耗力气，跳不同的距离对小美的力气消耗是不同的。

        你的任务是帮助小美计算最小的力气消耗，即在保证小美跳到第n个地块的前提下（注意：刚好是第n个地块，本题中不存在n+1之后的地块），求出最少要花费多少力气。



        输入描述
        第一行两个正整数n和p，空格隔开，n表示地块的数量，p表示小美单次的最远跳跃距离。

        接下来一行一个长度为n的字符串，只包含小写字母o和小写字母x，其中小写字母o表示地面，小写字母x表示水坑。保证字符串中的首个字符和末尾字符一定是地面（即小写字母o），保证从起点到终点至少存在一种合法路径。

        接下来一行p个正整数，第i个数字表示小美跳跃距离i所需要花费的体力值。（请注意：不保证小美跳的近就一定花费更少的力气）

        输出描述
        一行一个正整数表示小美最少花费的体力值。


        样例输入
        10 5
        oxxoooxxxo
        1 6 9 15 18
        样例输出
        26

        提示
        样例解释

        地块1 -> 地块4 -> 地块5 -> 地块6 -> 地块10

        共计花费力气 9 + 1 + 1 + 15 = 26



        数据范围和说明

        对于40% 的数据保证 n <= 100, 5 <= p <= 10

        对于100%的数据保证 n <= 10,000, 5 <= p <= 100

        小美每步跳跃的力气保证是个[1,100]之间的正整数。但不保证跳的越远小美需要消耗的力气越大。

思路：简单dp，dp[i] = Math.min(dp[i], dp[i - dis] + cost[dis]) 其中dp[i]是到i的最小花费，dp[i - dis]表示到达离i距离为dis的点的最小化费，cost[dis]表示跳dis步需要多少花费

import java.util.*;
class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        in.nextLine();
        char[] path = in.nextLine().toCharArray();
        int[] cost = new int[p];
        for(int i = 0; i < p; i++) {
            cost[i] = in.nextInt();
        }
        int[] dp = new int[path.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i < path.length; i++) {
            if(path[i] != 'x') {
                for(int dis = 0; dis < p; dis++) {
                    int pre = i - dis - 1;
                    if(pre >= 0 && path[pre] != 'x') {
                        dp[i] = Math.min(dp[i], dp[pre] + cost[dis]);
                    }
                }
            }
        }
        System.out.println(dp[dp.length - 1]);
    }
}