算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

在这里插入图片描述

算法沉淀——动态规划之子序列问题

  • 01.最长定差子序列
  • 02.最长的斐波那契子序列的长度
  • 03.最长等差数列
  • 04.等差数列划分 II - 子序列

01.最长定差子序列

题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

提示：

  • 1 <= arr.length <= 105
  • -104 <= arr[i], difference <= 104

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[i] 表示以第 i 个位置的元素为结尾的所有子序列中，最长的等差子序列的长度。
  2. 状态转移方程： 对于 dp[i]，上一个定差子序列的取值定为 arr[i] - difference。只要找到以上一个数为结尾的定差子序列长度的 dp[arr[i] - difference]，然后加上 1，就是以 i 为结尾的定差子序列的长度。这里可以使用哈希表进行优化，将元素和 dp[j] 绑定，放入哈希表中。
  3. 初始化： 刚开始的时候，需要把第一个元素放进哈希表中，即 hash[arr[0]] = 1。
  4. 填表顺序： 根据状态转移方程，填表顺序是从左往右。
  5. 返回值： 根据状态表达，返回整个 dp 数组中的最大值。

代码

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int,int> hash;hash[arr[0]]=1;int ret=1;for(int i=1;i<arr.size();i++){hash[arr[i]]=hash[arr[i]-difference]+1;ret=max(ret,hash[arr[i]]);}return ret;}
};

02.最长的斐波那契子序列的长度

题目链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

  • n >= 3
  • 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：

  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10^9

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[j][i] 表示以第 j 位置以及第 i 位置的元素为结尾的所有的子序列中，最长的斐波那契子序列的长度。
  2. 状态转移方程： 设 nums[j] = b，nums[i] = c，那么这个序列的前一个元素就是 a = c - b。根据 a 的情况讨论：
    • 如果 a 存在，下标为 k，并且 a < b，那么 dp[j][i] = dp[k][j] + 1；
    • 如果 a 存在，但是 b < a < c，那么 dp[j][i] = 2；
    • 如果 a 不存在，那么 dp[j][i] = 2。
  3. 优化点： 在状态转移方程中，需要确定 a 元素的下标，可以在填表之前，将所有的「元素 + 下标」绑定在一起，放到哈希表中。
  4. 初始化： 将表里面的值都初始化为 2。
  5. 填表顺序：
    • 先固定最后一个数；
    • 然后枚举倒数第二个数。
  6. 返回值： 返回 dp 表中的最大值 ret。但是 ret 可能小于 3，小于 3 说明不存在，需要判断一下。

代码

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n=arr.size();unordered_map<int,int> hash;for(int i=0;i<n;i++) hash[arr[i]]=i;vector<vector<int>> dp(n,vector<int>(n,2));int ret=2;for(int i=2;i<n;++i){for(int j=1;j<i;j++){int x=arr[i]-arr[j];if(x<arr[j]&&hash.count(x))dp[j][i] = dp[hash[x]][j]+1;ret = max(ret,dp[j][i]);}}return ret<3?0:ret;}
};

03.最长等差数列

题目链接：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]。

提示：

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

思路

  1. 状态表达： 定义动态规划数组 dp，其中 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。
  3. 优化点： 在状态转移方程中，需要确定 a 元素的下标。可以一边动态规划，一边保存最近的元素的下标，不用保存下标数组。遍历的时候，先固定倒数第二个数，再遍历倒数第一个数。这样可以在 i 使用完时候，将 nums[i] 扔到哈希表中。
  4. 初始化： 将表里面的值都初始化为 2。
  5. 填表顺序：
    • 先固定倒数第二个数；
    • 然后枚举倒数第一个数。
  6. 返回值： 返回 dp 表中的最大值。

代码

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

04.等差数列划分 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 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[i][j] 表示以第 i 位置以及第 j 位置的元素为结尾的所有的子序列中，等差子序列的个数。
  2. 状态转移方程： 设 nums[i] = b，nums[j] = c，那么这个序列的前一个元素就是 a = 2 * b - c。根据 a 的情况讨论：
    • 如果 a 存在，下标为 k，并且 a < b，那么以 k 元素以及 i 元素结尾的等差序列的个数为 dp[k][i]，在这些子序列的后面加上 j 位置的元素依旧是等差序列。但是这里会多出来一个以 k, i, j 位置的元素组成的新的等差序列，因此 dp[i][j] += dp[k][i] + 1；
    • 因为 a 可能有很多个，需要全部累加起来。
  3. 优化点： 在状态转移方程中，需要确定 a 元素的下标。因此在 dp 之前，将所有元素和下标数组绑定在一起，放到哈希表中。这里保存下标数组是因为需要统计个数。
  4. 初始化： 刚开始是没有等差数列的，因此初始化 dp 表为 0。
  5. 填表顺序：
    • 先固定倒数第一个数；
    • 然后枚举倒数第二个数。
  6. 返回值： 统计所有的等差子序列，返回 dp 表中所有元素的和。

代码

class Solution {
public: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);vector<vector<int>> dp(n,vector<int>(n));int sum=0;for(int j=2;j<n;j++){for(int i=1;i<j;i++){long long x=(long long)nums[i]*2-nums[j];if(hash.count(x)) for(int& k:hash[x])if(k<i) dp[i][j]+=dp[k][i]+1;sum+=dp[i][j];}}return sum;}
};

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

springboot+vue实现oss文件存储

springboot+vue实现oss文件存储

前提oss准备工作 进入阿里云官网&#xff1a;阿里云oss官网 注册 搜OSS&#xff0c;点击“对象存储OSS” 第一次进入需要开通&#xff0c;直接点击立即开通&#xff0c;到右上角AccessKey管理中创建AccessKey&#xff0c;并且记住自己的accessKeyId和accessKeySecret&#…
阅读更多...
【数据结构与算法】回溯法解题20240229

【数据结构与算法】回溯法解题20240229

【数据结构与算法】回溯法解题20240229 一、46. 全排列1、以[1,2,3]为例&#xff0c;抽象成树形结构2、回溯三部曲 二、LCR 084. 全排列 II1、以[1,1,2]为例&#xff0c;抽象成树形结构 三、面试题 08.07. 无重复字符串的排列组合四、面试题 08.08. 有重复字符串的排列组合 一、…
阅读更多...
Java面试资料集合，只需一篇文章吃透Java多线程技术

Java面试资料集合，只需一篇文章吃透Java多线程技术

前言 受到疫情影响我从过完年一直呆在家里&#xff0c;索性学点知识方便以后跳槽涨薪&#xff0c;于是从二月份开始学习阿里P8架构师纯手打的一份Java面经手册&#xff0c;没想到5月初我成功从我们三线的一个小公司跳槽进了腾讯&#xff0c;虽然等级不高&#xff0c;但是涨薪还…
阅读更多...
【力扣hot100】刷题笔记Day15

【力扣hot100】刷题笔记Day15

前言 今天要刷的是图论&#xff0c;还没学过&#xff0c;先看看《代码随想录》这部分的基础 深搜DFS理论基础 深搜三部曲 确认递归函数、参数确认终止条件处理目前搜索节点出发的路径 代码框架 void dfs(参数) {if (终止条件) {存放结果;return;}for (选择&#xff1a;本节点…
阅读更多...
Git教程-Git的基本使用

Git教程-Git的基本使用

Git是一个强大的分布式版本控制系统&#xff0c;它不仅用于跟踪代码的变化&#xff0c;还能够协调多个开发者之间的工作。在软件开发过程中&#xff0c;Git被广泛应用于协作开发、版本管理和代码追踪等方面。以下是一个详细的Git教程&#xff0c;我们将深入探讨Git的基本概念和…
阅读更多...
npm ERR! code ERESOLVE

npm ERR! code ERESOLVE

1、问题概述&#xff1f; 执行npm install命令的时候报错如下&#xff1a; tangxiaochuntangxiaochundeMacBook-Pro stf % npm install npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree npm ERR! npm ERR! While resol…
阅读更多...
C++ Primer 总结索引 | 第八章：IO库

C++ Primer 总结索引 | 第八章：IO库

1、IO类 1、已经使用过的IO类型和对象 都是 操纵char数据的。默认情况下&#xff0c;这些对象 都是关联到 用户的控制台窗口的 但是 不能仅从控制台窗口 进行IO操作&#xff0c;应用程序 需要 读写命名文件&#xff0c;使用IO操作 处理string中的字符 会很方便&#xff0c;此…
阅读更多...
Netty入门指南：从零开始的异步网络通信

Netty入门指南：从零开始的异步网络通信

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 Netty入门指南&#xff1a;从零开始的异步网络通信 前言Netty简介由来&#xff1a;发展历程&#xff1a;异步、事件驱动的编程模型&#xff1a; 核心组件解析通信协议高性能特性异步编程范式性能优化与…
阅读更多...
Linux零基础快速入门

Linux零基础快速入门

Linux的诞生 Linux创始人:林纳斯 托瓦兹 Linux 诞生于1991年&#xff0c;作者上大学期间 因为创始人在上大学期间经常需要浏览新闻和处理邮件&#xff0c;发现现有的操作系统不好用,于是他决心自己写一个保护模式下的操作系统&#xff0c;这就是Linux的原型&#xff0c;当时他…
阅读更多...
【MySQL】DCL

【MySQL】DCL

DCL英文全称是Data Control Language(数据控制语言)&#xff0c;用来管理数据库用户、控制数据库的访问权限。 1. 管理用户 在MySQL数据库中&#xff0c;DCL&#xff08;数据控制语言&#xff09;是用来管理用户和权限的语句集合。通过DCL语句&#xff0c;可以创建、修改、删…
阅读更多...
leetcode 重复的子字符串

leetcode 重复的子字符串

前要推理 以abababab为例&#xff0c;这里最主要的就是根据相等前后缀进行推导 s [ 0123 ] 如 t【 0123 】 f 【01 23 】 后两个分别是前后缀&#xff0c;第一个是总的字符串&#xff0c;然后可以推导 //首先还是算出…
阅读更多...
Spring的定时任务不生效、不触发，一些可能的原因，和具体的解决方法。

Spring的定时任务不生效、不触发，一些可能的原因，和具体的解决方法。

1 . 未在启动类上加 EnableScheduling 注解 原因&#xff1a;未在Spring Boot应用主类上添加EnableScheduling注解或未在XML配置文件中配置定时任务的启用。解决方法&#xff1a;确保在应用的配置类上添加EnableScheduling注解&#xff0c;启用定时任务。 2 . cron 表达式书写…
阅读更多...
P4859 已经没有什么好害怕的了（二项式反演+dp）

P4859 已经没有什么好害怕的了（二项式反演+dp）

题录&#xff1a;P4859 已经没有什么好害怕的了 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路: 代码&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string> #include<cstring> #include<cmath> #include<ctim…
阅读更多...
Kubernetes剖析

Kubernetes剖析

Kubernetes剖析 前言 ​ 容器技术这样一个新生事物&#xff0c;完全重塑了整个云计算市场的形态。它不仅催生出了一批年轻有为的容器技术人&#xff0c;更培育出了一个具有相当规模的开源基础设施技术市场。 ​ 在这个市场里&#xff0c;不仅有 Google、Microsoft 等技术巨擘…
阅读更多...
【GPTs分享】GPTs分享之Photo Multiverse，不唱、跳、RAP的坤坤能叫坤坤吗

【GPTs分享】GPTs分享之Photo Multiverse，不唱、跳、RAP的坤坤能叫坤坤吗

今日GPTs分享&#xff1a;Photo Multiverse。Photo Multiverse 是一款基于先进人工智能技术的创意辅助工具&#xff0c;专为艺术家和创意人士设计&#xff0c;以探索和创造多元宇宙中的视觉艺术。它通过结合古老的艺术神秘主义和现代技术&#xff0c;帮助用户将他们的想象力变为…
阅读更多...
linux gdb 调试工具

linux gdb 调试工具

1.写程序 首先&#xff0c;我们先写出一个 .c 或者.cpp程序 如 然后 gcc -g hello.c -o hello 或者 g -g hello.cpp -o hello &#xff08;-g&#xff09;要加 2. gdb调试 用 gdb &#xff08;可执行程序&#xff0c;如hello&#xff09; 进入之后&#xff0c;有…
阅读更多...
el-table 多选表格存在分页，编辑再次操作勾选会丢失原来选中的数据

el-table 多选表格存在分页，编辑再次操作勾选会丢失原来选中的数据

el-table表格多选时&#xff0c;只需要添加type"selection"&#xff0c; row-key及selection-change&#xff0c;如果存在分页时需要加上reserve-selection&#xff0c;这里就不写具体的实现方法了&#xff0c;可以查看我之前的文章&#xff0c;这篇文章主要说一下存…
阅读更多...
算法打卡day5|哈希表篇01|Leetcode 242.有效的字母异位词 、19.删除链表的倒数第N个节点、202. 快乐数、1. 两数之和

算法打卡day5|哈希表篇01|Leetcode 242.有效的字母异位词 、19.删除链表的倒数第N个节点、202. 快乐数、1. 两数之和

哈希表基础知识 哈希表 哈希表关键码就是数组的索引下标&#xff0c;然后通过下标直接访问数组中的元素&#xff1b;数组就是哈希表的一种 一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在班级里&#xff1a; 要枚举的话时间复杂度是O(n)&…
阅读更多...
Linux服务器中文乱码如何解决

Linux服务器中文乱码如何解决

如果服务器上数字和英文均可正常展示&#xff0c;只有中文是奇奇怪怪的乱码&#xff0c;那么可以考虑是服务器本身字体输出有问题。 如何在服务器上安装中文宋体字体库呢&#xff0c;排查及安装字体库步骤如下&#xff1a; 使用 fc-list命令检查服务器是否安装字体库如果提示…
阅读更多...
Docker部署Portainer图形化管理工具

Docker部署Portainer图形化管理工具

文章目录 前言1. 部署Portainer2. 本地访问Portainer3. Linux 安装cpolar4. 配置Portainer 公网访问地址5. 公网远程访问Portainer6. 固定Portainer公网地址 前言 Portainer 是一个轻量级的容器管理工具&#xff0c;可以通过 Web 界面对 Docker 容器进行管理和监控。它提供了可…
阅读更多...
最新文章

Copyright @ 2022~2023