【算法挨揍日记】day40——712. 两个字符串的最小ASCII删除和、718. 最长重复子数组

谁践踏了优雅 2024-02-05 14:58 66阅读 0赞

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

[712. 两个字符串的最小ASCII删除和][712. _ASCII]

### 题目描述： ###

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

![7a24e4be11764632bfaeb8840b26969f.png][]

### 解题思路： ###

算法思路：

正难则反：求两个字符串的最⼩  ASCII  删除和，其实就是找到两个字符串中所有的公共⼦序列

⾥⾯，  ASCII  最⼤和。

因此，我们的思路就是按照「最⻓公共⼦序列」的分析⽅式来分析。

1.  状态表⽰：

dp\[i\]\[j\]  表⽰：  s1  的  \[0, i\]  区间以及  s2  的  \[0, j\]  区间内的所有的⼦序列中，公

共⼦序列的  ASCII  最⼤和。

2.  状态转移⽅程：

对于  dp\[i\]\[j\]  根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：

i.  当  s1\[i\] == s2\[j\]  时：应该先在  s1  的  \[0, i - 1\]  区间以及  s2  的  \[0, j

\- 1\]  区间内找⼀个公共⼦序列的最⼤和，然后在它们后⾯加上⼀个  s1\[i\]  字符即可。

此时  dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + s1\[i\]  ；

ii.  当 s1\[i\] != s2\[j\] 时：公共⼦序列的最⼤和会有三种可能：

•  s1  的  \[0, i - 1\]  区间以及  s2  的  \[0, j\]  区间内：此时  dp\[i\]\[j\] =

dp\[i - 1\]\[j\]  ；

•  s1  的  \[0, i\]  区间以及  s2  的  \[0, j - 1\]  区间内：此时  dp\[i\]\[j\] =

dp\[i\]\[j - 1\]  ；

•  s1  的  \[0, i - 1\]  区间以及  s2  的  \[0, j - 1\]  区间内：此时  dp\[i\]\[j\]

= dp\[i - 1\]\[j - 1\]  。

但是前两种情况⾥⾯包含了第三种情况，因此仅需考虑前两种情况下的最⼤值即可。

综上所述，状态转移⽅程为：

◦  当  s1\[i - 1\] == s2\[j - 1\]  时，  dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + s1\[i\]  ；

◦  当  s1\[i - 1\] != s2\[j - 1\]  时，  dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i\]\[j

\- 1\])

3.  初始化：

a.  「空串」是有研究意义的，因此我们将原始  dp  表的规模多加上⼀⾏和⼀列，表⽰空串。

b.  引⼊空串后，⼤⼤的「⽅便我们的初始化」。

c.  但也要注意「下标的映射」关系，以及⾥⾯的值要保证「后续填表是正确的」。

当  s1  为空时，没有⻓度，同理  s2  也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为  0  即可保证

后续填表是正确的。

4.  填表顺序：

「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5.  返回值：

根据「状态表⽰」，我们不能直接返回  dp  表⾥⾯的某个值：

i.  先找到  dp\[m\]\[n\]  ，也是最⼤公共  ASCII  和；

ii.  统计两个字符串的  ASCII  码和 s  u  m；

iii.  返回  sum - 2 \* dp\[m\]\[n\]  。

###  ###

### 解题代码： ###

class Solution {
    public:
        int minimumDeleteSum(string s1, string s2) {
            int m=s1.size();
            int n=s2.size();
            vector<vector<int>>dp(m+1,vector<int>(n+1,0));
            int sum=0;
            for(int i=0;i<m;i++)sum+=s1[i];
            for(int i=0;i<n;i++)sum+=s2[i];
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    if(s1[i-1]==s2[j-1])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);
                }
            }
            return sum-2*dp[m][n];
        }
    };

## 718. 最长重复子数组 ##

###    [718. 最长重复子数组][718.] ###

### 题目描述： ###

给两个整数数组 `nums1` 和 `nums2` ，返回 *两个数组中 **公共的** 、长度最长的子数组的长度* 。

### ![300afd9fae744cbca837626570813dd1.png][] 解题思路： ###

算法思路：

⼦数组是数组中「连续」的⼀段，我们习惯上「以某⼀个位置为结尾」来研究。由于是两个数组，

因此我们可以尝试：以第⼀个数组的  i  位置为结尾以及第⼆个数组的  j  位置为结尾来解决问

题。

1.  状态表⽰：

dp\[i\]\[j\]  表⽰「以第⼀个数组的  i  位置为结尾」，以及「第⼆个数组的  j  位置为结尾」公

共的 、⻓度最⻓的「⼦数组」的⻓度。

2.  状态转移⽅程：

对于  dp\[i\]\[j\]  ，当  nums1\[i\] == nums2\[j\]  的时候，才有意义，此时最⻓重复⼦数组的

⻓度应该等于  1  加上除去最后⼀个位置时，以  i - 1, j - 1  为结尾的最⻓重复⼦数组的⻓

度。

因此，状态转移⽅程为：  dp\[i\]\[j\] = 1 + dp\[i - 1\]\[j - 1\]

3.  初始化：

为了处理「越界」的情况，我们可以添加⼀⾏和⼀列，  dp  数组的下标从  1  开始，这样就⽆需初

始化。

第⼀⾏表⽰第⼀个数组为空，此时没有重复⼦数组，因此⾥⾯的值设置成  0  即可；

第⼀列也是同理。

4.  填表顺序：

根据「状态转移」，我们需要「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5.  返回值：

根据「状态表⽰」，我们需要返回  dp  表⾥⾯的「最⼤值」。

### 解题代码： ###

class Solution {
    public:
        int findLength(vector<int>& nums1, vector<int>& nums2) {
            int m=nums1.size();
            int n=nums2.size();
            vector<vector<int>>dp(m+1,vector<int>(n+1,0));
            int ret=0;
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(nums1[i-1]==nums2[j-1])
                        dp[i][j]=dp[i-1][j-1]+1;
                    ret=max(ret,dp[i][j]);
                }
            }
            return ret;
        }
    };

[712. _ASCII]: https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
[7a24e4be11764632bfaeb8840b26969f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/63de7c4a52424310ac0eafdae58f90c7.png
[718.]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
[300afd9fae744cbca837626570813dd1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/5efa298c62c14365ad88bbcfaba8adf2.png