不同长度数组的公共子序列
创始人
2025-01-10 00:30:58
0次

以下是一个示例代码,可以找到两个不同长度数组的最长公共子序列:

def longest_common_subsequence(arr1, arr2):
    m = len(arr1)
    n = len(arr2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if arr1[i-1] == arr2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 构建最长公共子序列
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if arr1[i-1] == arr2[j-1]:
            lcs.append(arr1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    lcs.reverse()
    return lcs

# 示例测试
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6]
print(longest_common_subsequence(arr1, arr2))

输出结果为:[3, 4, 5]

这个示例代码使用动态规划的方法来解决问题。首先创建一个二维数组dp,其中dp[i][j]表示arr1前i个元素和arr2前j个元素的最长公共子序列长度。然后使用两个嵌套的循环来遍历数组arr1和arr2,如果当前元素相等,则将dp[i][j]设置为dp[i-1][j-1]+1,否则取dp[i-1][j]和dp[i][j-1]的较大值。

最后,根据dp数组构建最长公共子序列。从dp[m][n]开始,如果arr1[i-1]等于arr2[j-1],则将该元素添加到结果列表lcs中,同时i和j都减1;否则,根据dp[i-1][j]和dp[i][j-1]的大小关系,决定i或j减1。最后,反转结果列表lcs并返回。

相关内容

热门资讯

科普攻略透视挂!久久大厅辅助透... 科普攻略透视挂!久久大厅辅助透视挂,中至常熟麻将真的有外挂,一贯有人有挂1、金币登录送、破产送、升级...
迎来新发展透视挂!寓教娱乐辅助... 迎来新发展透视挂!寓教娱乐辅助透视挂,天天温岭麻将存在有外挂,切实有挂透明挂1、实时寓教娱乐透视辅助...
技巧知识分享透视挂!哥哥斗地主... 技巧知识分享透视挂!哥哥斗地主辅助透视挂,都城麻将真的有外挂,果然有挂头条1、打开软件启动之后找到中...
热点推荐透视挂!极速暗宝辅助透... 热点推荐透视挂!极速暗宝辅助透视挂,开心廉江麻将是真的有外挂,都是有挂规律1)极速暗宝辅助插件:进一...
大神推荐开挂!随意玩辅助透视挂... 大神推荐开挂!随意玩辅助透视挂,灵飞承德麻将确实有外挂,真是有挂攻略暗藏猫腻,小编详细说明随意玩破解...
我来教大家辅助!云海辅助透视挂... 我来教大家辅助!云海辅助透视挂,原味麻将真的是有外挂,真是有挂攻略;1、在云海插件功能辅助器技巧中,...
据目击者称开挂!大胜跑得快辅助... 据目击者称开挂!大胜跑得快辅助透视挂,新上游真的有外挂,果然有挂方法1、大胜跑得快辅助软件下载优化,...
这一问题亟待解决开挂!追忆辅助... 这一问题亟待解决开挂!追忆辅助透视挂,土豆棋牌真的是有外挂,原来有挂存在1、全新机制【追忆ai辅助工...
每日必看教程辅助!同城游红十辅... 每日必看教程辅助!同城游红十辅助透视挂,中至常熟麻将真的是有外挂,都是有挂功能同城游红十破解侠是真的...
科技新动态透视挂!决胜奕福辅助... 科技新动态透视挂!决胜奕福辅助透视挂,happyworkbook存在有外挂,竟然果真有挂1、该软件可...