动态规划学习——等差子序列问题

目录

一,最长等差子序列

1.题目

2.题目接口

3.解题思路及其代码

二,等差序列的划分——子序列

1.题目

2.题目接口

3.解题思路及其代码


一,最长等差子序列

1.题目

给你一个整数数组 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:

输入: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]。

提示:

  • 2 <= nums.length <= 1000
  • 0 <= nums[i] <= 500

2.题目接口

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {}
};

3.解题思路及其代码

1.状态转移方程:

      每次做动态规划问题时都要先找到状态转移方程。在这道题里面,我们要找的是最长的等差子序列,那我们的状态转移方程必须就是二维的,为什么呢?因为要找等差序列我们首先得找到差值,一个数是构成不了差的只有两个数才行。现在我规定:dp[i][j]表示以arr[i]和arr[j]为结尾的等差子序列的最大长度,差值为arr[j]-arr[i]。那我们的dp[i][j] = dp[k][i]+1。其中dp[k][i]也表示以arr[k],arr[i]为结尾的最长的等差子序列。

2.初始化:

因为:

所以这道题的子序列最小长度就应该为2。所以在初始化时可以初始化为2。

3.优化:

   这道题的优化点还是在与元素与下标数组或者下标的绑定。

   先来看第一种:

   元素与下标数组的绑定(要与下标数组绑定的原因在于元素的出现次数会重复)

操作如下:

vector<vector<int>>dp(n,vector<int>(n,2));unordered_map<int,vector<int>>hash;for(int i = 0;i<n;i++) hash[nums[i]].push_back(i);

但是在这道题里面如果按照上面的方式绑定的话,就会面临一个超时的问题。如下:

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();int maxLenth = 2;vector<vector<int>>dp(n,vector<int>(n,2));unordered_map<int,vector<int>>hash;for(int i = 0;i<n;i++) hash[nums[i]].push_back(i);for(int j = 1;j<n;j++){for(int i = 0;i<j;i++){int num = 2*nums[i]-nums[j];for(auto e:hash[num]){if(e<i){dp[i][j] = dp[e][i]+1;}}maxLenth = max(maxLenth,dp[i][j]);}}return maxLenth;}
};

结果如下:

第二种优化方法:

元素与下标进行绑定。

前面说了,这道题里面是有重复元素的。如果直接初始化hash表就会出现下标覆盖的问题。所以在这里初始化下标就得来点技巧:

1.先初始化hash[nums[0]]  = 0;

 unordered_map<int,int>hash;hash[nums[0]] = 0;

2.先固定倒数第二个位置,遍历倒数第一个位置。(这样填表的目的就是为了在出现重复元素的时候能把离i最近的元素代入二不管其它元素)。

3.在遍历完i前面的元素以后才把hash[nums[i]]与i进行绑定。为什么呢?因为i下标肯定不是在i的前面的。并且,如果你在之前就将hash表就全部初始化了的话就会有覆盖问题。覆盖问题会导致在以i,j位置为结尾的等差序列本来是可以和前面的重复元素结成等差子序列的,但是因为下标覆盖问题导致我下标竟然比前面的元素小进而导致错误。

代码如下:

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();int maxLenth = 2;vector<vector<int>>dp(n,vector<int>(n,2));unordered_map<int,int>hash;hash[nums[0]] = 0;for(int i = 1;i<n;i++){for(int j= i+1;j<n;j++){int num = 2*nums[i]-nums[j];if(hash.count(num)){dp[i][j] = dp[hash[num]][i]+1;}maxLenth = max(maxLenth,dp[i][j]);}hash[nums[i]] = i;}return maxLenth;}
};

结果:

二,等差序列的划分——子序列

1.题目

给你一个整数数组 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

2.题目接口

 

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {}
};

3.解题思路及其代码

这道题的解题思路和前面的题目的思路差不多,只是dp[i][j]的所表示的意义不同了。这里的dp[i][j]表示以arr[i],arr[j]为结尾的子序列的个数。代码如下:

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();vector<vector<int>>dp(n,vector<int>(n));//这次表示的是以i,j下标为结尾的最大个数unordered_map<long long ,vector<long long>>hash;//使用long long是因为数据太大会溢出for(int i = 0;i<n;i++) hash[nums[i]].push_back(i);//元素+下标数组绑定是因为有重复元素。int count = 0;for(int j = 2;j<n;j++){for(int i= 1;i<j;i++){long long num =(long long) 2*nums[i] - (long long)nums[j];//使用long long是因为数据太大会溢出for(auto e:hash[num]){if(e<i){dp[i][j]+= dp[e][i]+1;//找前面的子序列的个数再加上自己这个新的。}else{break;//因为vector是尾插,所以出现重复元素时下标小的在前面。}}count+=dp[i][j];//统计所有等差子序列的个数}}return count;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/206137.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【实验】配置用户自动获取IPv6地址的案例

热门IT课程-试听视频文章浏览阅读49次。认证课程介绍&#xff1a;华为HCIA试听课程 &#xff1a; 华为HCIA试听课程&#xff1a;华为HCIA试听课程&#xff1a;华为HCIP试听课程&#xff1a;思科CCNA试听课程&#xff1a;思科CCNA试听课程&#xff1a;思科CCNA试听课程&#xff…

Open3D (C++) 计算两点云之间的最小距离

目录 一、算法原理二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理 Open3D中ComputePointCloudDistance函数提供了计算从源点云到目标点云的距离的方法,计算点云的距离。也就…

【论文精读】HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face

HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face 前言Abstract1 Introduction2 Related Works3 HuggingGPT3.1 Task PlanningSpecification-based InstructionDemonstration-based Parsing 3.2 Model SelectionIn-context Task-model Assignment 3…

MybatisPlus改造逻辑删除有多方便

MybatisPlus的逻辑删除可以有效保留历史数据。之前没有用逻辑删除的项目&#xff0c;想改造成逻辑删除总共需要几步&#xff1f; 答案&#xff1a;4步搞定 一、修改pom.xml的MybatisPlus版本&#xff08;注意版本兼容性&#xff09; <properties>...<!--<mybatis-…

【C语言期末不挂科——指针进阶篇】【上】

C语言进阶篇【上】 文章目录 C语言进阶篇【上】字符指针数组指针数组传参和指针传参  数组传参  一级指针传参  二级指针传参 前言&#xff1a; 我们在指针初阶篇学习了&#xff1a; 1、指针就是个变量&#xff0c;用来存放地址&#xff0c;地址唯一标识一块空间。 2、指…

tomcat-pass-getshell 弱口令 漏洞复现

tomcat-pass-getshell 弱口令 漏洞复现 名称: tomcat-pass-getshell 弱口令 描述: Tomcat是Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;的Jakarta 项目中的一个核心项目&#xff0c;由Apache、Sun 和其他一些公司及个人共同开发而成。 通过弱口令登…

基于GAN的多尺度门合并多模态MRI图像合成

Multi-Modal MRI Image Synthesis via GAN With Multi-Scale Gate Mergence 基于GAN的多尺度门合并多模态MRI图像合成背景贡献实验方法生成器gate mergence (GM) strategy&#xff08;门控融合策略&#xff09;判别器 损失函数Thinking 基于GAN的多尺度门合并多模态MRI图像合成…

notepad++ 插件JSONView安装

1&#xff0c;前提 开发过程中经常需要处理json格式语句&#xff0c;需要对json数据格式化处理&#xff0c;因为使用的是虚拟机内开发&#xff0c;所以没法连接外网&#xff0c;只能在本地电脑下载插件后&#xff0c;然后上传到虚拟机中&#xff0c;进行安装使用。 2&#xf…

SparkSQL之Optimized LogicalPlan生成过程

经过Analyzer的处理&#xff0c;Unresolved LogicalPlan已经解析成为Analyzed LogicalPlan。Analyzed LogicalPlan中自底向上节点分别对应Relation、Subquery、Filter和Project算子。   Analyzed LogicalPlan基本上是根据Unresolved LogicalPlan一对一转换过来的&#xff0c;…

Linux CentOS7 LVM

LVM&#xff08;Logical Volume Manger&#xff09;逻辑卷管理&#xff0c;Linux磁盘分区管理的一种机制&#xff0c;建立在硬盘和分区上的一个逻辑层&#xff0c;提高磁盘分区管理的灵活性。物理设备&#xff0c;是用于保留逻辑卷中所存储数据的存储设备。它们是块设备,可以是…

【算法萌新闯力扣】:旋转链表

力扣题目&#xff1a;旋转链表 开篇 今天是备战蓝桥杯的第25天和算法村开营第3天&#xff01;经过这3天的学习&#xff0c;感觉自己对链表的掌握程度大大地提升&#xff0c;尤其是在帮村里的同学讨论相关问题时。本篇文章&#xff0c;给大家带来一道旋转链表的题目&#xff0c…

XC1136 功率传输(PD) Sink控制器IC PD诱骗器芯片 输出可调 可支持多个

XC1136是一款功率传输(PD) Sink控制器IC。XC1136可以从符合Type-CPD协议的电源中请求最大或指定电压。输入电压范围:3V~28V支持USBType-C规范版本1.3支持USB PD2.0和PD3.0通讯协议&#xff0c;最多支持七个电源对象 该XC1136内置拉低电阻CC1和CC2引脚。当XC1136连接到T…

vuepress-----6、时间更新

# 6、时间更新 基于Git提交时间修改文字时间格式 moment # 最后更新时间 # 时间格式修改 下载库文件 yarn add momentconst moment require(moment); moment.locale(zh-cn)module.exports {themeConfig: {lastUpdated: 更新时间,},plugins: [[vuepress/last-updated,{trans…

Vue大屏自适应终极解决方案

v-scale-screenv-scale-screen是一个大屏自适应组件&#xff0c;在实际业务中&#xff0c;我们常用图表来做数据统计&#xff0c;数据展示&#xff0c;数据可视化等比较直观的方式来达到一目了然的数据查看&#xff0c;但在大屏开发过程中&#xff0c;常会因为适配不同屏幕而感…

作为搜索引擎,TikTok超过了谷歌

Rise at Seven通过分析不同行业的数千个关键词进行了研究&#xff0c;突出了用户在TikTok上搜索的100个单词和短语&#xff0c;比在谷歌上搜索的更多。 虽然承认“near me”和“what’s on”的搜索查询仍然是谷歌上最突出的搜索查询&#xff0c;但Rise at Seven得出的结论是&a…

MySQL之redo log

聊聊REDO LOG 为什么需要redolog&#xff1f; 那redolog主要是为了保证数据的持久化&#xff0c;我们知道innodb存储引擎中数据是以页为单位进行存储&#xff0c;每一个页中有很多行记录来存储数据&#xff0c;我们的数据最终是要持久化到硬盘中&#xff0c;那如果我们每进行…

Unity技美35——再URP管线环境下,配置post后期效果插件(post processing)

前两年在我的unity文章第10篇写过&#xff0c;后效滤镜的使用&#xff0c;那时候大部分项目用的还是unity的基础管线&#xff0c;stander管线。 但是现在随着unity的发展&#xff0c;大部分项目都用了URO管线&#xff0c;甚至很多PC端用的都是高效果的HDRP管线&#xff0c;这就…

re:Invent 构建未来:云计算生成式 AI 诞生科技新局面

文章目录 前言一、亚马逊云科技re:Invent二、亚马逊云科技re:Invent 2023 Adam Selipsky 主题演讲三、由亚马逊云科技思想领袖主持的深度探讨四、云计算是什么五、云计算机的主要服务模型六、云计算机的用途七、重构生成式AI 前言 活动介绍 回顾过去十几年&#xff0c;云计算已…

【从浅识到熟知Linux】基本指令之基本权限

&#x1f388;归属专栏&#xff1a;从浅学到熟知Linux &#x1f697;个人主页&#xff1a;Jammingpro &#x1f41f;每日一句&#xff1a;用博客整理整理之前学过的知识&#xff0c;是个不错的选择。 文章前言&#xff1a;本文介绍Linux中的基本权限及相关指令用法并给出示例和…

基于深度学习的表情动作单元识别综述

论文标题&#xff1a;基于深度学习的表情动作单元识别综述 作者&#xff1a;邵志文1&#xff0c;2&#xff0c;周 勇1&#xff0c;2&#xff0c;谭 鑫3&#xff0c;马利庄3&#xff0c;4&#xff0c;刘 兵1&#xff0c;2&#xff0c;姚 睿1&#xff0c;2 发表日期&#xff1a…