文章目录
- 环绕字符串中唯一的子字符串
-
- 题目解析
- 状态转移方程
- 返回值
- 完整代码
- 最长递增子序列
-
- 子数组与子序列的区别
- 状态转移方程
- 完整代码
- 摆动序列
-
- 题目解析
- 状态转移方程
-
- f[i]状态转移方程
- g[i]状态转移方程
- 完整代码
环绕字符串中唯一的子字符串
点击查看:467. 环绕字符串中唯一的子字符串
定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串,所以 base 看起来是这样的:
“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.
给你一个字符串 s ,请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
示例 1:
输入:s = “a”
输出:1
解释:字符串 s 的子字符串 “a” 在 base 中出现。
示例 2:
输入:s = “cac”
输出:2
解释:字符串 s 有两个子字符串 (“a”, “c”) 在 base 中出现。
题目解析
若以c开头,则可分为 c ca cac
若以a开头,则可分为 a ac
若以最后一个c开头,则可分为c
在环绕字符串中去寻找 上述六种字符串,发现只有 c a 符合要求
所以只有两种
状态转移方程
dp[i] 表示 以i位置的元素为结尾的所有的子串里面,有多少个在base中出现过
dp[i]分为两种情况
–
情况1:i位置元素本身(长度为1)
在base中包含a-z的所有字母,所以单独一个字母肯定在base中出现
即该情况下长度为1
情况2:i位置元素与前面元素结合(长度大于1)
想要求以i位置的元素为结尾的所有的子串里面,有多少个在base中出现过
就需要先求i-1位置的元素为结尾的所有的子串里面,有多少个在base中出现 即dp[i-1]
然后再加上i位置的元素即可
需要保证以 i-1位置为结尾的子串加上i位置元素也要在base中出现
情况1:base是由a到z连续组成
由i-1位置的字符ASCII值+1 即可为i位置的字符的ASCII值 即s[i-1]+1==s[i]
情况2:base是由z到a 跳跃组成
i-1位置的字符为z,i位置的字符为a 即s[i-1]==‘z’ && s[i] ==‘a’
两种情况满足一个时,才为符合条件的子字符串
返回值
对于上述字符串,若返回值计算的是dp表的所有值之和
则会计算重复的子串ac ca ,导致结果错误
所以需要去重
两个字符串都是以d字符为结尾的,若都计算就会造成重复
所以当相同字符结尾,将dp值较大的进行累加 ,将dp值较小的舍去
完整代码
class Solution {
public:
int findSubstringInWraproundString(string s) {
int n=s.size();
//在base中包含a-z的所有字母,所以单独一个字母肯定在base中出现
//所以将dp表初始化为1
vector<int>dp(n,1);
//创建大小为26的数组,用于统计以i位置2为结尾的dp值
//将dp值大的进行累加 将dp值小的舍去
//以此达到去重
vector<int>arr(26,0);
int i=0;
int ret=0;
for(i=1;i<n;i++)
{
if(s[i-1]+1==s[i]||s[i-1]=='z'&&s[i]=='a')
{
dp[i]+=dp[i-1];
}
}
//遍历dp表 取其中重复子串的dp最大值
for(i=0;i<n;i++)
{
arr[s[i]-'a']=max(arr[s[i]-'a'],dp[i]);
}
for(auto&e:arr)
{
ret+=e;
}
//返回arr数组的和
return ret;
}
};
最长递增子序列
点击查看:300. 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
子数组与子序列的区别
子序列:按照从左到右的顺序,任意挑选几个 所组成的新序列 即为子序列
如:a b d 为子序列 跳过了c ,但相对顺序与原数组保持一致(d在原数组中就在a b后,新的数组也是如此)
而 d a b 就不是一个子序列了
子数组:按照从左到右的顺序,任意挑选的必须是连续的
如:a b c为子数组 ,但 a b d就不是子数组
状态转移方程
dp[i] 表示 以i位置元素为结尾的所有的子序列中,最长的递增子序列的长度
dp[i]分为两种情况
情况1:i位置元素本身(长度为1)
只有i位置元素本身,所以该情况下最长的递增子序列的长度为1
情况2:i位置元素和前面元素结合(长度大于1)
版权声明:本文为博主作者:风起、风落原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_62939852/article/details/131712164