資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的 Distinct Subsequences II
假設我們有一個字串 S，我們需要計算 S 的不同子序列的數量。結果可能很大，因此我們將返回模 10^9 + 7 的結果。
因此，如果輸入類似於“bab”，則輸出將為 6，因為有 6 個不同的序列，它們是“a”，“b”，“ba”，“ab”，“bb”，“abb”。
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 add()，它將接收 a、b，
返回 ((a mod MOD) + (b mod MOD)) mod MOD
定義一個函式 sub()，它將接收 a、b，
返回 (((a mod MOD) - (b mod MOD)) + MOD) mod MOD
定義一個函式 mul()，它將接收 a、b，
返回 ((a mod MOD) * (b mod MOD)) mod MOD
從主方法開始，執行以下操作 -
n := s 的大小
定義一個大小為 26 的陣列 dp
res := 0
s := 在 s 前面連線空格
從 i := 1 初始化，當 i <= n 時，更新（i 增加 1），執行 -
x := s[i]
added := sub(add(res, 1), dp[x - 'a'])
dp[x - 'a'] = add(dp[x - 'a'], added)
res := add(res, added)
返回 res
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % MOD) + (b % MOD) ) % MOD;
}
lli sub(lli a, lli b){
return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
}
lli mul(lli a, lli b){
return ( (a % MOD) * (b % MOD) ) % MOD;
}
int distinctSubseqII(string s) {
int n = s.size();
vector <lli> dp(26);
int res = 0;
s = " " + s;
for(lli i = 1; i <= n; i++){
char x = s[i];
int added = sub(add(res, 1) , dp[x - 'a']);
dp[x - 'a'] = add(dp[x - 'a'], added);
res = add(res, added);
}
return res;
}
};
main(){
Solution ob;
cout << (ob.distinctSubseqII("bab"));
}輸入
"bab"
輸出
6
更新於: 2020年6月4日
89 次瀏覽
廣告