IT俱乐部 Java Java C++题解eetcode940不同的子序列 II

Java C++题解eetcode940不同的子序列 II

题目要求

思路一:动态规划+转移优化

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;
        vector f(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俱乐部其它相关文章!

本文收集自网络,不代表IT俱乐部立场,转载请注明出处。https://www.2it.club/code/java/5010.html
上一篇
下一篇
联系我们

联系我们

在线咨询: QQ交谈

邮箱: 1120393934@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部