【动态规划刷题 16】最长等差数列 (有难度) 等差数列划分 II - 子序列
1027. 最长等差数列
https://leetcode.cn/problems/longest-arithmetic-subsequence/
给你一个整数数组 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]。
1.状态表示*
我们先试着定义一个状态转移数组:
dp[i] 表⽰:以 i 位置元素为结尾的「所有⼦序列」中,最⻓的等差序列的⻓度。
但是这⾥有⼀个⾮常致命的问题,那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程,因此我们定义的状态表⽰需要能够确定⼀个等差序列:
dp[i][j] 表⽰:以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中,最⻓的等差序列的⻓度。
2.状态转移方程
设 nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们
根据 a 的情况讨论:
- a 存在,下标为 k ,并且 a < b :此时我们需要以 k 位置以及 i 位置元素为结尾的最⻓等差序列的⻓度,然后再加上 j 位置的元素即可。于是
dp[i][j] = dp[k][i] +1
。这⾥因为会有许多个 k ,我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k 为结尾; - a 存在,但是 b < a < c :此时只能两个元素⾃⼰玩了, dp[i][j] = 2 ;
- a 不存在:此时依旧只能两个元素⾃⼰玩了, dp[i][j] = 2 ;
优化:
⼀边 dp ,⼀边保存。这种⽅式,我们仅需保存最近的元素的下标,不⽤保存下标数组。但是⽤这种⽅法的话,我们在遍历顺序那⾥,先固定倒数第⼆个数,再遍历倒数第⼀个数。这样就可以在 i 使⽤完时候,将 nums[i] 扔到哈希表中。
3. 初始化
根据实际情况,可以将所有位置初始化为 2 。
4. 填表顺序
a. 先固定倒数第⼆个数;
b. 然后枚举倒数第⼀个数。
5. 返回值
由于不知道最⻓的结尾在哪⾥,因此返回 dp 表中的最⼤值。
代码:
int longestArithSeqLength(vector<int>& nums) {int n=nums.size();unordered_map<int,int> hash;hash[nums[0]]=0;//表示的是以 i,j 为结尾的,最长的等差子序列的长度int Max=2;vector<vector<int>> dp(n,vector<int>(n,2));for(int i=0;i<n;i++)//先固定倒数第二个位置{for(int j=i+1;j<n;j++)//在固定倒数第一个位置{int a=2*nums[i]-nums[j];if(hash.count(a)&&hash[a]<i)dp[i][j]=dp[hash[a]][i]+1;Max=max(Max,dp[i][j]);}hash[nums[i]]=i;}return Max;}
446. 等差数列划分 II - 子序列
https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/
给你一个整数数组 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.状态表示*
我们先试着定义一个状态转移数组:
dp[i] 表⽰:以 i 位置元素为结尾的「所有⼦序列」中,最⻓的等差序列的⻓度。
但是这⾥有⼀个⾮常致命的问题,那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程,因此我们定义的状态表⽰需要能够确定⼀个等差序列:
dp[i][j] 表⽰:以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中,等差⼦序列的个数。
2.状态转移方程
设 nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们
根据 a 的情况讨论:
- a 存在,下标为 k ,并且 a < b :此时我们需要以 k 位置以及 i 位置元素为结尾的最⻓等差序列的⻓度,然后再加上 j 位置的元素即可。于是
dp[i][j] = dp[k][i] +1
。这⾥因为会有许多个 k ,我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k 为结尾; - b. 因为 a 可能有很多个,我们需要全部累加起来
综上, dp[i][j] += dp[k][i] + 1 。
优化:
优化点:我们发现,在状态转移⽅程中,我们需要确定 a 元素的下标。因此我们可以在 dp 之前,将
所有元素 +下标数组绑定在⼀起,放到哈希表中。这⾥为何要保存下标数组,是因为我们要统计个
数,所有的下标都需要统计。
3. 初始化
刚开始是没有等差数列的,因此初始化 dp 表为 0
4. 填表顺序
a. 先固定倒数第⼆个数;
b. 然后枚举倒数第⼀个数。
5. 返回值
我们要统计所有的等差⼦序列,因此返回 dp 表中所有元素的和。
代码:
int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();unordered_map<long long,vector<int>> hash;for(int i=0;i<n;i++){hash[nums[i]].push_back(i);}int sum=0;vector<vector<int>> dp(n,vector<int>(n));for(int j=2;j<n;j++){for(int i=1;i<j;i++){long long a=(long long)2*nums[i]-nums[j];if(hash.count(a)){for(auto e:hash[a]){if(e<i) { dp[i][j]+=dp[e][i]+1;}else break;}}sum+=dp[i][j];}}return sum;}
相关文章:

【动态规划刷题 16】最长等差数列 (有难度) 等差数列划分 II - 子序列
1027. 最长等差数列 https://leetcode.cn/problems/longest-arithmetic-subsequence/ 给你一个整数数组 nums,返回 nums 中最长等差子序列的长度。 回想一下,nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] ,且 0 < i1 <…...

【postgresql】替换 mysql 中的ifnull()
数据库由mysql 迁移到postgresql,程序在执行查询时候报错。 HINT: No function matches the given name and argument types. You might need to add explicit type casts. CONTEXT: referenced column: ifnull 具体SQL: SELECT ifnull(phone,) FROM c_user p…...
单例模式(懒汉式,饿汉式,变体)
单例模式,用于确保一个类只有一个实例,并提供一个全局访问点以访问该实例。 饿汉式(Eager Initialization) 程序启动时就创建实例 #include <iostream> class SingletonEager { private:static SingletonEager* instanc…...
Java Lambda表达式:简洁且强大的函数式编程工具
Lambda表达式是Java 8及以后版本中引入的一种函数式编程特性。它是一种匿名函数,允许开发人员以简洁和易读的方式编写代码,并且可以作为参数传递给方法或存储在变量中。Lambda表达式的基本语法如下:(parameters) -> expression,…...

开源框架中的责任链模式实践
作者:vivo 互联网服务器团队-Wang Zhi 责任链模式作为常用的设计模式而被大家熟知和使用。本文介绍责任链的常见实现方式,并结合开源框架如Dubbo、Sentinel等进行延伸探讨。 一、责任链介绍 在GoF 的《设计模式》一书中对责任链模定义的:将…...

智能配电系统:保障电力运行安全、可控与高效
智能配电系统是一种先进的电力分配技术,它通过智能化、数字化和网络化等方式,有效地保障了电力运行的安全、可控和高效。 力安科技智能配电系统是在配电室(含高压柜、变压器、低压柜)、箱式变电站、配电箱及动力柜(…...
MySQL学习系列(11)-每天学习10个知识
目录 1. 数据库设计的关键因素2. 使用存储过程和函数来提高性能和可重用性3. MySQL性能优化4. 使用视图简化查询和提供数据安全性5. 数据库备份和恢复策略的重要性和实践经验6. 在分布式系统中保证数据一致性和可用性7. 理解MySQL的复制和其在实际应用中的作用8. 使用游标进行分…...

如何通过Gunicorn和Niginx部署Django
本文主要介绍如何配置Niginx加载Django的静态资源文件,也就是Static 1、首先需要将Django项目中的Settings.py 文件中的两个参数做以下设置: STATIC_URL /static/ STATIC_ROOT os.path.join(BASE_DIR, static) 然后在宝塔面板中执行python manage.…...

C语言 cortex-A7核UART总线实验
一、C 1)uart4.h #ifndef __UART4_H__ #define __UART4_H__ #include "stm32mp1xx_rcc.h" #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_uart.h&quo…...
asp.net C#免费反编译工具ILSpy
在维护一个没有源码的C#项目,只能反编译了。 项目主页 https://github.com/icsharpcode/ILSpy 使用方法 中文界面使用简单,把你要反编译的dll拖过去就可以了。好使!!!...

演讲实录:DataFun 垂直开发者社区基于指标平台自主洞察北极星指标
在7月14日举办的 Kyligence 用户大会的数智新应用论坛上,DataFun COO 杜颖女士为大家带来了《垂直开发者社区基于指标平台自主洞察北极星指标》的主题演讲。接下来,我们一起看看 DataFun 如何在没有专门的 IT 团队的情况下,实现对北极星指标的…...

ffmpeg编译 Error: operand type mismatch for `shr‘
错误如下: D:\msys2\tmp\ccUxvBjQ.s: Assembler messages: D:\msys2\tmp\ccUxvBjQ.s:345: Error: operand type mismatch for shr D:\msys2\tmp\ccUxvBjQ.s:410: Error: operand type mismatch for shr D:\msys2\tmp\ccUxvBjQ.s:470: Error: operand type mismatch…...

【Windows Server 2012 R2搭建FTP站点】
打开服务器管理器——添加角色和功能 下一步 下一步 下一步 选择FTP服务器,勾上FTP服务和FTP扩展,点击下一步 安装 安装完成关闭 打开我们的IIS服务器 在WIN-XXX主页可以看到我们的FTP相关菜单 右键WIN-XXXX主页,添加FTP站点 输入站点名称-FT…...

python教程:使用gevent实现高并发并限制最大并发数
嗨喽~大家好呀,这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 import time import gevent from gevent.pool import Pool from gevent import monkey # 一,定义最大并发数 p Pool(20) # 二,导入gevent…...
借助reCAPTCHA实现JavaScript验证码功能
前言 验证码(CAPTCHA)是一种常见的安全验证机制,常用于区分真实用户和机器人。使用验证码可以有效防止恶意登录、自动注册或者密码爆破等攻击。本文将借助reCAPTCHA第三方库来实现JavaScript验证码功能。 验证码的原理 验证码的核心思想是要…...

监控数据的采集方式及原理
采集方法使用频率从高到低依次是读取 /proc目录、执行命令行工具、远程黑盒探测、拉取特定协议的数据、连接到目标对象执行命令、代码埋点、日志解析。 读取 /proc目录 /proc是一个位于内存中的伪文件系统,而在该目录下保存的不是真正的文件和目录,而是…...

Vue路由与node.js环境搭建
目录 前言 一.Vue路由 1.什么是spa 1.1简介 1.2 spa的特点 1.3 spa的优势以及未来的挑战 2.路由的使用 2.1 导入JS依赖 2.2 定义两个组件 2.3 定义组件与路径对应关系 2.4 通过路由关系获取路由对象 2.5 将对象挂载到vue实例中 2.6 定义触发路由事件的按钮 2.7 定…...

腾讯云16核服务器性能测评_轻量和CVM配置大全
腾讯云16核服务器配置大全,CVM云服务器可选择标准型S6、标准型SA3、计算型C6或标准型S5等,目前标准型S5云服务器有优惠活动,性价比高,计算型C6云服务器16核性能更高,轻量16核32G28M带宽优惠价3468元15个月,…...

Postman应用——下载注册和登录
文章目录 下载安装注册登录注册账号登录账号 下载安装 Postman下载:https://www.postman.com/ 访问链接后,进入首页,根据自己的操作系统下载对应的版本。 找到下载到的目录直接双击.exe文件,会默认安装在C盘,安装完会…...
uni-app混合开发 navigateTo、reLaunch、redirectTo、switchTab区别
1.navigateTo 保留当前页面,跳转到应用内的某个页面,使用uni.navigateBack可以返回到原页面。 要注意的是navigateTo只能跳转的应用内非 tabBar 的页面的路径 , 路径后可以带参数;如果跳转url参数为tabBar的路径则无法进行跳转 2.redir…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...