跳到主要内容

子序列题库

2024年03月14日
柏拉文
越努力，越幸运

一、不同的子序列​

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例1:

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例2:

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

1.1 动态规划​

思路:

  1. 状态定义:
    • s[i:]表示s从下标i到末尾的子字符串
    • t[j:]表示s从下标j到末尾的子字符串
    • dp[i][j]表示在s[i:]的子序列中t[j:]出现的个数
  2. 状态转移方程:
    • j=n时，t[j:]为空字符串，由于空字符串是任何字符串的子序列，因此对任意的0<=i<=m,方程为:dp[i][n]=1`
    • i=m&&j<n时，s[i:]为空字符串,t[j:]为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意0<=j<n,方程为:dp[m][j]=0
    • i<m&&j<n时，
      • 如果s[i]==t[j]时，方程为:dp[i][j]=dp[i+1][j+1]+dp[i+1][j]
      • 如果s[i]!=t[j]时, 方程为:dp[i][j]=dp[i+1][j]
  3. 初始化状态: dp 初始元素为 0
  4. 问题答案: dp[0][0]即为在s的子序列中t出现的个数
function numDistinct(s, t) {
    const row=s.length;
    const col=t.length;
    if(row<col){
        return 0;
    }
    const dp=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(0));
    for(let i=0;i<=row;i++){
        dp[i][col]=1;
    }
    for(let i=row-1;i>=0;i--){
        for(let j=col-1;j>=0;j--){
            if(s[i]==t[j]){
                dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
            }else{
                dp[i][j]=dp[i+1][j];
            }
        }
    }
    return dp[0][0];
};

性能分析:

  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

二、最长公共子序列​

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

2.1 动态规划​

思路:

  1. 状态定义: 假设字符串text1和text2的长度分别为m和n,创建m+1行n+1列的二维数组dp,其中dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度
  2. 动态转移方程:
    • 当i>0且j>0时：
      • 如果text1[i-1]=text2[j-1]，dp[i][j]=dp[i-1][j-1]+1
      • 如果text1[i-1]!=text2[j-1],dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    • 当i=0或者j=0时: dp[i][j]=0
  3. 初始化状态: dp 元素都为0
  4. 问题答案: dp[m][n]即为text1和text2的最长公共子序列的长度
function longestCommonSubsequence(text1, text2) {
    const row=text1.length;
    const col=text2.length;
    const dp=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(0));
    for(let i=1;i<=row;i++){
        for(let j=1;j<=col;j++){
            if(text1[i-1]==text2[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[row][col];
};

性能分析:

  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

三、最长递增子序列​

给你一个整数数组nums,找到其中最长严格递增子序列的长度。

示例1:

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2:

输入：nums = [0,1,0,3,2,3]
输出：4

3.1 贪心+二分查找​

问题: 给你一个整数数组 nums, 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1:

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2:

输入：nums = [0,1,0,3,2,3]
输出：4

思路: 贪心+二分查找

  • 贪心思路: 如果我们要使上升子序列尽可能的长,则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小

  • 初始化:

    • 维护一个数组 d[i]: 表示长度为 i 的最长上升子序列的末尾元素的最小值, d[1]=nums[0]

    • 用 len 记录目前最长上升子序列的长度: 起始时 len 为 1

  • 算法流程: 从前往后遍历数组 nums,在遍历到 nums[i] 时:

    • 如果 nums[i]>d[len], 则直接加入到 d 数组末尾，并更新 len=len+1

    • 否则，在 d 数组中二分查找(因为 d 数组是单调递增的，可以通过二分查找),找到第一个比 nums[i] 小的数 d[k]，并更新 d[k+1]=nums[i]

实现:

function binarySearch(left, right, target, array) {
  let l = left;
  let r = right;
  while (l < r) {
    let middle = (l + r) >> 1;
    if (array[middle] < target) {
      l = middle + 1;
    } else {
      r = middle;
    }
  }
  return l;
}

function lengthOfLIS(nums) {
  let len = 1;
  const dp = new Array(nums.length + 1);
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    if (num > dp[len]) {
      dp[++len] = num;
    } else {
      let pos = binarySearch(1, len, num, dp);
      dp[pos] = num;
    }
  }
  return len; // 返回递增序列长度 
  return dp.filter(i => i); // 返回递增序列
}

测试

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(nums));

  • 时间复杂度: O(nlogn)

  • 空间复杂度: O(n)

四、最长递增子序列的个数​

问题: 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

示例:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

4.1 贪心 + 前缀和 + 二分查找​

  1. 我们将数组 d 扩展成一个二维数组，其中 d[i] 数组表示所有能成为长度为 i 的最长上升子序列的末尾元素的值。具体地，我们将更新 d[i]=nums[j] 这一操作替换成将 nums[j] 置于 d[i] 数组末尾。这样 d[i] 中就保留了历史信息，且 d[i] 中的元素是有序的（单调非增）。

  2. 类似地，我们也可以定义一个二维数组 cnt，其中 cnt[i][j] 记录了以 d[i][j] 为结尾的最长上升子序列的个数。为了计算 cnt[i][j]，我们可以考察 d[i−1] 和 cnt[i−1]，将所有满足 d[i−1][k]<d[i][j] 的 cnt[i−1][k] 累加到 cnt[i][j]，这样最终答案就是 cnt[maxLen] 的所有元素之和。

  3. 在代码实现时，由于 d[i]d[i]d[i] 中的元素是有序的，我们可以二分得到最小的满足 d[i−1][k]<d[i][j] 的下标 k。另一处优化是将 cnt 改为其前缀和，并在开头填上 0，此时 d[i][j] 对应的最长上升子序列的个数就是 cnt[i−1][−1]−cnt[i−1][k]，这里 [−1] 表示数组的最后一个元素。

function binarySearch1(left,right,target,array){
    let l = left;
    let r = right;
    while(l < r){
        const middle = (l + r) >> 1;
        const list = array[middle];
        if(list[list.length - 1] < target){
            l = middle + 1;
        }else{
            r = middle;
        }
    }
    return l;
}

function binarySearch2(left,right,target,array){
    let l = left;
    let r = right;
    while(l < r){
        const middle = (l + r) >> 1;
        if(array[middle] < target){
            r = middle;
        }else{
            l = middle + 1;
        }
    }
    return l;
}

function findNumberOfLIS(nums){
    const d = [];
    const cnt = [];
    for(const num of nums){
        const i = binarySearch1(0, d.length,num,d);
        let c = 1;
        if(i > 0){
            const k = binarySearch2(0,d[i-1].length,num,d[i-1]);
            c = cnt[i-1][cnt[i-1].length -1] - cnt[i-1][k];
        }
        if(i === d.length){
            const dList = [];
            dList.push(num);
            d.push(dList);
            const cntList = [];
            cntList.push(0);
            cntList.push(c);
            cnt.push(cntList);
        }else{
            d[i].push(num);
            const cntSize = cnt[i].length;
            cnt[i].push(cnt[i][cntSize - 1]+c);
        }
    }   

    const size1 = cnt.length;
    const size2 = cnt[size1 - 1].length;
    return cnt[size1 - 1][size2 -1];
}

复杂度分析

  • 时间复杂度: O(nlogn)

  • 空间复杂度: O(n)

五、每个元音包含偶数次的最长子字符串​

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

示例1:

输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。

示例2:

输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。

5.1 前缀和与状态压缩​

思路:

  1. 状态定义: dp[pattern] 用来记录当前索引值下对应的元音奇偶次数组合特征,一共有32中情况
  2. 状态压缩: 将a、e、i、o、u 出现的奇偶次状态用 0和1标识，0 表示该字母出现了偶数次，1 表示该字母出现了奇数次。如果该字母又出现了一次，那么奇数次+1=偶数次，偶数次+1=奇数次，需要奇偶切换状态，并且其他字母状态保持不变，这里使用按位异或运算。
    • 通过1、2点举例说明: dp[10] 对应二进制为 dp[01010],此时组合特征为: u:偶数,o:奇数,i:偶数,e:奇数,a:偶数。如果下一次遍历出现了a字母，那么此时a的状态要切换成奇数，我们通过按位异或运算来切换01010^00001，结果变为01011
    • 通过1、2点举例说明: dp[8] 对应二进制为 dp[01000],此时组合特征为: u:偶数,o:奇数,i:偶数,e:偶数,a:偶数。如果下一次遍历出现了a字母，那么此时a的状态要切换成奇数，我们通过按位异或运算来切换01000^00001,结果变为01001
  3. 状态转移方程: 每一次遍历，都会有一个[dp[pattern],i]区间
    • 如果dp[pattern]!=-1 更新长度result=max(result,i-dp[pattern]+1)
    • 如果dp[pattern]==-1，方程为: dp[pattern]=i+1
  4. 初始化状态:
    • dp初始预设为-1
    • dp[0]为0
function findTheLongestSubstring(s) {
    const len=s.length;
    const dp=new Array(1<<5).fill(-1);
    let result=0;
    let status=0;
    dp[0]=0;
    for(let i=0;i<len;i++){
        let ch=s[i];
        if(ch=='a'){
            status^=1<<0;
        }else if(ch=='e'){
            status^=1<<1;
        }else if(ch=='i'){
            status^=1<<2;
        }else if(ch=='o'){
            status^=1<<3;
        }else if(ch=='u'){
            status^=1<<4;
        }
        if(~dp[status]){
            result=Math.max(result,i+1-dp[status]);
        }else{
            dp[status]=i+1;
        }
    }
    return result;
};

性能分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(s)