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我在說什么，舉個(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)放棄，然后跳到后面理清思路返回來就好理解很多，但還是只選了兩種比較簡(jiǎn)潔的方式寫；
以上就是Java C++題解eetcode940不同的子序列 II的詳細(xì)內(nèi)容，更多關(guān)于Java C++ 不同的子序列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
java排查進(jìn)程占用系統(tǒng)內(nèi)存高方法
這篇文章主要為大家介紹了java進(jìn)程占用系統(tǒng)內(nèi)存高排查方法，2023-06-06
這篇文章主要介紹了springboot使用@data注解減少不必要代碼,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
Java深入數(shù)據(jù)結(jié)構(gòu)理解掌握抽象類與接口
在類中沒有包含足夠的信息來描繪一個(gè)具體的對(duì)象，這樣的類稱為抽象類，接口是Java中最重要的概念之一，它可以被理解為一種特殊的類，不同的是接口的成員沒有執(zhí)行體，是由全局常量和公共的抽象方法所組成，本文給大家介紹Java抽象類和接口，感興趣的朋友一起看看吧2022-05-05
解決一個(gè)JSON反序列化問題的辦法(空字符串變?yōu)榭占?
在平時(shí)的業(yè)務(wù)開發(fā)中,經(jīng)常會(huì)有拿到一串序列化后的字符串要來反序列化,下面這篇文章主要給大家介紹了如何解決一個(gè)JSON反序列化問題的相關(guān)資料,空字符串變?yōu)榭占?需要的朋友可以參考下2024-03-03
spring中12種@Transactional的失效場(chǎng)景(小結(jié))
日常我們進(jìn)行業(yè)務(wù)開發(fā)時(shí)，基本上使用的都是聲明式事務(wù)，即為使用@Transactional注解的方式，本文主要介紹了spring中12種@Transactional的失效場(chǎng)景，感興趣的小伙伴們可以參考一下2022-01-01
Java?list如何實(shí)現(xiàn)將指定元素排在第一位
這篇文章主要為大家詳細(xì)介紹了Java?list中如何實(shí)現(xiàn)將指定元素排在第一位,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-02-02
Shiro想必大家都知道了，是目前使用率要比spring security都要多的一個(gè)權(quán)限框架，下面這篇文章主要給大家介紹了關(guān)于Shiro集成Spring之注解的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-09-09
Mybatis-plus:${ew.sqlselect}用法說明
這篇文章主要介紹了Mybatis-plus:${ew.sqlselect}用法說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06
RabbitMQ中的Connection和Channel信道詳解
這篇文章主要介紹了RabbitMQ中的Connection和Channel信道詳解,信道是建立在 Connection 之上的虛擬連接,RabbitMQ 處理的每條 AMQP 指令都是通過信道完成的,需要的朋友可以參考下2023-08-08
短網(wǎng)址的原理與生成方法（Java實(shí)現(xiàn)）
這篇文章主要給大家介紹了關(guān)于短網(wǎng)址的原理與生成方法，利用的是Java實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10