当前位置: 首页 > news >正文

【动态规划刷题 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 的情况讨论:

  1. a 存在,下标为 k ,并且 a < b :此时我们需要以 k 位置以及 i 位置元素为结尾的最⻓等差序列的⻓度,然后再加上 j 位置的元素即可。于是dp[i][j] = dp[k][i] +1 。这⾥因为会有许多个 k ,我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k 为结尾;
  2. a 存在,但是 b < a < c :此时只能两个元素⾃⼰玩了, dp[i][j] = 2 ;
  3. 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 的情况讨论:

  1. a 存在,下标为 k ,并且 a < b :此时我们需要以 k 位置以及 i 位置元素为结尾的最⻓等差序列的⻓度,然后再加上 j 位置的元素即可。于是dp[i][j] = dp[k][i] +1 。这⾥因为会有许多个 k ,我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k 为结尾;
  2. 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&#xff0c;返回 nums 中最长等差子序列的长度。 回想一下&#xff0c;nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] &#xff0c;且 0 < i1 <…...

【postgresql】替换 mysql 中的ifnull()

数据库由mysql 迁移到postgresql&#xff0c;程序在执行查询时候报错。 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…...

单例模式(懒汉式,饿汉式,变体)

单例模式&#xff0c;用于确保一个类只有一个实例&#xff0c;并提供一个全局访问点以访问该实例。 饿汉式&#xff08;Eager Initialization&#xff09; 程序启动时就创建实例 #include <iostream> class SingletonEager { private:static SingletonEager* instanc…...

Java Lambda表达式:简洁且强大的函数式编程工具

Lambda表达式是Java 8及以后版本中引入的一种函数式编程特性。它是一种匿名函数&#xff0c;允许开发人员以简洁和易读的方式编写代码&#xff0c;并且可以作为参数传递给方法或存储在变量中。Lambda表达式的基本语法如下&#xff1a;(parameters) -> expression&#xff0c…...

开源框架中的责任链模式实践

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

智能配电系统:保障电力运行安全、可控与高效

智能配电系统是一种先进的电力分配技术&#xff0c;它通过智能化、数字化和网络化等方式&#xff0c;有效地保障了电力运行的安全、可控和高效。 力安科技智能配电系统是在配电室&#xff08;含高压柜、变压器、低压柜&#xff09;、箱式变电站、配电箱及动力柜&#xff08…...

MySQL学习系列(11)-每天学习10个知识

目录 1. 数据库设计的关键因素2. 使用存储过程和函数来提高性能和可重用性3. MySQL性能优化4. 使用视图简化查询和提供数据安全性5. 数据库备份和恢复策略的重要性和实践经验6. 在分布式系统中保证数据一致性和可用性7. 理解MySQL的复制和其在实际应用中的作用8. 使用游标进行分…...

如何通过Gunicorn和Niginx部署Django

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

C语言 cortex-A7核UART总线实验

一、C 1&#xff09;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#项目&#xff0c;只能反编译了。 项目主页 https://github.com/icsharpcode/ILSpy 使用方法 中文界面使用简单&#xff0c;把你要反编译的dll拖过去就可以了。好使&#xff01;&#xff01;&#xff01;...

演讲实录:DataFun 垂直开发者社区基于指标平台自主洞察北极星指标

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

ffmpeg编译 Error: operand type mismatch for `shr‘

错误如下&#xff1a; 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服务器&#xff0c;勾上FTP服务和FTP扩展&#xff0c;点击下一步 安装 安装完成关闭 打开我们的IIS服务器 在WIN-XXX主页可以看到我们的FTP相关菜单 右键WIN-XXXX主页&#xff0c;添加FTP站点 输入站点名称-FT…...

python教程:使用gevent实现高并发并限制最大并发数

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 import time import gevent from gevent.pool import Pool from gevent import monkey # 一&#xff0c;定义最大并发数 p Pool(20) # 二&#xff0c;导入gevent…...

借助reCAPTCHA实现JavaScript验证码功能

前言 验证码&#xff08;CAPTCHA&#xff09;是一种常见的安全验证机制&#xff0c;常用于区分真实用户和机器人。使用验证码可以有效防止恶意登录、自动注册或者密码爆破等攻击。本文将借助reCAPTCHA第三方库来实现JavaScript验证码功能。 验证码的原理 验证码的核心思想是要…...

监控数据的采集方式及原理

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

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核服务器配置大全&#xff0c;CVM云服务器可选择标准型S6、标准型SA3、计算型C6或标准型S5等&#xff0c;目前标准型S5云服务器有优惠活动&#xff0c;性价比高&#xff0c;计算型C6云服务器16核性能更高&#xff0c;轻量16核32G28M带宽优惠价3468元15个月&#xff0c;…...

Postman应用——下载注册和登录

文章目录 下载安装注册登录注册账号登录账号 下载安装 Postman下载&#xff1a;https://www.postman.com/ 访问链接后&#xff0c;进入首页&#xff0c;根据自己的操作系统下载对应的版本。 找到下载到的目录直接双击.exe文件&#xff0c;会默认安装在C盘&#xff0c;安装完会…...

uni-app混合开发 navigateTo、reLaunch、redirectTo、switchTab区别

1.navigateTo 保留当前页面&#xff0c;跳转到应用内的某个页面&#xff0c;使用uni.navigateBack可以返回到原页面。 要注意的是navigateTo只能跳转的应用内非 tabBar 的页面的路径 , 路径后可以带参数&#xff1b;如果跳转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仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

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

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...