携程3.18日算法笔试
1. 给n个点（0到n-1）和n-1条有方向的路径，要求最终在0位置集合，需要修改多少条路径的方向
n,l = input().split()
n=int(n)
l = l.replace('[','')
l = l.replace(']','')
nums = [int(i) for i in l.split(',')]
linjiebiao = [[] for i in range(n)]
paths = [[] for i in range(n)]
for i in range(n-1):
a, b = nums[2*i], nums[2*i+1]
linjiebiao[a].append(b)
linjiebiao[b].append(a)1 2 3 4<trip>5 10 5 7
paths[a].append(b)
ans = 0
def dfs(i):
global ans
visited.append(i)
for to in linjiebiao[i]:
if to not in visited:
if i not in paths[to]:
ans+=1
dfs(to)
visited = []
dfs(0)
print(ans)
2. 计算自注意力机制的结果
import numpy as np
def softmax(x):
x_row_max = x.max(axis=-1)
x_row_max = x_row_max.reshape(list(x.shape)[:-1]+[1])
x = x - x_row_max
x_exp = np.exp(x)
x_exp_row_sum = x_exp.sum(axis=-1).reshape(list(x.shape)[:-1]+[1])
softmax = x_exp / x_exp_row_sum
return softmax
nums = [list(map(int,line.split())) for line in input().split('<trip>')]
d = int(input())
inputs = np.array((nums))
Q, K, V = np.ones((inputs.shape[1],d))*0.5,np.ones((inputs.shape[1],d))*0.5,np.ones((inputs.shape[1],d))*0.5
query, key, value = np.matmul(inputs, Q), np.matmul(inputs, K), np.matmul(inputs, V)
tmp = np.matmul(key, query.transpose())
tmp = softmax(tmp)
out = np.matmul(tmp, value)
out = out*np.sqrt(inputs.shape[1])#len(inputs)
for i in range(len(nums)-1):
for j in range(d):
if j==d-1:
print("%.2f" % out[i][j], end='<trip>')
else: print("%.2f" % out[i][j], end=' ')
for j in range(d):
if j==d-1:
print("%.2f" % out[len(nums)-1][j])
else: print("%.2f" % out[len(nums)-1][j], end=' ')
