devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

两个数组的动态规划——最长公共子序列模型_两个数组的最大公共子序列

作者：小丑西瓜9 | 2024-04-25 23:25:21

赞

踩

两个数组的最大公共子序列

✅ tips

1.考虑空串，即dp表多出一行一列， 代表某个字符串为空。

2.考虑最后一个位置；是否相等；

3.可在字符串最前面加虚拟位置以对应映射关系；

4.一般横行是j，列是i。此时第一行代表第二个字符串不为空，即第一个字符串是空的

1.最长公共子序列

  1. class Solution {
  2.     //dp[i][j]表s1的[0,i]以及s2的[0,j]所有子序列中最长公共子序列的长度；
  3.     //如果s[i]=s[j]，那公共序列一定是以i,j为结尾
  4.     public int longestCommonSubsequence(String s1, String s2) {
  5.         int m = s1.length(), n = s2.length();
  6.         s1 = " " + s1;
  7.         s2 = " " + s2;
  8.         int[][] dp = new int[m + 1][n + 1];
  9.         for (int i = 1; i <= m; i++) {
  10.             for (int j = 1; j <= n; j++) {
  11.                 if (s1.charAt(i) == s2.charAt(j)) {
  12.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  13.                 } else {
  14.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  15.                 }
  16.             }
  17.         }
  18.         return dp[m][n];
  19.     }
  20. }
  21. //!=时，有[0,i-1]&[0,j],[0,i-1]&[0,j-1],[0,i]&[0,j-1];空串
  1.         StringBuilder sb = new StringBuilder();
  2.         int i = m, j = n;
  3.         while (i > 0 && j > 0) {
  4.             if (s1.charAt(i) == s2.charAt(j)) {
  5.                 sb.insert(0, s1.charAt(i));
  6.                 i--;
  7.                 j--;
  8.             } else if (dp[i - 1][j] >= dp[i][j - 1]) {
  9.                 i--;
  10.             } else {
  11.                 j--;
  12.             }
  13.         }
  14.  
  15.         System.out.println( sb.toString());

 2.最长重复子数组

  1. class Solution {
  2.     public int findLength(int[] nums1, int[] nums2) {
  3.         int m=nums1.length;int n=nums2.length;
  4.         int[][] dp=new int[m+1][n+1];
  5.         int ret=0;
  6.         for(int i=1;i<=m;i++){
  7.             for(int j=1;j<=n;j++){
  8.                 if(nums1[i-1]==nums2[j-1])
  9.                     dp[i][j]=dp[i-1][j-1]+1;
  10.             
  11.             ret=Math.max(ret,dp[i][j]);
  12.             }
  13.         }
  14.         return ret;
  15.  
  16.     }
  17. }
  1. class Solution {
  2.     public int[] findLength(int[] nums1, int[] nums2) {
  3.         int m = nums1.length;
  4.         int n = nums2.length;
  5.         int[][] dp = new int[m + 1][n + 1];
  6.         int maxLength = 0;
  7.         int endIndex = 0;
  8.         
  9.         for (int i = 1; i <= m; i++) {
  10.             for (int j = 1; j <= n; j++) {
  11.                 if (nums1[i - 1] == nums2[j - 1]) {
  12.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  13.                     if (dp[i][j] > maxLength) {
  14.                         maxLength = dp[i][j];
  15.                         endIndex = i - 1; // 结束索引
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         
  21.         int[] result = new int[maxLength];
  22.         for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
  23.             result[i - (endIndex - maxLength + 1)] = nums1[i];
  24.         }
  25.         
  26.         return result;
  27.     }
  28. }
  1. class Solution {
  2.     public int[] findLength(int[] nums1, int[] nums2) {
  3.         int maxLength = 0;
  4.         int endIndex = -1;
  5.         
  6.         for (int i = 0; i < nums1.length; i++) {
  7.             for (int j = 0; j < nums2.length; j++) {
  8.                 int len = 0;
  9.                 while (i + len < nums1.length && j + len < nums2.length && nums1[i + len] == nums2[j + len]) {
  10.                     len++;
  11.                 }
  12.                 
  13.                 if (len > maxLength) {
  14.                     maxLength = len;
  15.                     endIndex = i + maxLength - 1; 
  16.                 }
  17.             }
  18.         }
  19.         
  20.         int[] result = new int[maxLength];
  21.         for (int i = endIndex - maxLength + 1; i <= endIndex; i++) {
  22.             result[i - (endIndex - maxLength + 1)] = nums1[i];
  23.         }
  24.         
  25.         return result;
  26.     }
  27. }

3.不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
  1.  
  2. 输出
：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
  1. class Solution {
  2.     //dp[i][j]在s的[0,j]的子序列中出现t的[0,i]子串的个数
  3.     //是否包含字符s[j]
  4.    public int numDistinct(String s, String t) {
  5.         int m = t.length(), n = s.length();
  6.         int[][] dp = new int[m + 1][n + 1];
  7.         for (int j = 0; j <= n; j++) {
  8.             dp[0][j] = 1;
  9.         }
  10.         for (int i = 1; i <= m; i++) {
  11.             for (int j = 1; j <= n; j++) {
  12.                 dp[i][j] = dp[i][j - 1];
  13.                 if (t.charAt(i - 1) == s.charAt(j - 1)) {
  14.                     dp[i][j] += dp[i - 1][j - 1];
  15.                 }
  16.             }
  17.         }
  18.         return dp[m][n];
  19.     }
  20. }

 4.交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1、s2、和 s3 都由小写英文字母组成

  1. class Solution {
  2.     public boolean isInterleave(String s1, String s2, String s3) {
  3.         int m = s1.length(), n = s2.length();
  4.         if (m + n != s3.length()) {
  5.             return false;
  6.         }
  7.         
  8.         s1 = "" + s1;
  9.         s2 = "" + s2;
  10.         s3 = "" + s3;
  11.         
  12.         boolean[][] dp = new boolean[m + 1][n + 1];
  13.         dp[0][0] = true; // 初始化第一个位置
  14.         
  15.         for (int j = 1; j <= n; j++) { // 初始化第一行
  16.             if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
  17.                 dp[0][j] = true;
  18.             } else {
  19.                 break;
  20.             }
  21.         }
  22.         
  23.         for (int i = 1; i <= m; i++) { // 初始化第一列
  24.             if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
  25.                 dp[i][0] = true;
  26.             } else {
  27.                 break;
  28.             }
  29.         }
  30.         
  31.         for (int i = 1; i <= m; i++) {
  32.             for (int j = 1; j <= n; j++) {
  33.                 dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j])
  34.                         || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
  35.             }
  36.         }
  37.         
  38.         return dp[m][n];
  39.     }
  40. }

5.通配符匹配 

44. 通配符匹配icon-default.png?t=N7T8https://leetcode.cn/problems/wildcard-matching/

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：

输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b
  1. class Solution {
  2.     //主要是*可以匹配空符，1个，2个。。。。,s的[0,i],p的[0,j]
  3.     public boolean isMatch(String s, String p) {
  4.         if (p.equals("*")) return true;
  5.         int m = s.length();
  6.         int n = p.length();
  7.         boolean[][] dp = new boolean[m + 1][n + 1];
  8.         dp[0][0] = true;
  9.         for (int j = 1; j <= n; j++) {
  10.             if (p.charAt(j - 1) == '*') {
  11.                 dp[0][j] = true;
  12.             }else 
  13.                 break;
  14.         }
  15.  
  16.         for (int i = 1; i <= m; i++) {
  17.             for (int j = 1; j <= n; j++) {
  18.                 if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
  19.                     dp[i][j] = dp[i - 1][j - 1];
  20.                 } else if (p.charAt(j - 1) == '*') {
  21.                     dp[i][j] = dp[i][j - 1] || dp[i - 1][j];//去一个空符+数学推导
  22.                 }
  23.             }
  24.         }
  25.         
  26.         return dp[m][n];
  27.     }
  28. }

6.两个字符串的最小ASCII删除和

712. 两个字符串的最小ASCII删除和icon-default.png?t=N7T8https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

转化：在两个字符串中找出

  1. class Solution {
  2.     public int minimumDeleteSum(String s1, String s2) {
  3.         int m = s1.length();
  4.         int n = s2.length();
  5.         int sum = 0;
  6.         for (int i = 0; i < m; i++) {
  7.             sum += (int) s1.charAt(i);
  8.         }
  9.         for (int i = 0; i < n; i++) {
  10.             sum += (int) s2.charAt(i);
  11.         }
  12.         int[][] dp = new int[m + 1][n + 1];
  13.  
  14.         for (int i = 1; i <= m; i++) {
  15.             for (int j = 1; j <= n; j++) {
  16.                 if (s1.charAt(i - 1) == s2.charAt(j - 1))
  17.                     dp[i][j] = dp[i - 1][j - 1] + (int) s1.charAt(i - 1);
  18.                 else
  19.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  20.             }
  21.         }
  22.         return sum - 2 * dp[m][n];
  23.     }
  24. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/487741
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号