美团机器学习笔试题交流

''' 10 2 1 0 0 1 0 1 0 1 0 1 ''' # 思路：确定填充每相邻K个0得到的总长度 N, K = [int(i) for i in input().strip().split()] temp_list = [int(i) for i in input().strip().split()] dp = [0] for i in range(N): if temp_list[i] == 0: dp.append(i + 1) dp.append(N + 1) # 遍历得到最大长度 max_len = 0 for i in range(K + 1, len(dp)): max_len = max(max_len, dp[i] - dp[i - K - 1] - 1) print(max_len)

def minPathLen(n, B):#     node_list = [0]*100000#     for i in range(len(B)):         b = B[i]         x = b[0]         y = b[1]         node_list[y] = node_list[x] + 1     #print(node_list)     depth = 0     for i in range(1,n+1):         if node_list[i] > depth:             depth = node_list[i]         else:             depth = depth     minPath_length = 2*n-2-depth     return minPath_length if __name__ == '__main__':     n = int(raw_input())     B=[]     for i in range(n-1):         A = [i for i in raw_input().split()]         A = map(int, A)         B.append(A)     #print(n,B)     result = minPathLen(n, B)     print(result)

同求

def min_path(n, B): node_list = [0] * (n + 1) # 保存节点的距离 for path in B: # 遍历路径，使后一节点距离值等于前一节点距离值加一 x, y = path node_list[y] = node_list[x] + 1 depth = 0 # 找到最大深度 for i in range(1, n + 1): if node_list[i] > depth: depth = node_list[i] # 计算最短路径,即最深的路径走一遍，其他路径走2遍 return 2 * n - 2 - depth if __name__ == '__main__': n = int(input().strip()) B = [] # 得到路径列表 for i in range(n - 1): A = [int(i) for i in input().strip().split()] if A[0] > A[1]: A[0], A[1] = A[1], A[0] # 使得第一个元素小于第二个元素 B.append(A) B.sort(key=lambda x: x[0]) # 按第一个元素排序 result = min_path(n, B) print(result)