09-06美团机器学习编程题思路

第一题：图的遍历

• 思路：假设最后需要回归根节点，那么无论怎么遍历，每条边都会被访问两次，总路程总是2(n-1)；如果只需要遍历所有节点，则访问完最后一个叶子节点无需返回，要是总路程最小，那么最终访问的叶子节点应该距离根节点最远；如果树的最大深度为h，那么总路程最少需要2(n-1)-h。
• 代码：BFS计算树的最大深度，时间复杂度O(V+E)=O(n)

from collections import defaultdict
n = input()
adj = defaultdict(list)
for i in xrange(n-1):
    x,y = map(int, raw_input().split())
    adj[x-1].append(y-1)
    adj[y-1].append(x-1)
level = -1
color = [0] * n
color[0] = 1
q = [0]
while q:
    level += 1
    qq = []
    for pre in q:
        for pre_adj in adj[pre]:
            if color[pre_adj] == 0:
                color[pre_adj] = 1
                qq.append(pre_adj)
    q = qq
print 2 * (n-1) - level

第二题：最长全1串

• 思路：动态规划，设dp[i][k]表示以下标i结尾且最多变换k次的最长1串长度，最终最大长度=max(dp[i][K]),i=0,1,...,n-1；时间复杂度O(kn)，状态转移方程可以写作：

dp[i][k] = dp[i-1][k]+1; 如果s[i] == '1'， i > 0
dp[i][k] = dp[i-1][k-1] + 1; 如果s[i] =='0'，i > 0, k > 0
dp[i][k] = [k!=0 or s[i]=='1']； 如果i == 0
dp[i][k] = dp[i-1][k] + 1;如果s[i] == '1',k = 0，i > 0
dp[i][k] = 0；如果s[i] == '0', k = 0

• 改进：考虑dp[i][k]只与当前层和上一层有关，可以用滚动数组将空间复杂度减少至O(n)
• 代码：

N, K = map(int, raw_input().split())
s = ''.join(raw_input().split())
dp = [-1] * N
for k in xrange(K+1):
    tmp = [k!=0 or s[0]=='1'] * N
    for i in xrange(1,N):
        tmp[i] = tmp[i-1] + 1 if s[i] == '1' else dp[i-1] + 1
    dp = tmp
print max(dp)

仅为个人思路，第二题使用二维DP，超出内存限制，未验证滚动数组解法是否可以AC。