作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
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:
输入: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
动态规划
时间复杂度😮(nn)
空间复杂度😮(nn)
变量解析
长度大于2的称为等差子序列,长度等于2的不妨称为“准等差”。
mSubCount1 | mSubCount1[i][sub]表示以nums[i]结尾,差为sub的“准等差”数量。 |
mSubCount2 | mSubCount2[i][sub]表示以nums[i]结尾,差为sub的等差数列的数量。 |
动态规划的细节,方便检查
两层循环,分别枚举等差数列的最后一个元素和倒数第二个元素。
动态规划的状态表示 | mSubCount1 和mSubCount2 |
动态规划的转移方程 | mSubCount2 [i][sub] +=mSubCount1 [j][sub]+ mSubCount2 [j][sub] mSubCount1[i][sub]++ |
动态规划的初始状态 | 空 |
动态规划的填表顺序 | i和j都是从小到大处理,确保动态规划的无后效性 |
动态规划的返回值 | Sumi,submSubCount2[i][sub] |
代码
核心代码
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
m_c = nums.size();
vector<unordered_map<long long, int>> mSubCount1(m_c), mSubCount2(m_c);
int iRet = 0;
for (int i = 1; i < m_c; i++)
{
for (int j = 0; j < i; j++)
{
const long long sub = (long long)nums[i] - nums[j];
if (mSubCount2[j].count(sub))
{
mSubCount2[i][sub] += mSubCount2[j][sub];
}
if (mSubCount1[j].count(sub))
{
mSubCount2[i][sub] += mSubCount1[j][sub];
}
mSubCount1[i][sub]++;
}
for (const auto& [_tmp,cnt] : mSubCount2[i])
{
iRet += cnt;
}
}
return iRet;
}
int m_c;
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<int> nums;
{
Solution sln;
nums = { 1,1,1,1 };
auto res = sln.numberOfArithmeticSlices(nums);
Assert(5, res);
}
{
Solution sln;
nums = { 2, 4, 6, 8, 10 };
auto res = sln.numberOfArithmeticSlices(nums);
Assert(7, res);
}
{
Solution sln;
nums = { 7,7,7,7,7 };
auto res = sln.numberOfArithmeticSlices(nums);
Assert(16, res);
}
{
Solution sln;
nums = { 0, 2000000000, -294967296 };
auto res = sln.numberOfArithmeticSlices(nums);
Assert(16, res);
}
}
可以优化掉一个变量
class Solution {
public:
int numberOfArithmeticSlices(vector& nums) {
m_c = nums.size();
vector<unordered_map<long long, int>> mSubCount(m_c);
int iRet = 0;
for (int i = 1; i < m_c; i++)
{
for (int j = 0; j < i; j++)
{
const long long sub = (long long)nums[i] - nums[j];
if (mSubCount[j].count(sub))
{
mSubCount[i][sub] += mSubCount[j][sub];
iRet += mSubCount[j][sub];
}
mSubCount[i][sub]++;
}
}
return iRet;
}
int m_c;
};
2023年1月版
class Solution {
public:
int numberOfArithmeticSlices(vector& nums) {
m_c = nums.size();
vector<std::unordered_map<long long, int>> dp(m_c);
int iRet = 0;
for (int i = 0; i < m_c; i++)
{
for (int j = 0; j < i; j++)
{
long long tmp = 1LL * nums[i] - nums[j];
auto it = dp[j].find(tmp);
int iNum = (dp[j].end() == it) ? 0 : it->second ;
iRet += iNum;
dp[i][tmp] += iNum + 1;
}
}
return iRet;
}
int m_c;
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+
+17**
如无特殊说明,本算法用**C++**实现。文章来源:https://www.toymoban.com/news/detail-778939.html
文章来源地址https://www.toymoban.com/news/detail-778939.html
到了这里,关于【动态规划】C++算法:446等差数列划分 II - 子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!