数据结构
网络
关系型数据库管理系统 (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 次浏览
广告