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

本文主要是介绍算法沉淀——动态规划之子序列问题(下)(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] = bnums[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] = bnums[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] = bnums[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;}
};

这篇关于算法沉淀——动态规划之子序列问题(下)(leetcode真题剖析)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/757524

相关文章

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL