【刷题篇】动态规划(七)
1、 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> hash;
for(auto& e : wordDict)
hash.insert(e);
int n=s.size();
vector<bool> dp(n+1);
dp[0]=true;
s=' '+s;//使下面便利的更加的清晰
for(int i=1;i<=n;i++)
{
for(int j=i;j>=1;j--)
{
if(dp[j-1]&&hash.count(s.substr(j,i-j+1)))
{
dp[i]=true;
break;
}
}
}
return dp[n];
}
};
2、环绕字符串中唯一的子字符串
定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串,所以 base 看起来是这样的:
“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.
给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
class Solution {
public:
int findSubstringInWraproundString(string s) {
int n=s.size();
vector<int> dp(n,1);
for(int i=1;i<n;i++)
{
if(s[i-1]+1==s[i]||(s[i-1]=='z'&&s[i]=='a'))
dp[i]+=dp[i-1];
}
int hash[26]={0};
for(int i=0;i<n;i++)
hash[s[i]-'a']=max(dp[i],hash[s[i]-'a']);
int sum=0;
for(int i=0;i<26;i++)
sum+=hash[i];
return sum;
}
};
3、 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int size=nums.size();
vector<int> dp(size,1);
int maxi=-0x3F3F3F3F;
for(int i=0;i<size;i++)
{
for(int j=0;j<=i;j++)
if(nums[i]>nums[j])
dp[i]=max(dp[i],dp[j]+1);
maxi=max(dp[i],maxi);
}
return maxi;
}
};
4、摆动序列
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n=nums.size();
vector<int> d(n,1),p(n,1);
int maxi=-0x3F3F3f3F;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
d[i]=max(p[j]+1,d[i]);
else if(nums[i]<nums[j])
p[i]=max(d[j]+1,p[i]);
}
maxi=max(maxi,max(d[i],p[i]));
}
return maxi;
}
};
5、最长递增子序列的个数
给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n=nums.size();
vector<int> len(n,1),count(n,1);
int maxlen=1,maxcount=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
{
if(len[j]+1==len[i])
count[i]+=count[j];
else if(len[j]+1>len[i])
{
len[i]=len[j]+1;
count[i]=count[j];
}
}
}
if(maxlen==len[i])
maxcount+=count[i];
else if(maxlen<len[i])
{
maxlen=len[i];
maxcount=count[i];
}
}
return maxcount;
}
};
6、最长数对链
给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在,我们定义一种 跟随 关系,当且仅当 b < c 时,数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(),pairs.end());//按第一个数排序
int n=pairs.size();
vector<int> dp(n,1);
int maxi=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(pairs[j][1]<pairs[i][0])
dp[i]=max(dp[j]+1,dp[i]);
}
maxi=max(maxi,dp[i]);
}
return maxi;
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!