Java?C++題解eetcode940不同的子序列?II
題目要求
思路一:動(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)
- 思路和上面相似,但更簡單粗暴一點(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我在說什么,舉個(gè)例子吧】;
栗子【vonvv】:
當(dāng)前遍歷字符 | 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 |
最終即為三個(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)用【但沒完全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èng)想,看完題解覺得自己是傻子的類型……
看普通動(dòng)規(guī)的題解感覺好難理解,差點(diǎn)放棄,然后跳到后面理清思路返回來就好理解很多,但還是只選了兩種比較簡潔的方式寫;
以上就是Java C++題解eetcode940不同的子序列 II的詳細(xì)內(nèi)容,更多關(guān)于Java C++ 不同的子序列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
java實(shí)現(xiàn)一個(gè)簡單的Web服務(wù)器實(shí)例解析
這篇文章主要介紹了java實(shí)現(xiàn)一個(gè)簡單的Web服務(wù)器實(shí)例解析,分享了相關(guān)代碼示例,小編覺得還是挺不錯(cuò)的,具有一定借鑒價(jià)值,需要的朋友可以參考下2018-02-02spring boot前后端傳參的實(shí)現(xiàn)
這篇文章主要介紹了spring boot前后端傳參的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01IntelliJ?IDEA?2024.2?發(fā)布新功能介紹Spring?Data?JPA即時(shí)查詢、自動(dòng)補(bǔ)全cro
在2024.2?Ultimate版本中,對(duì)?Spring?Data?JPA?的支持做了增強(qiáng),新功能允許您在不運(yùn)行應(yīng)用程序和分析日志文件的情況下查看方法將生成的查詢,下面就來一起看看這個(gè)版本中推出的幾個(gè)強(qiáng)大新特性2024-08-08java WSDL接口webService實(shí)現(xiàn)方式
這篇文章主要為大家詳細(xì)介紹了java WSDL接口webService實(shí)現(xiàn)方式的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-04-04springboot項(xiàng)目啟動(dòng)類錯(cuò)誤(找不到或無法加載主類 com.**Application)
本文主要介紹了spring-boot項(xiàng)目啟動(dòng)類錯(cuò)誤(找不到或無法加載主類 com.**Application),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-05-05springboot使用jasypt加密庫實(shí)現(xiàn)數(shù)據(jù)庫加解密示例代碼
這篇文章主要給大家介紹了關(guān)于springboot使用jasypt加密庫實(shí)現(xiàn)數(shù)據(jù)庫加解密的相關(guān)資料,Jasypt是一個(gè)用于配置文件加密的Java庫,它可以用來加密和解密配置文件中的敏感信息,如數(shù)據(jù)庫密碼、API?密鑰等,需要的朋友可以參考下2024-04-04