题目要求
思路一:动态规划+转移优化
Java
class Solution { public int distinctSubseqII(String s) { int MOD = (int)1e9+7; int res = 0; int[] f = new int[26]; for (int i = 0; i
- 时间复杂度:O(n×C)
- 空间复杂度:O(C)
C++
class Solution { public: int distinctSubseqII(string s) { int MOD = (int)1e9+7; int res = 0; int f[26]; memset(f, 0, sizeof(f)); for (int i = 0; i
- 时间复杂度:O(n×C)
- 空间复杂度:O(C)
Rust
impl Solution { pub fn distinct_subseq_ii(s: String) -> i32 { let MOD = 1000000007; let mut res = 0; let mut f = vec![0; 26]; for cur in s.chars() { let i = cur as u8 - 'a' as u8; let pre = f[i as usize]; f[i as usize] = (res + 1) % MOD; res = ((res + f[i as usize] - pre) % MOD + MOD) % MOD; } res } }
- 时间复杂度:O(n×C)
- 空间复杂度:O(C)
思路二:求和(调api)
- 思路和上面相似,但更简单粗暴一点,f[i]依旧用于记录以当前字符为末尾的子串数量,在每次遍历中计算整个数组的和(即当前的全部子串数量),然后加上自己的单字符串,表示为f[i]=sum(f)+1,答案即为整个数组的和;
- 此处规避掉了重复字符的讨论,因为相同字符后面的会覆盖前面的,可以看作每次遍历都在已有子串的基础上加一个字符【md我在说什么,举个例子吧】;
栗子【vonvv】:
当前遍历字符 | f[i] | 子串 |
---|---|---|
v | 1 | v |
o | 2 | vo,o |
n | 4 | vn,von,on,n |
v | 8 | vv,vov,ov,vnv,vonv,onv,nv,v |
v | 15 | vv,vov,ov,vnv,vonv,onv,nv,vvv,vovv,ovv,vnvv,vonvv,onvv,nvv,vv,v |
最终即为三个字符对应值相加f[o]+f[n]+f[v]=2+4+15=21
注意!!!
因为要计算sum(f),这值可能会超级大,所以要用long型!
Java
class Solution { public int distinctSubseqII(String s) { int MOD = (int)1e9+7; long[] f = new long[26]; for (char cur : s.toCharArray()) { f[cur - 'a'] = Arrays.stream(f).sum() % MOD + 1; } return (int)(Arrays.stream(f).sum() % MOD); } }
- 时间复杂度:O(n×C)
- 空间复杂度:O(C)
C++
class Solution { public: int distinctSubseqII(string s) { int MOD = (int)1e9+7; vectorf(26, 0); for (auto cur : s) { f[cur - 'a'] = accumulate(f.begin(), f.end(), 1l) % MOD; } return accumulate(f.begin(), f.end(), 0l) % MOD; } };
- 时间复杂度:O(n×C)
- 空间复杂度:O(C)
Rust
- get了求和函数的奇妙调用【但没完全get】
impl Solution { pub fn distinct_subseq_ii(s: String) -> i32 { let MOD = 1000000007; let mut f = vec![0; 26]; for cur in s.chars() { f[(cur as u8 - 'a' as u8) as usize] = f.iter().sum::() % MOD + 1; } (f.iter().sum:: () % MOD) as i32 } }
- 时间复杂度:O(n×C)
- 空间复杂度:O(C)
总结
完全没思路的一道题~是那种望而生畏,读完题失去梦想,看完题解觉得自己是傻子的类型……
看普通动规的题解感觉好难理解,差点放弃,然后跳到后面理清思路返回来就好理解很多,但还是只选了两种比较简洁的方式写;
以上就是Java C++题解eetcode940不同的子序列 II的详细内容,更多关于Java C++ 不同的子序列的资料请关注IT俱乐部其它相关文章!