1.有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
这是经典的 LCS 问题，如果用常规遍历解法，时间复杂度是 O(m*n)，如果采用动态规划策略，时间复杂度是 O(mlogn)。
设 C[i,j]C[i,j]表示 XiXi 和 YjYj 的最长公共子序列 LCS 的长度。如果 i=0i=0 或 j=0j=0,即一个序列长度为 00 时，那么 LCS 的长度为 0。根据 LCS 问题的最优子结构性质，动态规划状态转移方程式为：
代码实现为：
def lcs(X, Y): # find the length of the strings m = len(X) n = len(Y)
# declaring the array for storing the dp values L = [[None] * (n + 1) for i in range(m + 1)]
"""Following steps build L[m + 1][n + 1] in bottom up fashion Note: L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]""" for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: L[i][j] = 0 elif X[i - 1] == Y[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1])
# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] return L[m][n]
if __name__ == '__main__': print(lcs('abxyz','defxyz'))
复制代码
结果为 3，如果结果大于 0，说存在公共子串，也就是合并。
2.请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
评论