【算法挨揍日记】day33——1027. 最长等差数列、446. 等差数列划分 II – 子序列

1027. 最长等差数列 

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;
    }
};