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)