面试：2022 春招实习美团面试题目

昨天做了美团的一套题目，把题目记录了一下。分享出来，并且把自己编的思路和过程也写出来，当然应该会有错误，如果有错误，可以直接评论给我提出来。或者如果有自己的思路，希望可以给我分享一下，学习学习。

第一题：汉明距离之和

小美有两个 01 串 s, t。她想求 s 和 t 的所有长度等于 ∣s∣|s|∣s∣ 子串（连续）的汉明距离的和。即，她想知道汉明距离 Ham(ti,s)\text{Ham}(t_i , s)Ham(ti​,s)，其中 tit_iti​ 指第 iii 个字符开始的长度为 ∣s∣|s|∣s∣ 的子串。对于等长 01 串 a, b， 他们之间汉明距离的定义是：

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

输入：对于每一组数据，包含两行数据，第一行是 s，第二行是 t；1≤∣s∣≤∣t∣≤500001\le|s|\le|t|\le500001≤∣s∣≤∣t∣≤50000.

输出：输出一个整数，表示汉明距离之和

样例输入：
01
00111

样例输出：
3

我自己的思路：哈希表

• 首先用一个滑动窗口，长度为 s 的长度，遍历整个字符串 t；
• 使用一个哈希表，key 为滑动窗口中的子串，value 为子串在 t 中出现的次数，遍历完整个 ttt 字符串；
• 将哈希表中的每个 key 与 s 计算汉明距离，乘以出现的次数，并且加起来就可以得到结果；

def distance(t, s):  # 汉明距离
    n = len(s)
    ans = 0
    for i in range(n):
        if t[i] != s[i]:
            ans += 1
    return ans

while True:
    try:
        s = input()
        t = input()
        ns, nt = len(s), len(t)  # 获得两个字符串的长度
        cntHash = dict()   # 记录不同类型子串的数量的哈希表
        l, r = 0, ns  # 滑动窗口去记录所有的子串数量
        while r <= nt:
            subStr = t[l:r]  # 获得当前子串
            if subStr not in cntHash:
                cntHash[subStr] = 1
            else:  # 如果子串在 哈希表 中
                cntHash[subStr] += 1
            l += 1  # 窗口往后移一格
            r += 1
        distSum = 0  # 汉明距离的和
        # 计算子串之间汉明距离之和
        for ti in cntHash.keys():
            distSum += cntHash[ti] * distance(ti, s)
        print(distSum)
    except: break

第二题：菱形图

菱形是一类非常优美的图形：其对边对称，四条边长度相等。例如正方形就是一类特殊的菱形。对于图论而言，菱形图是指一个无向图形成的环，满足点数大于等于 4，其中可以找到四个不相同的点 a,b,c,d，使得 a => b，b => c，c => d，d => a 的距离都相等。

小美刚刚学完图论。她随手造了一张 n 个点 m 条无向边的图（不含重边和自环，保证连通，即任意两个点都互相可达），她想知道这张图是不是菱形图。（默认两点之间的距离为 1）

输入：第一行一个正整数 T，表示有 T 组数据。

对于每一组数据，第一行两个正整数 n, m，表示无向图的点数和边数；

第二行 m 个正整数 u_i；第三行 m 个正整数 v_i，表示 u_i 与 v_i 之间有一条无向边。

数据保证无重边和自环且图连通。数字间两两有空格隔开。

4≤n≤m≤104，1≤ui,vi≤n，1≤T≤84\le n\le m\le 10^4 ，1\le u_i,vi\le n ，1\le T\le 84≤n≤m≤104，1≤ui​,vi≤n，1≤T≤8

输出：对于每一组数据，如果其是菱形图，输出一行 Yes；否则，输出一行 No。

样例输入：
3
8 8
1 3 7 8 5 6 2 4
3 7 8 5 6 2 4 1
9 9
1 3 7 8 5 6 2 4 3
3 7 8 5 6 2 4 1 9
7 7
1 5 6 7 3 4 2
5 6 7 3 4 2 1


样例输出：
Yes
No
No

这道题没有做出来。

第三题：大米仓库

小美的家乡遇到了特大暴雨。为此她建立了一个救援的大米仓库。有货车运来或取走大米。现在有一列车队，每个车都要运来或取走一定的大米。假设小美的仓库最开始有 M 千克大米，它会在某辆车路过时打开仓库，这样这辆车以及后面的车辆都可以进入仓库运来或取走大米。如果有一辆车取不到本想取到的大米，小美会提前关闭仓库，这辆车以及后面的车辆都不再能进入仓库。（即小美的仓库会对车队的一个连续子串开放，且保证仓库内的大米不为负值）

请问小美的仓库最多有多少辆车进入。

输入：对于每一组数据，包含两行数据，第一行是车队的车辆数 n 和小美仓库本有的大米 m，第二行是车队想取走（负值）或运来（正值）的大米 aia_iai​，数字间两两有空格隔开。

1≤n≤50000，−109≤ai≤109，0≤m≤1091\le n \le 50000， -10^9\le a_i\le10^9，0\le m\le 10^91≤n≤50000，−109≤ai​≤109，0≤m≤109

输出：输出一个整数，表示最多有多少辆车进入（最长连续子串）。

样例输入：
4 10
-16 2 -6 8

样例输出：
3

我的思路：

• 用两个变量，模拟一辆一辆车进入，rest 记录当前仓库的剩余（初始值为 m），maxCar 记录当前已经进入过仓库的车辆，从头遍历数组 a ，下一辆车进入会出现一下三种情况：
  • 仓库的剩余还是不为负数，即 rest + a[i] >= 0，那么让 maxCar := maxCar + 1；
  • 如果当前的仓库剩余不够下一辆车来取，即 rest + a[i] < 0，那么从当前位置开始前面的车辆都不能让它进，这个时候有两种情况：
    • 如果当前准备进入仓库的这辆车想要取的大米数量小于等于仓库初始量，即 m + a[i] >= 0，那么这辆车可以进入，令 rest = m + a[i]，maxCar = 1；
    • 否则，这辆车想要取的大米数量大于仓库初始量，即 m + a[i] < 0，那么就不能让它进来，跳过这辆车并且 rest = m, maxCar = 0，从头开始；

while True:
    try:
        n, m = map(int, input().split())  # 第一行：车队数量，仓库大米存量
        a = list(map(int, input().split()))  # 车队预计要运输的大米
        n = len(a)
        maxCar = 0  # 
        rest = m
        for i in range(n):
            rest += a[i]
            if rest >= 0:
                maxCar += 1
            elif m + a[i] >= 0:
                rest = m + a[i]
                maxCar = 1
            else:
                rest = m
                maxCar = 0
        print(maxCar)
    except: break

第四题：买果汁

小美的班上要组织班级聚会啦！老师交给小美一个任务：去给聚会采购果汁饮料。

小美来到超市，发现超市里面一共有 n 种不同的果汁饮料，种类标记为 1,2,3,…,n1,2,3,\dots,n1,2,3,…,n，每一种饮料都有一个美味度 aia_iai​。aia_iai​ 越大，说明饮料越好喝。但是，由于有些果汁饮料味道可能很奇怪，于是 aia_iai​ 有可能小于等于 0。

由于不知道每个同学的口味，每一种饮料小美都恰好买了一瓶。这时，小美在思考：能不能找到这样一对 l, r 满足 1≤l≤r≤n1\le l\le r \le n1≤l≤r≤n，且不满足 [l,r]=[1,n][l,r]=[1,n][l,r]=[1,n]（即全选），使得 [l,r][l,r][l,r] 将这个种类内的饮料各买一瓶，其美味度之和大于等于每一种饮料都买一瓶的美味度之和？

输入：第一行一个正整数 T，表示有 T 组数据。

对于每一组数据，第一行一个正整数 n；第二行 n 个整数 a1,a2,…,ana_1,a_2,\dots ,a_na1​,a2​,…,an​。

1≤T≤5,3≤n≤5×104,−100≤ai≤1001\le T\le 5, 3\le n\le 5\times 10^4, -100\le a_i\le 1001≤T≤5,3≤n≤5×104,−100≤ai​≤100

输出：对于每一组数据，如果找得到这样的，输出 Yes；否则，输出 No。

样例
2
4
1 2 3 4
3
-5 5 -5

答案
No
Yes

我的思路：

• 对 a 进行从左往右累加和从右往左累加
• 然后只要出现了负数或者为 0，就代表存在题目描述的这样一种买法

T = int(input())  # 有 T 组数据
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    s = 0
    res = "No"
    for i in range(n):
        s += a[i]
        if s <= 0:
            res = "Yes"
            break
    s = 0
    if res == "No":
        for i in range(n-1, -1, -1):
            s += a[i]
            if s <= 0:
                res = "Yes"
                break
    print(res)