【算法挨揍日记】day33——1027. 最长等差数列、446. 等差数列划分 II - 子序列-CSDN博客
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
1027. 最长等差数列
题目描述
给你一个整数数组 nums返回 nums 中最长等差子序列的长度。
回想一下nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] 且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同那么序列 seq 是等差的。
解题思路
算法思路
1.
状态表⽰
对于线性
dp
我们可以⽤「经验 + 题⽬要求」来定义状态表⽰
i.
以某个位置为结尾巴拉巴拉
ii.
以某个位置为起点巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰
dp[i]
表⽰以
i
位置元素为结尾的「所有⼦序列」中最⻓的等差序列的⻓度。
但是这⾥有⼀个⾮常致命的问题那就是我们⽆法确定
i
结尾的等差序列的样⼦。这样就会导致
我们⽆法推导状态转移⽅程因此我们定义的状态表⽰需要能够确定⼀个等差序列。
根据等差序列的特性我们仅需知道序列⾥⾯的最后两个元素就可以确定这个序列的样⼦。因
此我们修改我们的状态表⽰为
dp[i][j]
表⽰以
i
位置以及
j
位置的元素为结尾的所有的⼦序列中最⻓的等差序列的
⻓度。规定⼀下
i < j
。
2.
状态转移⽅程
设
nums[i] = b, nums[j] = c
那么这个序列的前⼀个元素就是
a = 2 * b - c
。我们
根据
a
的情况讨论
a.
a
存在下标为
k
并且
a < b
此时我们需要以
k
位置以及
i
位置元素为结尾的最
⻓等差序列的⻓度然后再加上
j
位置的元素即可。于是
dp[i][j] = dp[k][i] +
1
。这⾥因为会有许多个
k
我们仅需离
i
最近的
k
即可。因此任何最⻓的都可以以
k
为结尾
b.
a
存在但是
b < a < c
此时只能两个元素⾃⼰玩了
dp[i][j] = 2
c.
a
不存在此时依旧只能两个元素⾃⼰玩了
dp[i][j] = 2
。
综上状态转移⽅程分情况讨论即可。
优化点我们发现在状态转移⽅程中我们需要确定
a
元素的下标。因此我们可以将所有的元素 +
下标绑定在⼀起放到哈希表中这⾥有两种策略
a.
在
dp
之前放⼊哈希表中。这是可以的但是需要将下标形成⼀个数组放进哈希表中。这样
时间复杂度较⾼我帮⼤家试过了超时。
b.
⼀边
dp
⼀边保存。这种⽅式我们仅需保存最近的元素的下标不⽤保存下标数组。但是
⽤这种⽅法的话我们在遍历顺序那⾥先固定倒数第⼆个数再遍历倒数第⼀个数。这样就
可以在
i
使⽤完时候将
nums[i]
扔到哈希表中。
3.
初始化
根据实际情况可以将所有位置初始化为
2
。
4.
填表顺序
a.
先固定倒数第⼆个数
b.
然后枚举倒数第⼀个数。
5.
返回值
由于不知道最⻓的结尾在哪⾥因此返回
dp
表中的最⼤值。
解题代码
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n=nums.size();
vector<vector<int>>dp(n,vector<int>(n,2));
unordered_map<int,int>hash;
int ret=2;
hash[nums[0]]=0;
for(int i=1;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
int a=2*nums[i]-nums[j];
// int k=hash.count(a);
if(hash.count(a))
{
dp[i][j]=dp[hash[a]][i]+1;
}
ret=max(ret,dp[i][j]);
}
hash[nums[i]]=i;
}
return ret;
}
};446. 等差数列划分 II - 子序列
题目描述
给你一个整数数组 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.
状态表⽰
对于线性
dp
我们可以⽤「经验 + 题⽬要求」来定义状态表⽰
i.
以某个位置为结尾巴拉巴拉
ii.
以某个位置为起点巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰
dp[i]
表⽰以
i
位置元素为结尾的「所有⼦序列」中等差⼦序列的个数。
但是这⾥有⼀个⾮常致命的问题那就是我们⽆法确定
i
结尾的等差序列的样⼦。这样就会导致
我们⽆法推导状态转移⽅程因此我们定义的状态表⽰需要能够确定⼀个等差序列。
根据等差序列的特性我们仅需知道序列⾥⾯的最后两个元素就可以确定这个序列的样⼦。因
此我们修改我们的状态表⽰为
dp[i][j]
表⽰以
i
位置以及
j
位置的元素为结尾的所有的⼦序列中等差⼦序列的个
数。规定⼀下
i < j
。
2.
状态转移⽅程
设
nums[i] = b, nums[j] = c
那么这个序列的前⼀个元素就是
a = 2 * b - c
。我们
根据
a
的情况讨论
a.
a
存在下标为
k
并且
a < b
此时我们知道以
k
元素以及
i
元素结尾的等差序列
的个数
dp[k][i]
在这些⼦序列的后⾯加上
j
位置的元素依旧是等差序列。但是这⾥会多
出来⼀个以
k, i, j
位置的元素组成的新的等差序列因此
dp[i][j] = dp[k][i]
+ 1
b.
因为
a
可能有很多个我们需要全部累加起来。
综上
dp[i][j] += dp[k][i] + 1
。
优化点我们发现在状态转移⽅程中我们需要确定
a
元素的下标。因此我们可以在 dp 之前将
所有元素 + 下标数组绑定在⼀起放到哈希表中。这⾥为何要保存下标数组是因为我们要统计个
数所有的下标都需要统计。
3.
初始化
刚开始是没有等差数列的因此初始化
dp
表为
0
。
4.
填表顺序
a.
先固定倒数第⼀个数
b.
然后枚举倒数第⼆个数。
5.
返回值
我们要统计所有的等差⼦序列因此返回
dp
表中所有元素的和。
解题代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n=nums.size();
vector<vector<int>>dp(n,vector(n,0));
unordered_map<long long,vector<int>>hash;
hash[nums[0]].push_back(0);
int sum=0;
for(int i=1;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
long long a=2*(long long)nums[i]-nums[j];
if(hash.count(a))
{
int length=hash[a].size();
for(int k=0;k<length;k++)
{
dp[i][j]+=dp[hash[a][k]][i]+1;
}
}
sum+=dp[i][j];
}
hash[nums[i]].push_back(i);
}
return sum;
}
};