不同长度数组的公共子序列
创始人
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并返回。

相关内容

热门资讯

事发当天!上饶辅助设备出租,真... 事发当天!上饶辅助设备出租,真是是真的辅助工具(有挂头条)-哔哩哔哩上饶辅助设备出租脚本下载中分为三...
随着!菠萝神辅助器app,一直... 随着!菠萝神辅助器app,一直是有辅助平台(有挂教程)-哔哩哔哩1、很好的工具软件,可以解锁游戏的菠...
推出新举措!兴动海满辅助,一贯... 您好,兴动海满辅助这款游戏可以开挂的,确实是有挂的,需要了解加去威信【136704302】很多玩家在...
做出回应!微乐贵阳捉鸡麻将挂软... 做出回应!微乐贵阳捉鸡麻将挂软件,果然真的是有辅助神器(有挂秘诀)-哔哩哔哩1、打开软件启动之后找到...
反观!九游破解辅助插件,都是真... 反观!九游破解辅助插件,都是真的有辅助神器(有挂秘籍)-哔哩哔哩九游破解辅助插件能透视中分为三种模型...
据文件显示!科米台州麻将辅助,... 据文件显示!科米台州麻将辅助,真是有挂辅助app(竟然有挂)-哔哩哔哩1、每一步都需要思考,不同水平...
今天上午!赣湘互娱挂,总是是有... 今天上午!赣湘互娱挂,总是是有辅助修改器(有挂详情)-哔哩哔哩1、在赣湘互娱挂插件功能辅助器技巧中,...
来临!广西友乐解码器辅助器,原... 来临!广西友乐解码器辅助器,原来真的是有辅助脚本(真的有挂)-哔哩哔哩1.广西友乐解码器辅助器 选牌...
来临!新天道辅助脚本,确实有挂... 来临!新天道辅助脚本,确实有挂辅助下载(有挂秘诀)-哔哩哔哩1、金币登录送、破产送、升级送、活动送。...
近期!青橙竞技卡五星辅助,好像... 近期!青橙竞技卡五星辅助,好像真的是有辅助脚本(竟然有挂)-哔哩哔哩1、用户打开应用后不用登录就可以...