【携程】开发笔试暑期实习春招题解0329

携程第二次笔试，后端算法前端都要做的题，有帮助欢迎点赞评论哦~

T1 计算圆圈个数 直接计数即可。参考代码如下：

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
	print(n.count('0')+n.count('6')+n.count('9')+2*n.count('8'))

T2 排列构造，需要K个好元素。只需要选择0, 2, 4,..., 2*(k-1)下标的地方依次填入n-k+1, n-k+2, ... ,n，也就是倒数k大的数，剩下的地方把剩下的地方填写即可。参考代码如下：

import sys
if __name__ == "__main__":
	n, k = map(int, sys.stdin.readline().strip().split())
	ans = [0]*n
	for i in range(k):
	ans[i+2] = n-k+i+1;
	if i*2+1<n:
	  ans[i*2+1] = i+1
	for i in range(2*k, n):
	  ans[i] = i-k+1
	for a in ans:
	  print(a, end = "")

T3 x的阶乘范围决定了x不会超过15，枚举x，然后y取n/x和(n/x)+1计算哪个绝对值小即可。注意x和y不能取2，但可能取1。提交时感觉有个样例bug，x取1时按理说y直接消了取多少都可以，但是取n不通过，取1就通过了。参考代码如下：

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
	facts = [6]
	for i in range(4, 15):
	  facts.append(facts[-1]*i)
	  minAbs, minX, minY = n, 1, 1
	  for i in range(len(facts)):
		curY = n//facts[i]
		if abs(curY*facts[i]-n)<minAbs and curY!=2:
		  minAbs, minX, minY = abs(curY*facts[i]-n), i+3, curY
		if abs((curY+1)*facts[i]-n)<minAbs and curY+1!=2:
		  minAbs, minX, minY = abs(curY*facts[i]-n), i+3, curY+1
	print(minX, minY)

T4 树形DP，直接DFS，计算孩子允许染色和不允许染色的情况，返回两个状态：一个是不允许自己和孩子之间染色，一个是允许，两种情况下的权值。允许自己和孩子之间染色这个状态即drawAns的计算需要注意一下，应该选择与哪一个孩子染色呢？应当对每一个孩子考虑，“选择与它染色得到的最大权值”和“不选择与它染色”得到的最大权值之差，即代码中的drawDiff，这个差最大的就是染色对权值贡献最大的孩子，我们选择与它染色。参考代码如下：   

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    G = [[] for i in range(n)]
    for i in range(n-1):
        line = sys.stdin.readline().strip()
        u, v, w = list(map(int, line.split()))
        G[u-1].append([v-1, w])
        G[v-1].append([u-1, w])
    flag = [False]*n
    start = -1
    for i in range(n):
        if len(G[i])==1:
            start = i
            break
    flag[start] = True
    def dfs(node):
        draw, nodraw, drawed = [], [], []   # 存储孩子状态
        for nei, W in G[node]:
            if not flag[nei]:
                flag[nei] = True
                neiNoDraw, neiDraw = dfs(nei)
                nodraw.append(neiNoDraw)
                draw.append(neiDraw)
                drawed.append(W + neiNoDraw)
        if draw:   # 如果不是叶子
            noDrawAns = sum(map(max, zip(draw, nodraw)))   # 不跟孩子之间染色，取孩子所有状态最大值
            drawDiff = [drawed[i] - draw[i] for i in range(len(draw))]  # 假设分别与每个孩子之间染色，比不染多出的权值
            maxDiffIndex = drawDiff.index(max(drawDiff))  # 多出权值最大的孩子
            drawAns = max(noDrawAns, drawed[maxDiffIndex]+sum(draw)-draw[maxDiffIndex])  # 能跟孩子之间染色情况下的最大权值
            return noDrawAns, drawAns
        return 0, 0
    print(max(dfs(start)))