不同的好子序列数目
难度:
标签:
题目描述
代码结果
运行时间: 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`时,它们具体代表了什么意义?为何选择这样的表示方法?
▷🦆
为什么在处理字符'1'时,更新`odd`的表达式中要额外加1?
▷🦆
你是如何确保子序列不包含前导0的?在代码中是如何体现这一点的?
▷🦆
题解中提到,最终结果需要加上单独的'0'序列,这是基于什么考虑?为何需要特别处理?
▷