黄圣杰

bjfuhsj.top

445.两数相加(顺) II && 002(逆)

发表于 分类于 阅读次数：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

1.最长公共子序列：

最长公共子序列(LCS):Longest Common Subsequence

  • 对于两个子序列 S1 和 S2，找出它们最长的公共子序列。

  • 定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况：

  1. 当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
  2. 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。
  3. 综上，最长公共子序列的状态转移方程为：

4c4ff66ed0decdde711678563728e0cf_ecd89a22-c075-4716-8423-e0ba89230e9a.jpg

  • 对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。

作者：bryank-3
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/jian-dan-yi-dong-zui-chang-gong-gong-zi-xu-lie-by-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
              dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
              dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n1][n2];
}

3.几种解法：

  1. 暴力递归（不用DP Table）

  • 是 从后往前 比较计数的；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestCommonSubsequence(str1, str2) -> int:
    def dp(i, j):
        # 空串的 base case
        if i == -1 or j == -1:
            return 0
        if str1[i] == str2[j]:
            # 这边找到一个 lcs 的元素，继续往前找
            return dp(i - 1, j - 1) + 1
        else:
            # 谁能让 lcs 最长，就听谁的
            return max(dp(i-1, j), dp(i, j-1))
        
    # i 和 j 初始化为最后一个索引
    return dp(len(str1)-1, len(str2)-1)

2. 法二，借用DP Table来记录（也可用备忘录）

  • 双层遍历：
  • 判断：当前两个字符一样吗？
    • 一样：左斜上角空格数字（dp[i-1][i-1]） 加1;
    • 不一样：比较 上 && 下 的最大值，取大的那一个来填充当前dp[ i ][ j ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestCommonSubsequence(str1, str2) -> int:
    m, n = len(str1), len(str2)
    # 构建 DP table 和 base case
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 进行状态转移
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                # 找到一个 lcs 中的字符
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
    return dp[-1][-1]

3. 优化：用动态数组（一维数组）来解决：

  1. 在利用二维dp数组记录dp[ i ][ j ]时，需要用到dp[ i-1 ][ j-1 ] (左上方),dp[ i-1 ][ j ] (上边),dp[ i ][ j-1 ] (左边)。
  2. 优化为滚动数组记录dp[ j ] (dp[ i ][ j ]) 时，dp[ j-1 ] ( i-1 ) 已被更新为dp[ j-1 ]（ i ），所以需定义变量last去记录未被更新前的dp[ j-1 ]（ i-1 ）;
  3. 所以计算dp[j]的当前值时，会用到last（dp[ i-1 ][ j-1 ]）、dp[ j ] (dp[ i-1 ][ j ])和dp[ j-1 ] (dp[ i ][ j-1 ]);
    注意：计算每一行的第一个元素时候，last需要初始化为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size(),m=text2.size();
				int dp[m+1],last=0,temp;
				fill(dp,dp+m+1,0);//fill(数组名，起始地【包括】，结束地【不包括】，填充值)
        for(int i=1;i<=n;++i,last=0){
						for(int j=1;j<=m;++j){
            	    temp=dp[j];
		   						if(text1[i-1]==text2[j-1])	dp[j]=last+1; 
		   						else	 dp[j]=max(dp[j],dp[j-1]);
        	  			last=temp;
						}
        }
	return dp[m];
    }
};
  • 画一下流程图你就懂了，顺着 DP Table，按着上面的代码（一维数组）推一遍：
    1. 先用 temp 保存当前节点，然后更新当前节点；
    2. 其中更新的时候，有两种情况：
      1. 不相等：用 左边 （体现在一维数组的前一个位置）和 上面（体现在一维数组的当前位置）进行比较，取更大的值来刷新当前节点（体现在一维数组当前的位置）
      2. 相等：用 last + 1 ，其中 last 表征左上角（是在每一轮结束之后，把之前保存的 旧的 当前位置值 给保存下来；从二位数组角度看来，就是左上角：因为 temp 下一轮已经右移，但是 last 还在上一个位置；）
    3. 更新完当前节点位置数据之后，用 last 把当前的节点 旧的信息保存下来，last = temp，从二位数组角度看，就像是左上角数据；
    4. 然后循环1，2，3步骤
  • 注意，每一行结束更新之后，要把 last 重新归零！相当于 左上角数据从零开始重新移动（默认第零行、第零列 全为零）
  • img