【Python】2021校招腾讯数分笔试题

Q1：合法括号问题

图片说明

思路：
该题是典型的动态规划题目。利用dp[i][j]表示i位置开始j位置结束的字符串所需要添加的最少括号数。

所有单个字符的字符串所需要的最少括号数都为1，即dp[i][i]=1.
由下至上更新动态数组dp，即先更新长度为2的字符串所需要的最少括号数，然后是3、4......：
2-1. 当头尾是匹配的括号时，所有添加的最少括号数和去掉头尾之后所需要的最少括号数一致，即dp[i][j]=dp[i+1][j-1]；注意当字符串长度为2时，这里需要特殊处理。
2-2. 否则，将字符串拆成两部分，分别求这两部分所需要的最少括号数之和，然后遍历所有和中的最小值。
输出整个字符串所需要的最少括号数。

s = input()
n = len(s)
dp = [[float('inf') for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = 1

for l in range(1, n):
    for i in range(n-l):
        j = i + l
        if (s[i]=='(' and s[j]==')') or (s[i]=='[' and s[j]==']'):
            if l == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j-1]
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
print(dp[0][n-1])

Q2：定积分求面积问题

图片说明
坑：
注意输出的格式。

Q3：队长问题

图片说明
思路：

从n个人中选k个人，共C(n,k)种；从k个人中选一个当队长，共k种。因此一共由k*C(n,k)种。
正写：ans = 0 * C(n,0) + 1 * C(n,1) + ... + n * C(n, n)
反写：ans = n * C(n,n) + (n-1) * C(n,1) + ... + n * C(n, n) = n * C(n,0) + (n-1) * C(n,1) + ... + 0 * C(n, n)，两者相加，得到ans。

n = int(input())
print(n*2**(n-1))

Q4：图价值问题

图片说明

思路：
找到所有节点的相邻节点集合，对这些集合进行计数，然后求满足条件的节点对个数即可。
难点在于，集合不能哈希，不能作为key，因此要转成tuple。

from collections import Counter
n, m = 4, 3
M = [(1,2),
     (2,3),
     (2,4)]
ans = 0
# 存储相邻节点(i索引代表i+1节点)
neibors = [set() for _ in range(n)]
for x in M:
    neibors[x[0]-1].add(x[1]-1)
    neibors[x[1]-1].add(x[0]-1)
# 将set转换成tuple，才可以计数
neibors = [tuple(x) for x in neibors]
cnt = Counter(neibors)
for k in cnt.keys():
    if cnt[k] != 1:
        ans += int(cnt[k]*(cnt[k]-1)/2)
print(ans)

Q5：最短路径问题

图片说明

思路：
直接套用最短路径的dijkstra算法求解。注意将无向边看成两条有向边，将传送门看成权重为0的有向边。

def add_edge(v1, v2, w):
    '''添加有向边'''
    G[v1][v2] = w

def dijkstra(start, end, G):
    '''
        @param start：起始节点
        @param end：结束节点
        @param G：图
        @return：最短路径的距离
    '''
    # 分别记录已观察和未观察的节点
    visited = [start]
    non_visited = [x for x in range(len(G)) if x!=start]
    # 用于存储start节点到其余节点的最短距离
    dist = G[start]

    while len(non_visited): # 直到所有点都被观察后结束
        # 在未观察的节点中，找出距离该节点最近的节点
        idx = non_visited[0]
        for i in non_visited:
            if dist[i] < dist[idx]:
                idx = i
        non_visited.remove(idx)
        visited.append(idx)
        # 更新剩余未观察节点的最短距离
        for i in non_visited:
            if dist[idx]+G[idx][i] < dist[i]:
                dist[i] = dist[idx]+G[idx][i]
    return dist[end]

if __name__ == "__main__":
    inf = 10086
    n, m, k = 5, 3, 2
    G = [[inf for _ in range(n)]for _ in range(n)]
    M = [(1,2,1), 
         (2,3,1), 
         (3,4,1)]
    K = [(4,5),
         (1,2)]
    # 无向边，因此添加两个方向
    for i in range(m):
        add_edge(M[i][0]-1, M[i][1]-1, M[i][2])
        add_edge(M[i][1]-1, M[i][0]-1, M[i][2])
    # 传送门为单向
    for i in range(k):
        add_edge(K[i][0]-1, K[i][1]-1, 0)

    ans = dijkstra(0, 5, G)
    print(ans)