Skip to content

子序列

子序列的数量

115. 不同的子序列 hard

剑指 Offer II 097. 子序列的数目

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

解法 DP

dp[i][j] 中 i,j 表示长度
母串的最后一个元素是否参与当次匹配
不参与是 [i-1][j];
参与是 [i-1][j] + [i-1][j-1];

java
class Solution {
    public int numDistinct(String s, String t) {
        int n1 = s.length();
        int n2 = t.length();
        long[][] dp = new long[n1 + 1][n2 + 1];
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= n2 && j <= i; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        int mod = (int) (1e9 + 7);
        return (int) (dp[n1][n2] % mod);
    }
}

解法 2 记忆化搜索

时间复杂度与 DP 相同

java
class Solution {

    int[][] memo;

    public int numDistinct(String s, String t) {
        memo = new int[s.length() + 1][t.length() + 1];
        for (int[] arr : memo) {
            Arrays.fill(arr, -1);
        }
        return helper(s, t, s.length(), t.length());
    }

    private int helper(String s, String t, int m, int n) {
        if (n == 0) return 1;
        if (m == 0) return 0;
        if (memo[m][n] > -1) return memo[m][n];

        int ans = 0;
        if (s.charAt(m - 1) == t.charAt(n - 1)) {
            ans += helper(s, t, m - 1, n - 1) + helper(s, t, m - 1, n);
        } else {
            ans += helper(s, t, m - 1, n);
        }

        memo[m][n] = ans;
        return ans;
    }
}

最长子序列

128. 最长连续序列 mid

剑指 Offer II 119. 最长连续序列

给定一个未排序的整数数组 nums, 找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

找到开头, 然后++统计数量

java
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int res = 0;
        for (int num : numSet) {
            // 找起点
            if (!numSet.contains(num - 1)) {
                int currNum = num;
                while (numSet.contains(currNum + 1)) {
                    currNum++;
                }
                res = Math.max(res, currNum - num + 1);
            }
        }
        return res;
    }
}

300. 最长递增子序列 mid

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

子序列 是由数组派生而来的序列, 删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解法 1 DP

状态转移方程: dp[i]=max(dp[j])+1;j[0,i),nums[j]<nums[i]

java
class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp[i]=以nums[i]为结尾的子序列的长度
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

解法 2 贪心+二分

维护 1 个递增数组 arr, arr[i] 是当长度等于 i+1 时, 尾部的元素最小值;
如果后面出现更小值, 二分查找替换到队列中

go
func lengthOfLIS(nums []int) int {
	list := []int{}
	for _, x := range nums {
		i := sort.SearchInts(list, x)
		if i == len(list) {
			list = append(list, x)
		} else {
			list[i] = x
		}
	}
	return len(list)
}

376. 摆动序列 mid

如果连续数字之间的差严格地在正数和负数之间交替, 则数字序列称为 摆动序列。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列, 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反, [1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列, 第一个序列是因为它的前两个差值都是正数, 第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得, 剩下的元素保持其原始顺序。

给你一个整数数组 nums, 返回 nums 中作为 摆动序列 的 最长子序列的长度。

连续递增的序列只计算为 2, 也就是中间的点拿掉
遍历中, 只根据前一个的状态转移长度

java
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return Math.max(up, down);
    }
}

516. 最长回文子序列 mid

给你一个字符串 s,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

解法 DP

dp[i][j]表示: [i,j] 范围内的最大长度

java
class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                // dp[i + 1][j] 和 dp[i][j - 1] 最多比 dp[i + 1][j - 1] 多 2; 懒得想可以再取1次max
                else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}

583. 两个字符串的删除操作 mid

给定两个单词 word1 和 word2,返回使得 word1 和 word2 相同所需的最小步数。 每步可以删除任意一个字符串中的一个字符。

解法 DP

java
class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(
                            2 + dp[i - 1][j - 1],
                            1 + Math.min(dp[i][j - 1], dp[i - 1][j])
                    );
            }
        }
        return dp[n1][n2];
    }
}

873. 最长的斐波那契子序列的长度 mid

剑指 Offer II 093. 最长斐波那契数列

如果序列 X1,X2,...,Xn 满足下列条件,就说它是 斐波那契式 的:

  • n>=3
  • 对于所有 i+2<=n,都有 Xi+Xi+1=Xi+2

给定一个严格递增的正整数数组形成序列 arr ,找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在,返回 0。

一个斐波那契数列可以由最后 2 个元素表征
dp[i][j] 表示最后 2 个元素为[i]和[j]的长度
类似于 3 数之和

java
class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int res = 0;
        for (int i = 2; i < n; i++) {
            int j = i - 1;
            int k = 0;
            while (k < j) {
                if (arr[k] + arr[j] == arr[i]) {
                    dp[j][i] = Math.max(3, dp[k][j] + 1);
                    res = Math.max(res, dp[j][i]);
                    j--;
                    k++;
                } else if (arr[k] + arr[j] < arr[i]) k++;
                else j--;
            }
        }
        return res;
    }
}

判定子序列

392 判断子序列 easy

给定字符串 s 和 t, 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

解法 贪心

java
class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.isEmpty()) return true;
        int i = 0;
        for (int j = 0; i < s.length() && j < t.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) i++;
        }
        return i >= s.length();
    }
}

利用 api

java
class Solution {
    public boolean isSubsequence(String s, String t) {
        int idx = -1;
        for (char c : s.toCharArray()) {
            idx = t.indexOf(c, idx + 1);
            if (idx == -1) return false;
        }
        return true;
    }
}

进阶: 如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10 亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

解法 DP

dp[len][26] 记录某个 idx 之后字符 c 的索引
搜索的时候维护 1 个 offset

java
class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = t.length();
        int[][] dp = new int[n + 1][26];
        Arrays.fill(dp[n], -1);
        for (int i = n - 1; i >= 0; i--) {
            char c = t.charAt(i);
            for (int j = 0; j < 26; j++) {
                if (c == j + 'a')
                    dp[i][j] = i;
                else
                    dp[i][j] = dp[i + 1][j];
            }
        }
        int idx = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dp[idx][c - 'a'] == -1) return false;
            idx = dp[idx][c - 'a'] + 1;
        }
        return true;
    }
}

524. 通过删除字母匹配到字典里最长单词 mid

给你一个字符串 s 和一个字符串数组 dictionary,找出并返回 dictionary 中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个,返回长度最长且字母序最小的字符串。如果答案不存在,则返回空字符串。

解法 1 暴力

双指针子序列判定 + 取最大的 dic
排不排序无所谓

Java
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        // 长的, 字母序小的
        dictionary.sort((word1, word2) -> word1.length() != word2.length() ? word2.length() - word1.length() : word1.compareTo(word2));
        for (String d : dictionary) {
            if (isSubString(s,d)) return d;
        }
        return "";
    }

    private boolean isSubString(String s, String d) {
        // s > d
        int i = 0;
        int j = 0;
        while (i < s.length() && j < d.length()) {
            if (s.charAt(i) == d.charAt(j)) j++;
            i++;
        }
        return j == d.length();
    }
}

解法 2 DP 优化

可以 DP 优化, 预处理对于字符串 s 的每 1 个位置,从该位置开始往后每 1 个 char 第 1 次出现的位置。
dp[m][26]
这样可以在匹配的时候跳到 s 的下个索引

java
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        int n = s.length();
        int[][] dp = new int[n + 1][26];
        // 哨兵
        Arrays.fill(dp[n], n);
        // 预处理 s
        for (int i = n - 1; i >= 0; i--) {
            for (int c = 0; c < 26; c++) {
                if (s.charAt(i) == 'a' + c)
                    dp[i][c] = i;
                else
                    dp[i][c] = dp[i + 1][c];
            }
        }
        String res = "";
        for (String d : dictionary) {
            if (d.length() < res.length() || d.length() == res.length() && res.compareTo(d) <= 0) continue;
            boolean match = true;
            int j = 0; // s 的索引
            for (int i = 0; i < d.length(); i++) {
                if (dp[j][d.charAt(i) - 'a'] == n) {
                    match = false;
                    break;
                }
                j = dp[j][d.charAt(i) - 'a'] + 1;
            }
            if (match) res = d;
        }
        return res;
    }
}