欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2022年10月17日 11:19:48   作者:AnjaVon  
這篇文章主要為大家介紹了Java?C++題解eetcode940不同的子序列?II實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

題目要求

思路一:動(dòng)態(tài)規(guī)劃+轉(zhuǎn)移優(yōu)化

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 < s.length(); i++) {
            int cur = s.charAt(i) - 'a', pre = f[cur];
            f[cur] = (res + 1) % MOD;
            res = ((res + f[cur] - pre) % MOD + MOD) % MOD;
        }
        return res;
    }
}
  • 時(shí)間復(fù)雜度:O(n×C)
  • 空間復(fù)雜度: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 < s.size(); i++) {
            int cur = s[i] - 'a', pre = f[cur];
            f[cur] = (res + 1) % MOD;
            res = ((res + f[cur] - pre) % MOD + MOD) % MOD;
        }
        return res;
    }
};
  • 時(shí)間復(fù)雜度:O(n×C)
  • 空間復(fù)雜度: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
    }
}
  • 時(shí)間復(fù)雜度:O(n×C)
  • 空間復(fù)雜度:O(C)

思路二:求和(調(diào)api)

  • 思路和上面相似,但更簡(jiǎn)單粗暴一點(diǎn),f[i]依舊用于記錄以當(dāng)前字符為末尾的子串?dāng)?shù)量,在每次遍歷中計(jì)算整個(gè)數(shù)組的和(即當(dāng)前的全部子串?dāng)?shù)量),然后加上自己的單字符串,表示為f[i]=sum(f)+1,答案即為整個(gè)數(shù)組的和;
  • 此處規(guī)避掉了重復(fù)字符的討論,因?yàn)橄嗤址竺娴臅?huì)覆蓋前面的,可以看作每次遍歷都在已有子串的基礎(chǔ)上加一個(gè)字符【md我在說(shuō)什么,舉個(gè)例子吧】;

栗子【vonvv】:

當(dāng)前遍歷字符f[i]子串
v1v
o2vo,o
n4vn,von,on,n
v8vv,vov,ov,vnv,vonv,onv,nv,v
v15vv,vov,ov,vnv,vonv,onv,nv,vvv,vovv,ovv,vnvv,vonvv,onvv,nvv,vv,v

最終即為三個(gè)字符對(duì)應(yīng)值相加f[o]+f[n]+f[v]=2+4+15=21

注意?。?!

因?yàn)橐?jì)算sum(f),這值可能會(huì)超級(jí)大,所以要用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);
    }
}
  • 時(shí)間復(fù)雜度:O(n×C)
  • 空間復(fù)雜度:O(C)

C++

class Solution {
public:
    int distinctSubseqII(string s) {
        int MOD = (int)1e9+7;
        vector<long> 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;
    }
};
  • 時(shí)間復(fù)雜度:O(n×C)
  • 空間復(fù)雜度:O(C)

Rust

  • get了求和函數(shù)的奇妙調(diào)用【但沒(méi)完全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::<i64>() % MOD + 1;
        }
        (f.iter().sum::<i64>() % MOD) as i32
    }
}
  • 時(shí)間復(fù)雜度:O(n×C)
  • 空間復(fù)雜度:O(C)

總結(jié)

完全沒(méi)思路的一道題~是那種望而生畏,讀完題失去夢(mèng)想,看完題解覺(jué)得自己是傻子的類(lèi)型……

看普通動(dòng)規(guī)的題解感覺(jué)好難理解,差點(diǎn)放棄,然后跳到后面理清思路返回來(lái)就好理解很多,但還是只選了兩種比較簡(jiǎn)潔的方式寫(xiě);

以上就是Java C++題解eetcode940不同的子序列 II的詳細(xì)內(nèi)容,更多關(guān)于Java C++ 不同的子序列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評(píng)論