公需道德与能力建设培训网站,wordpress七牛云缩略图,团智慧团建登录入口,网站怎样做快照算法沉淀——动态规划之子序列问题 01.最长定差子序列02.最长的斐波那契子序列的长度03.最长等差数列04.等差数列划分 II - 子序列 01.最长定差子序列
题目链接#xff1a;https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/
给你一个整数数… 算法沉淀——动态规划之子序列问题 01.最长定差子序列02.最长的斐波那契子序列的长度03.最长等差数列04.等差数列划分 II - 子序列 01.最长定差子序列
题目链接https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/
给你一个整数数组 arr 和一个整数 difference请你找出并返回 arr 中最长等差子序列的长度该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1
输入arr [1,2,3,4], difference 1
输出4
解释最长的等差子序列是 [1,2,3,4]。示例 2
输入arr [1,3,5,7], difference 1
输出1
解释最长的等差子序列是任意单个元素。示例 3
输入arr [1,5,7,8,5,3,4,2,1], difference -2
输出4
解释最长的等差子序列是 [7,5,3,1]。 提示
1 arr.length 105-104 arr[i], difference 104
思路
状态表达 定义动态规划数组 dp其中 dp[i] 表示以第 i 个位置的元素为结尾的所有子序列中最长的等差子序列的长度。状态转移方程 对于 dp[i]上一个定差子序列的取值定为 arr[i] - difference。只要找到以上一个数为结尾的定差子序列长度的 dp[arr[i] - difference]然后加上 1就是以 i 为结尾的定差子序列的长度。这里可以使用哈希表进行优化将元素和 dp[j] 绑定放入哈希表中。初始化 刚开始的时候需要把第一个元素放进哈希表中即 hash[arr[0]] 1。填表顺序 根据状态转移方程填表顺序是从左往右。返回值 根据状态表达返回整个 dp 数组中的最大值。
代码
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {unordered_mapint,int hash;hash[arr[0]]1;int ret1;for(int i1;iarr.size();i){hash[arr[i]]hash[arr[i]-difference]1;retmax(ret,hash[arr[i]]);}return ret;}
};02.最长的斐波那契子序列的长度
题目链接https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
如果序列 X_1, X_2, ..., X_n 满足下列条件就说它是 斐波那契式 的
n 3对于所有 i 2 n都有 X_i X_{i1} X_{i2}
给定一个严格递增的正整数数组形成序列 arr 找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在返回 0 。
回想一下子序列是从原序列 arr 中派生出来的它从 arr 中删掉任意数量的元素也可以不删而不改变其余元素的顺序。例如 [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列
示例 1
输入: arr [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。示例 2
输入: arr [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。提示
3 arr.length 10001 arr[i] arr[i 1] 10^9
思路
状态表达 定义动态规划数组 dp其中 dp[j][i] 表示以第 j 位置以及第 i 位置的元素为结尾的所有的子序列中最长的斐波那契子序列的长度。状态转移方程 设 nums[j] bnums[i] c那么这个序列的前一个元素就是 a c - b。根据 a 的情况讨论 如果 a 存在下标为 k并且 a b那么 dp[j][i] dp[k][j] 1如果 a 存在但是 b a c那么 dp[j][i] 2如果 a 不存在那么 dp[j][i] 2。 优化点 在状态转移方程中需要确定 a 元素的下标可以在填表之前将所有的「元素 下标」绑定在一起放到哈希表中。初始化 将表里面的值都初始化为 2。填表顺序 先固定最后一个数然后枚举倒数第二个数。 返回值 返回 dp 表中的最大值 ret。但是 ret 可能小于 3小于 3 说明不存在需要判断一下。
代码
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {int narr.size();unordered_mapint,int hash;for(int i0;in;i) hash[arr[i]]i;vectorvectorint dp(n,vectorint(n,2));int ret2;for(int i2;in;i){for(int j1;ji;j){int xarr[i]-arr[j];if(xarr[j]hash.count(x))dp[j][i] dp[hash[x]][j]1;ret max(ret,dp[j][i]);}}return ret3?0:ret;}
};03.最长等差数列
题目链接https://leetcode.cn/problems/longest-arithmetic-subsequence/
给你一个整数数组 nums返回 nums 中最长等差子序列的长度。
回想一下nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] 且 0 i1 i2 ... ik nums.length - 1。并且如果 seq[i1] - seq[i]( 0 i seq.length - 1) 的值都相同那么序列 seq 是等差的。
示例 1
输入nums [3,6,9,12]
输出4
解释
整个数组是公差为 3 的等差数列。示例 2
输入nums [9,4,7,2,10]
输出3
解释
最长的等差子序列是 [4,7,10]。示例 3
输入nums [20,1,15,3,10,5,8]
输出4
解释
最长的等差子序列是 [20,15,10,5]。 提示
2 nums.length 10000 nums[i] 500
思路
状态表达 定义动态规划数组 dp其中 dp[i][j] 表示以第 i 位置以及第 j 位置的元素为结尾的所有的子序列中最长的等差序列的长度。状态转移方程 设 nums[i] bnums[j] c那么这个序列的前一个元素就是 a 2 * b - c。根据 a 的情况讨论 如果 a 存在下标为 k并且 a b那么我们需要以 k 位置以及 i 位置元素为结尾的最长等差序列的长度然后再加上 j 位置的元素即可。于是 dp[i][j] dp[k][i] 1。这里因为会有许多个 k我们仅需离 i 最近的 k 即可。因此任何最长的都可以以 k 为结尾如果 a 存在但是 b a c那么 dp[i][j] 2如果 a 不存在那么 dp[i][j] 2。 优化点 在状态转移方程中需要确定 a 元素的下标。可以一边动态规划一边保存最近的元素的下标不用保存下标数组。遍历的时候先固定倒数第二个数再遍历倒数第一个数。这样可以在 i 使用完时候将 nums[i] 扔到哈希表中。初始化 将表里面的值都初始化为 2。填表顺序 先固定倒数第二个数然后枚举倒数第一个数。 返回值 返回 dp 表中的最大值。
代码
class Solution {
public:int longestArithSeqLength(vectorint nums) {unordered_mapint,int hash;hash[nums[0]]0;int nnums.size();vectorvectorint dp(n,vectorint(n,2));int ret2;for(int i1;in;i){for(int ji1;jn;j){int x2*nums[i]-nums[j];if(hash.count(x)) dp[i][j] dp[hash[x]][i] 1;retmax(ret,dp[i][j]);}hash[nums[i]]i;}return ret;}
};04.等差数列划分 II - 子序列
题目链接https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/
给你一个整数数组 nums 返回 nums 中所有 等差子序列 的数目。
如果一个序列中 至少有三个元素 并且任意两个相邻元素之差相同则称该序列为等差序列。
例如[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。再例如[1, 1, 2, 5, 7] 不是等差序列。
数组中的子序列是从数组中删除一些元素也可能不删除得到的一个序列。
例如[2,5,10] 是 [1,2,1,***2***,4,1,***5\***,***10***] 的一个子序列。
题目数据保证答案是一个 32-bit 整数
示例 1
输入nums [2,4,6,8,10]
输出7
解释所有的等差子序列为
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]示例 2
输入nums [7,7,7,7,7]
输出16
解释数组中的任意子序列都是等差子序列。提示
1 nums.length 1000-231 nums[i] 231 - 1
思路
状态表达 定义动态规划数组 dp其中 dp[i][j] 表示以第 i 位置以及第 j 位置的元素为结尾的所有的子序列中等差子序列的个数。状态转移方程 设 nums[i] bnums[j] c那么这个序列的前一个元素就是 a 2 * b - c。根据 a 的情况讨论 如果 a 存在下标为 k并且 a b那么以 k 元素以及 i 元素结尾的等差序列的个数为 dp[k][i]在这些子序列的后面加上 j 位置的元素依旧是等差序列。但是这里会多出来一个以 k, i, j 位置的元素组成的新的等差序列因此 dp[i][j] dp[k][i] 1因为 a 可能有很多个需要全部累加起来。 优化点 在状态转移方程中需要确定 a 元素的下标。因此在 dp 之前将所有元素和下标数组绑定在一起放到哈希表中。这里保存下标数组是因为需要统计个数。初始化 刚开始是没有等差数列的因此初始化 dp 表为 0。填表顺序 先固定倒数第一个数然后枚举倒数第二个数。 返回值 统计所有的等差子序列返回 dp 表中所有元素的和。
代码
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int nnums.size();unordered_maplong long,vectorint hash;for(int i0;in;i) hash[nums[i]].push_back(i);vectorvectorint dp(n,vectorint(n));int sum0;for(int j2;jn;j){for(int i1;ij;i){long long x(long long)nums[i]*2-nums[j];if(hash.count(x)) for(int k:hash[x])if(ki) dp[i][j]dp[k][i]1;sumdp[i][j];}}return sum;}
};
