美团3.18 后端开发笔试

这是美团第二次笔试，上次只A了2.63，这次A了4.64。

第一题

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。

敌人的位置将被一个二维坐标 (x, y) 所描述。

小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。

捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。

现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

input:

3 1 1

1 1

1 2

1 3

output:

这道题我一上来有点摸不着头脑，随便写了一下就跳过先做后面的了。回过头来尝试用排序+滑动窗口过了。代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int ans = 1;
        int[][]loc = new int[n][2];
        for (int i=0;i<n;i++){
            loc[i][0] = sc.nextInt();
            loc[i][1] = sc.nextInt();
        }
        Arrays.sort(loc,(o1, o2) -> o1[0]-o2[0]);
        for (int i=0;i<n;i++){
            ArrayList<int[]> list = new ArrayList<>();
            int x = loc[i][0];
            for (int j=i;j<n;j++){
                int x2 = loc[j][0];
                if (x2-x>a)
                    break;
                list.add(loc[j]);
            }
            Collections.sort(list,(o1, o2) -> o1[1]-o2[1]);

            int index = 0;
            int cnt = 0;
            for (int j=0;j<list.size();j++){
                int y2 = list.get(j)[1];
                while(y2-list.get(index)[1]>b){
                    index++;
                    cnt--;
                }
                cnt++;
                ans = Math.max(ans,cnt);
            }
        }
        System.out.println(ans);
    }
}

第二题

小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。

因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。

显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。

你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。

简单滑动窗口题，AC。

第三题

现在小美获得了一个字符串。小美想要使得这个字符串是回文串。

小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符’a’-‘z’。

你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。

数据保证能在题目限制下形成回文字符串。

注：回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。

例如字符串abcba, aaaa, acca都是回文字符串。字符串abcd, acea都不是回文字符串。

输入：一行，一个字符串。字符串中仅由小写英文字符构成。保证字符串不会是空字符串。字符串长度介于 [1, 100000] 之间。

这道题分类讨论即可，当时过了91%，回过头来发现的确有一部分没有讨论到。思路如下：

先遍历字符串，将原字符串进行改造为回文串，同时记录下需要修改的字符数

如果有2个地方需要修改，例如下标为i的地方需要修改，找到其对应的回文位置（n-i-1），比较这两个位置字符的字典序，选较小的进行设置即可。
如果有1个地方需要修改，我们就看这个下标i与n-i-1的位置的字符是否为'a'，如果都不为'a'，需要修改两次，都修改成'a'；如果有一个为'a'，则将另一个也修改为'a'之后，判断一下字符串长度是奇数还是偶数，如果是奇数则将中间位置的字符也设置为'a'。
如果没有地方需要修改，遍历字符串将其调整为字典序最小的字符串即可（在2次修改次数内）。

第四题

现在商店里有N个物品，每个物品有原价和折扣价。小美想要购买商品。小美拥有X元，一共Y张折扣券。小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽量减少花费。你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入：第一行三个整数，以空格分开，分别表示N,X,Y。接下来N行，每行两个整数，以空格分开，表示一个的原价和折扣价。 1≤N≤100, 1≤X≤5000, 1≤Y≤50，每个商品原价和折扣价均介于[1,50]之间。

用DFS可以过73%。后来想想大概可以用DP来做，可惜时间不允许了。

第五题

现在有若干节点。每个节点上有能量塔。所有节点构成一棵树。某个节点u可以为和u距离不超过给定值的节点各提供一点能量。此处距离的定义为两个节点之间经过的边的数量。特别的，节点u到本身的距离为零。现在给出每个节点上的能量塔可以为多远的距离内的点提供能量。小美想要探究每个节点上的能量值具体是多少。你的任务是帮助小美计算得到，并依次输出。

输入：第一行一个整数N，表示节点的数量。接下来一行N个以空格分开的整数，依次表示节点1，节点2，…，节点N的能量塔所能提供能量的最远距离。接下来N-1行，每行两个整数，表示两个点之间有一条边。 1≤N≤500，节点上能量塔所能到达的最远距离距离不会大于 500.

input：

1 1 1

1 2

2 3

output: 2 3 2

AC了。这部分代码忘记留了，整体思路比较暴力，回溯进行节点的遍历，对于每个节点再进行回溯（比如从节点2位置进行长度为1的回溯，因为给出的距离数组节点2的发散距离为1）进行能量的计算，这一部分对于能回溯到的节点就ans[x]++，回溯完成之后输出ans数组即可。

#我的实习求职记录##你觉得今年春招回暖了吗#