可以免费浏览的网站,做网站哪个语言快,织梦xml网站地图,做好网络推广的技巧等差数列划分 思路#xff1a;
经验题目要求
dp[i]表示#xff1a;以 i 位置为结尾的所有子数组中有多少个等差数列
状态转移方程
对 dp[i] 位置#xff0c;数列至少有三个元素#xff0c;如果相邻三个为等差数列#xff0c;dp[i] dp[i-1] 1; 如果相邻三个不为等差数…等差数列划分 思路
经验题目要求
dp[i]表示以 i 位置为结尾的所有子数组中有多少个等差数列
状态转移方程
对 dp[i] 位置数列至少有三个元素如果相邻三个为等差数列dp[i] dp[i-1] 1; 如果相邻三个不为等差数列dp[i] 0;
初始化
dp[0] 和 dp[1] 位置都不符合判断要求直接 dp[0] dp[1] 0;
填表顺序 从左往右返回表里所有的和。
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();vectorint dp(n);int count 0;for(int i 2; in; i){if(nums[i]-nums[i-1] nums[i-1]-nums[i-2])dp[i] dp[i-1]1;elsedp[i] 0;countdp[i];}return count;}
};最长湍流子数组 什么叫湍流子数组 像这样一升一降的就叫湍流子数组。 思路
1.经验题目要求
dp[i]表示以 i 位置为结尾的所有子数组中最长湍流子数组的长度。
对于本题如果只定一个状态数组是不够的因为我们只有区分了 i 位置是在增长还是在降低才能判断 i 1 位置是否能续上前面的波浪。所以我们需要定义两个状态数组分别表示以 i 结尾的在增长和降低的最长湍流子数组长度。 f[i] 表示以i 位置为结尾的所有子数组中最后呈现 “ 上升” 状态下的最长湍流数组的长度。 g[i] 表示以i 位置为结尾的所有子数组中最后呈现 “ 下降” 状态下的最长湍流数组的长度。
2.状态转移方程 初始化
单个 存在为1直接初始化全为1。
填表
从左往右两个表一起填写。
class Solution {
public:int maxTurbulenceSize(vectorint arr) {int n arr.size();vectorint f(n,1);auto g f;int ret 1;//最差情况是1ret写为1;for(int i 1; in; i){if(arr[i] arr[i-1]){f[i] g[i-1] 1;ret max(ret,f[i]);}else if(arr[i] arr[i-1]){g[i] f[i-1] 1;ret max(ret,g[i]);}}return ret;}
};环绕字符串中唯一的子字符串 思路
经验题目要求
dp[i]表示以 i 位置为结尾的所有字串中有多少个在 base 中出现过。
状态转移方程
如果长度为1就是本身字符串为1 长度大于1就要看s[i-1] 1是否等于s[i] ;(特殊情况是“za”的情况)
初始化
dp 表里面所有的值都初始化为1。因为每一个本身字符都在base中出现过。
填表
从左往右填表
去重操作
对于右边的例子abc 在 yzabczabc都出现过我们直接取以c结尾的最大的dp值就可以。
class Solution {
public:int findSubstringInWraproundString(string s) {int n s.size();vectorint dp(n,1);for(int i 1; in; i){if(s[i-1] 1 s[i] || (s[i-1] z s[i] a))dp[i] dp[i-1] 1;}int hash[26] {0};for(int i 0; in; i){hash[s[i] - a] max(hash[s[i]-a],dp[i]);}int sum 0;for(auto x : hash) sumx;return sum;}
};最长递增子序列 注意这里的子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路
经验题目要求
dp[i]表示以 i 位置为结尾的所有子序列中最长递增子序列的长度。
状态转移方程
如果长度为1就为1 长度大于1就要找nums[i] 大于 nums0j里面的子序列大于的话就为dp[i] dp[j] 1; 然后每一次找到dp[i] 里面的最大值并记录。 初始化
全部初始化为1因为长度为1dp[i] 为1.
填表
从左往右填表
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint dp(n,1);int ret 1;for(int i 1; in; i){for(int j 0; ji; j){if(nums[i] nums[j]){dp[i] max(dp[j] 1,dp[i]);}ret max(ret,dp[i]);}}return ret;}
};
