网站建设与制作模板,汽车网站模块,可以随意建国际商城的网站吗,无极电影网评1027. 最长等差数列
https://leetcode.cn/problems/longest-arithmetic-subsequence/
给你一个整数数组 nums#xff0c;返回 nums 中最长等差子序列的长度。
回想一下#xff0c;nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] #xff0c;且 0 i1 返回 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]。
1.状态表示* 我们先试着定义一个状态转移数组 dp[i] 表⽰以 i 位置元素为结尾的「所有⼦序列」中最⻓的等差序列的⻓度。 但是这⾥有⼀个⾮常致命的问题那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程因此我们定义的状态表⽰需要能够确定⼀个等差序列 dp[i][j] 表⽰以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中最⻓的等差序列的⻓度。
2.状态转移方程 设 nums[i] b, nums[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
优化 ⼀边 dp ⼀边保存。这种⽅式我们仅需保存最近的元素的下标不⽤保存下标数组。但是⽤这种⽅法的话我们在遍历顺序那⾥先固定倒数第⼆个数再遍历倒数第⼀个数。这样就可以在 i 使⽤完时候将 nums[i] 扔到哈希表中。
3. 初始化 根据实际情况可以将所有位置初始化为 2 。
4. 填表顺序 a. 先固定倒数第⼆个数 b. 然后枚举倒数第⼀个数。
5. 返回值 由于不知道最⻓的结尾在哪⾥因此返回 dp 表中的最⼤值。
代码 int longestArithSeqLength(vectorint nums) {int nnums.size();unordered_mapint,int hash;hash[nums[0]]0;//表示的是以 ij 为结尾的最长的等差子序列的长度int Max2;vectorvectorint dp(n,vectorint(n,2));for(int i0;in;i)//先固定倒数第二个位置{for(int ji1;jn;j)//在固定倒数第一个位置{int a2*nums[i]-nums[j];if(hash.count(a)hash[a]i)dp[i][j]dp[hash[a]][i]1;Maxmax(Max,dp[i][j]);}hash[nums[i]]i;}return Max;}446. 等差数列划分 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.状态表示* 我们先试着定义一个状态转移数组 dp[i] 表⽰以 i 位置元素为结尾的「所有⼦序列」中最⻓的等差序列的⻓度。 但是这⾥有⼀个⾮常致命的问题那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程因此我们定义的状态表⽰需要能够确定⼀个等差序列 dp[i][j] 表⽰以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中等差⼦序列的个数。
2.状态转移方程 设 nums[i] b, nums[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 为结尾b. 因为 a 可能有很多个我们需要全部累加起来
综上 dp[i][j] dp[k][i] 1 。
优化 优化点我们发现在状态转移⽅程中我们需要确定 a 元素的下标。因此我们可以在 dp 之前将 所有元素 下标数组绑定在⼀起放到哈希表中。这⾥为何要保存下标数组是因为我们要统计个 数所有的下标都需要统计。 3. 初始化 刚开始是没有等差数列的因此初始化 dp 表为 0 4. 填表顺序 a. 先固定倒数第⼆个数 b. 然后枚举倒数第⼀个数。
5. 返回值 我们要统计所有的等差⼦序列因此返回 dp 表中所有元素的和。
代码
int numberOfArithmeticSlices(vectorint nums) {int nnums.size();unordered_maplong long,vectorint hash;for(int i0;in;i){hash[nums[i]].push_back(i);}int sum0;vectorvectorint dp(n,vectorint(n));for(int j2;jn;j){for(int i1;ij;i){long long a(long long)2*nums[i]-nums[j];if(hash.count(a)){for(auto e:hash[a]){if(ei) { dp[i][j]dp[e][i]1;}else break;}}sumdp[i][j];}}return sum;}
