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

Posted on by

題目要求

思路一：動態規劃+轉移優化

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;
    }
}
  • 時間復雜度：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 < 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;
    }
};
  • 時間復雜度：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<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;
    }
};
  • 時間復雜度：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::<i64>() % MOD + 1;
        }
        (f.iter().sum::<i64>() % MOD) as i32
    }
}
  • 時間復雜度：O(n×C)
  • 空間復雜度：O(C)

總結

完全沒思路的一道題~是那種望而生畏，讀完題失去夢想，看完題解覺得自己是傻子的類型……

看普通動規的題解感覺好難理解，差點放棄，然後跳到後面理清思路返回來就好理解很多，但還是隻選瞭兩種比較簡潔的方式寫；

以上就是Java C++題解eetcode940不同的子序列 II的詳細內容，更多關於Java C++ 不同的子序列的資料請關註WalkonNet其它相關文章！

推薦閱讀：

    None Found