【动态规划】C++算法:446等差数列划分 II - 子序列

简介: 【动态规划】C++算法:446等差数列划分 II - 子序列

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

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;

};


相关文章
|
18天前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
231 1
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
114 2
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
86 0
|
5月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
146 17
|
4月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
92 0
|
6月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
119 4
|
7月前
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
118 8
|
10天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
12天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
11天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)

热门文章

最新文章