3/18美团后端java实习笔试复盘
楼主这波是崩了，看着不难的题就A了一道，A的还是不太会的一道题。。。来分享一波笔试题目顺便给自己复盘一下。楼主算法训练地太少了！没打过ACM，力扣到今天才刷了30道。只能说还是太懒了。希望大家别笑话我
后端依旧是两张卷子，4+1一共五道编程题，美团的题是ACM形式的，不告诉你测试用例，只知道自己正确率。
1、捕获
输入一个矩阵中的几个点，输入最大捕获范围（一个长方形的长与宽），问最多能框住几个点
楼主建了一个二维数组，存了n*2大小的矩阵，n是点的个数，2是每个点的x,y坐标。
楼主想，第一题应该不会难为大家吧，就想直接暴力上手。一开始想遍历数组，找每个点与它后面的点是否行列距离均小于最大捕获范围，后来发现输入数据不是按大小排序，就对每个元素都又遍历了一遍整个数组，记录下最大匹配个数。时间复杂度n方。但楼主忽略了：最大捕获框的四个角不一定非得放在元素上。要暴力的话应对row*col矩阵的row*col个点都搜索一遍。看别的帖子的评论，暴力法还真能过。其他的方法我觉得并查集也许可以，对每个元素检查它能被框住的框的左上角为它的farther，farther在别的元素的框里时将它们俩合并。并查集昨天刚学的，其实楼主不太懂，大家看看就好。
2、回文
给一个字符串，你可以修改两个元素使之成为权值最小的回文字符串，权值a最小，z最大，这个字符串仅包含a到z的字母且修改两个字符一定可以成回文。
这题题干描述的很绕，其实重点不在回文，而在权值最小。它给的字符串至多修改两个字符一定可以成回文，修改成回文不难。楼主想的是用指针pos，记录要修改的字符的位置，再拿字符串的length减1减pos，得到的就是修改后与之对应的、修改后应当相同的字符的位置，再把这两个字符作比较，将它俩改成较小的那个。如果修改一个字符或不修改就能成回文串，就从前往后搜索权值较大的点，把它改小。楼主这题死在了：如果改一个就能成回文，那么就该直接返回，因为想降低权值并保持回文，那么至少应当改两个字符才能保持回文的对称性。楼主还在傻乎乎地想怎么能降权值。。。
类似资料：