2023暑期实习 |
您所在的位置：网站首页 › 美团算法岗笔试 › 2023暑期实习 |
|
2023暑期实习-笔试-美团-技术综合-算法策略方向
公司：美团 形式：编程题 4 道、选择题 3 道 笔试平台：赛码 时长：120分钟 时间：2023-03-18 10:00-12:00 编程题 捕获 描述小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。敌人的位置将被一个二维坐标 (x,y) 所描述。小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。捕获的敌人之间的横坐标的最大差值不能大于 A，纵坐标的最大差值不能大于 B。现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。 输入描述 第一行三个整数 N，A，B，表示共有 N 个敌人，小美的全屏技能的参数 A 和参数 B。接下来 N 行，每行两个数字，描述一个敌人所在的坐标。 1≤N≤500, 1≤A,B≤1000, 1≤x,y≤1000 输出描述 一行，一个整数表示小美使用技能单次所可以捕获的最多数量。 示例输入 3 1 1 1 1 1 2 1 3 输出 2 说明：最多可以同时捕获两名敌人，可以是 (1,1) 和 (1,2) 处的敌人，也可以是 (1,2) 和 (1,3) 处的敌人，但不可以同时捕获三名敌人，因为三名敌人时，纵坐标的最大差值是2，超过了参数B的值 1。 思路观察到坐标的范围不大，x、y 都是 1000 以内的，可以直接将每个敌人放入坐标系中，再枚举坐标系中的每个 A*B 的矩形，统计矩形内的敌人数量。 求敌人数量时使用二维前缀和优化时间，枚举时直接枚举右上端点即可。 代码 N, A, B = map(int, input().split()) mp = [[0 for j in range(1001)] for i in range(1001)] # 在地图内计数 for i in range(N): x, y = map(int, input().split()) mp[x][y] += 1 # 前缀和初始化 for i in range(1, 1001): for j in range(1, 1001): mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1] ans = 0 for i in range(A+1, 1001): #枚举右上端点 for j in range(B+1, 1001): # 此时枚举的矩形为 (i-A, j-B) 到 (i,j)之间的矩形 t = mp[i][j] - mp[i-A-1][j] - mp[i][j-B-1] + mp[i-A-1][j-B-1] ans = max(ans, t) print(ans) 彩带 描述输入描述 第一行两个整数 N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。 接下来一行 N 个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。 1≤N,K≤5000，彩带上的颜色数字介于[1, 2000]之间。 输出描述 一行，一个整数，表示选取的彩带的最大长度。 示例输入 8 3 1 2 3 2 1 4 5 1 输出 5 说明：最长的一段彩带是 [1, 2, 3, 2, 1]，共 5 厘米。 思路哈希表+滑动窗口。使用哈希表来统计每个数出现次数；当窗口内的颜色的数量超过K的时候，滑动左指针。 代码 N, K = map(int, input().split()) c = list(map(int, input().split())) ans = 0 d = {} left = 0 for right in range(N): if c[right] not in d: d[c[right]] = 1 else: d[c[right]] += 1 while left < right and len(d) > K: d[c[left]] -= 1 if d[c[left]] == 0: del d[c[left]] left += 1 ans = max(ans, right - left + 1) print(ans) 回文串 描述现在小美获得了一个字符串。小美想要使得这个字符串是回文串。 小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符 'a'-'z'。 你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。数据保证能在题目限制下形成回文字符串。 注：回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。例如字符串 abcba, aaaa 剩余60%内容，订阅专栏后可继续查看/也可单篇购买 一个普通数据人的成长之路 文章被收录于专栏记录实习和校招的笔试面试（标题年份表示笔试或面试的年份）和个人成长，牛友们的点赞、评论、收藏就是更新的动力和支持~ 提示 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |