08 15 美团 笔试 测试开发

分析

4道编程。还有一道问答题，关于快速体现功能进行等价类划分的题，设计测试用例。

1

判断逆序数，该逆序定义为：原值乘以四得到逆序值。

• 暴力怼，不知道漏了什么，AC 0.91

N = int(input())

res = []
for i in range(1099,(N+1)//4):
    inv = int(str(i)[::-1])
    if i*4 == inv:
        res.append([i,inv])
res.sort(key = lambda x:x[0])
print(len(res))
for i in range(len(res)):
    print("{} {}".format(res[i][0],res[i][1]))

2.

根据之前的买票记录计算总共有多少次旅程。每次旅程出发城市和回归的城市一样，且记录按时间排序。

• 也是暴力怼，只AC了0.55

N = int(input())

records = []
for _ in range(N):
    start,end = input().split()
    records.append([start,end])

cnt = 0
inCircle = False
start_position = None
for s,e in records:
    if not inCircle:
        start_position = s
        inCircle = True

    else:
        if e == start_position:
            inCircle = False
            cnt += 1
            start_position = None
print(cnt)

3

根据图的连接关系，判断哪几个结点属于同一个小区。

• 就是构造图，然后用BFS遍历，看能得到几个集合，再排序输出。 AC

N,M = list(map(int,input().split()))
m_dict = dict()
for i in range(1,N+1):
    m_dict[i] = set()

for _ in range(M):
    x,y = list(map(int,input().split()))
    if x != y:
        m_dict[x].add(y)
        m_dict[y].add(x)

visited = [0] * (N+1)
def bfs(m_dict,node,visited):
    cur_set = set()
    que = [node]
    while que:
        cur_node = que.pop(0)
        cur_set.add(cur_node)
        for to_node in m_dict[cur_node]:
            if visited[to_node] == 0:
                que.append(to_node)
                visited[to_node] = 1
    return cur_set


res = []
for key in m_dict.keys():
    if not visited[key]:
        cur_set = bfs(m_dict,key,visited)
        res.append(sorted(list(cur_set)))
res.sort()
print(len(res))
for i in range(len(res)):
    li = list(map(str,res[i]))
    print(" ".join(li))

4

调度问题。。把N个汽车中的a+b个派出去计算最大的利润。。

• 应该用DP的，最后暴力写 偷了18%的AC

N,a,b = list(map(int,input().split()))
nums = []
for _ in range(N):
    x,y = list(map(int,input().split()))
    nums.append([x,y])

nums.sort(key=lambda x:x[1])
nums.sort(key=lambda x:-x[0])

res = 0
while a:
    a -= 1
    x,y = nums.pop(0)
    res += x

nums.sort(key=lambda x:-x[1])
while b:
    b -= 1
    x,y = nums.pop(0)
    res += y

print(res)

总结

菜