第 256 场周赛 5857. 不同的好子序列数目

Rank 303,日常最后一题不会做。。。补了几道子序列的题目,希望以后碰到这种计数的可以做出来

Desciption

给你一个二进制字符串 binary 。 binary 的一个 子序列 如果是 非空 的且没有 前导 0 (除非数字是 “0” 本身),那么它就是一个 好 的子序列。

请你找到 binary 不同好子序列 的数目。

比方说,如果 binary = “001” ,那么所有 好 子序列为 [“0”, “0”, “1”] ,所以 不同 的好子序列为 “0” 和 “1” 。 注意,子序列 “00” ,“01” 和 “001” 不是好的,因为它们有前导 0 。 请你返回 binary 中 不同好子序列 的数目。由于答案可能很大,请将它对 109 + 7 取余 后返回。

一个 子序列 指的是从原数组中删除若干个(可以一个也不删除)元素后,不改变剩余元素顺序得到的序列。

1 <= binary.length <= 10^5
binary 只含有 '0' 和 '1' 。

示例:

输入:binary = "101"
输出:5
解释:好的二进制子序列为 ["1", "0", "1", "10", "11", "101"] 。
不同的好子序列为 "0" ,"1" ,"10" ,"11" 和 "101" 。

Solution

这种计算数量的题目,可以考虑dp。

可以看出是 940. 不同的子序列 II 题目的一个变种,我们思考一下这个题该怎么做?

首先是前导 0 的限制,题目的要求 好的子序列是非空且没有前导 0(除非数字是 “0” 本身),因此我们可以强制 子序列的开头必须是 1

我们首先找到字符串中第一个 1 所在的地方,假定这个 1 必须在“好的子序列“里,则包含这个 1 的“好的子序列”的数量,为这个 1 后面的字符串的子序列的数量,就变成了 940. 不同的子序列 II 题目的解法。

这样感觉会漏计算一些“好的子序列”:

  • 这个 1 如果不选的话,则以后面的 1 开头的“好的子序列”,肯定已经被包含在以这个 1 开头的“好的子序列“里了,因此不必考虑不选这个 1 的状态
  • “0” 子序列漏了:遍历 binary,如果包含 “0”,则把答案加 1

Code

    public int numberOfUniqueGoodSubsequences(String binary) {
        int n = binary.length();
        int st = -1;
        for (int i = 0; i < n; ++i) {
            if (binary.charAt(i) != '0') {
                st = i;
                break;
            }
        }
        if (st == -1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        int[] last = {-1, -1};
        dp[st + 1] = 1;
        int mod = 1000000007;
        for (int i = st + 2; i <= n; ++i) {
            dp[i] = dp[i-1] * 2 % mod;
            int x = binary.charAt(i - 1) - '0';
            if (last[x] >= 0) {
                dp[i] = (dp[i] + mod - dp[last[x]]) % mod;
            }
            last[x] = i - 1;
        }
        int ans = dp[n];
        for (int i = 0; i < n; ++i) {
            if (binary.charAt(i) == '0') {
                ans = (ans + 1) % mod;
                break;
            }
        }
        return ans;
    }