网站建设中幻灯片如何加链接电商运营工资大概多少

问题描述

小R正在研究DNA序列，他需要一个函数来计算将一个受损DNA序列（dna1）转换成一个未受损序列（dna2）所需的最少编辑步骤。编辑步骤包括：增加一个碱基、删除一个碱基或替换一个碱基。

测试样例

样例1：
输入：dna1 = “AGT”,dna2 = “AGCT”
输出：1

样例2：
输入：dna1 = “AACCGGTT”,dna2 = “AACCTTGG”
输出：4

样例3：
输入：dna1 = “ACGT”,dna2 = “TGC”
输出：3

样例4：
输入：dna1 = “A”,dna2 = “T”
输出：1

样例5：
输入：dna1 = “GGGG”,dna2 = “TTTT”
输出：4

法1

我们需要计算将一个DNA序列 dna1 转换成另一个DNA序列 dna2 所需的最少编辑步骤。编辑步骤包括增加、删除或替换一个碱基。

解题思路

1. 动态规划：我们可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示将 dna1 的前 i 个字符转换成 dna2 的前 j 个字符所需的最少编辑步骤。

2. 初始化：

   • dp[0][j] 表示将空字符串转换成 dna2 的前 j 个字符，需要 j 次增加操作。
   • dp[i][0] 表示将 dna1 的前 i 个字符转换成空字符串，需要 i 次删除操作。

3. 状态转移：

   • 如果 dna1[i-1] == dna2[j-1]，则 dp[i][j] = dp[i-1][j-1]，因为不需要任何编辑操作。
   • 否则，dp[i][j] 可以通过以下三种操作之一得到：
     • 增加：dp[i][j-1] + 1
     • 删除：dp[i-1][j] + 1
     • 替换：dp[i-1][j-1] + 1
   • 取这三种操作的最小值作为 dp[i][j]。

代码

def solution(dna1, dna2):# 获取两个DNA序列的长度m, n = len(dna1), len(dna2)# 创建一个 (m+1) x (n+1) 的二维数组 dpdp = [[0] * (n + 1) for _ in range(m + 1)]# 初始化 dp 数组的第一行和第一列for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = j# 填充 dp 数组for i in range(1, m + 1):for j in range(1, n + 1):if dna1[i - 1] == dna2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1# 返回最终结果return dp[m][n]if __name__ == "__main__":# 你可以添加更多测试用例print(solution("AGCTTAGC", "AGCTAGCT") == 2)print(solution("AGCCGAGC", "GCTAGCT") == 4)

关键步骤解释

1. 初始化：dp[i][0] 和 dp[0][j] 分别表示将 dna1 的前 i 个字符转换成空字符串，以及将空字符串转换成 dna2 的前 j 个字符。
2. 状态转移：根据 dna1[i-1] 和 dna2[j-1] 是否相等，选择不同的编辑操作，并取最小值。

法2

综合运用了动态规划（Dynamic Programming）和字符串处理的知识，是一道典型的编辑距离（Edit Distance）问题。题目要求计算将一个受损DNA序列（dna1）转换成一个未受损序列（dna2）所需的最少编辑步骤。编辑步骤包括增加一个碱基、删除一个碱基或替换一个碱基。这是一个典型的编辑距离问题，可以通过动态规划来解决。动态规划的核心思想是将问题分解为子问题，并通过状态转移方程逐步求解。

解题思路

1. 初始化：

   • 创建一个二维数组 f，大小为 (n+1) x (m+1)，其中 n 和 m 分别是 dna1 和 dna2 的长度。f[i][j] 表示将 dna1 的前 i 个字符转换为 dna2 的前 j 个字符所需的最少编辑步骤。
   • 初始化边界条件：f[i][0] = i 表示将 dna1 的前 i 个字符转换为空字符串需要 i 次删除操作；f[0][j] = j 表示将空字符串转换为 dna2 的前 j 个字符需要 j 次插入操作。

2. 状态转移：

   • 对于每个 i 和 j，计算 f[i][j]：
     • 如果 dna1[i-1] == dna2[j-1]，则不需要进行替换操作，f[i][j] = f[i-1][j-1]。
     • 否则，f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1] + 1)，分别对应删除、插入和替换操作。

3. 结果：

   • 最终结果为 f[n][m]，即 dna1 转换为 dna2 所需的最少编辑步骤。

• 时间复杂度：$O(n\times m)$，其中 n 和 m 分别是 dna1 和 dna2 的长度。需要填充一个 (n+1) x (m+1) 的二维数组。
• 空间复杂度：$O(n\times m)$，用于存储动态规划表 f。

代码

def solution(dna1: str, dna2: str) -> int:n = len(dna1)m = len(dna2)if n * m == 0:return n + mf = [[0] * (m + 1) for _ in range(n + 1)]for i in range(n + 1):f[i][0] = ifor j in range(m + 1):f[0][j] = jfor i in range(1, n + 1):for j in range(1, m + 1):f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + (dna1[i - 1] != dna2[j - 1]))return f[n][m]if __name__ == '__main__':print(solution(dna1 = "AGT",dna2 = "AGCT") == 1)print(solution(dna1 = "AACCGGTT",dna2 = "AACCTTGG") == 4)print(solution(dna1 = "ACGT",dna2 = "TGC") == 3)print(solution(dna1 = "A",dna2 = "T") == 1)print(solution(dna1 = "GGGG",dna2 = "TTTT") == 4)