LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

本文主要是介绍LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

3177. 求出最长好子序列 II

题目链接

题目描述

给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。

实例1:

输入:nums = [1,2,1,1,3], k = 2
输出:2
解释:最长的好子序列是 [1,2,1,1] 。

实例2:

输入:nums = [1,2,3,4,5,1], k = 0
输出:2
解释:最长好子序列为 [1,1] 。

题目解析

这道题目是求出最长好子序列 I的升级版,对时间复杂度有了更高的要求。我们在上一篇题解中,给出了时间复杂度为 O ( n 2 ∗ k ) O(n^2*k) O(n2k)的解法。这次需要将时间复杂度降低到 O ( n ∗ k ) O(n*k) O(nk)

解题思路

这道题目和求出最长好子序列 I的解法类似,也是使用动态规划。

我们同样定义定义dp[i][j]表示以nums[i]结尾,最多有j个下标i 满足seq[i] != seq[i + 1]的子序列的长度。其中,0<=j<=k。

而在上一篇题解中,我们使用了三重循环,来解决问题。

而这次,我们考虑去掉第三重循环。

			for cur := 0; cur < i; cur++ {if nums[i] == nums[cur] {dp[i][j]=max(dp[i][j],dp[cur][j]+1)}else{if(j-1>=0){dp[i][j]=max(dp[i][j],dp[cur][j-1]+1)}}}

我们看到,循环中只需考虑两种情况

  • 数字i之前有数字和nums[i]相同
  • 数字i之前有数字和nums[i]不同,且j大于0

因此我们使用哈希表lastPos := make(map[int]int) 用于记录和nums[i]相同的数字最后出现的位置。
lastMax := make([]int, k+1) 用于记录不同列的当前最大取值,即dp[cur][j-1]的最大值,其中0 <=cur<i

  • 数字i之前有数字和nums[i]相同,则dp[i][j]=max(dp[i][j],dp[lastPos[nums[i]]][j]+1)
  • 数字i之前有数字和nums[i]不同,且j大于0,则dp[i][j]=max(dp[i][j],lastMax[j-1]+1)

代码实现

Go版本:

func maximumLength(nums []int, k int) int {n := len(nums)dp := make([][]int, n)for i := range dp {dp[i] = make([]int, k+1)}res := 0lastPos := make(map[int]int) // 用于记录每个数字的最后出现位置lastMax := make([]int, k+1)  // 用于记录第 j 列的最大值lastNew := make([]int, k+1)  // 用于临时保存本轮计算中的最大值for i := 0; i < n; i++ {dp[i][0] = 1// 在每次外循环开始时,重置 lastNew 为 lastMax 的当前状态copy(lastNew, lastMax)for j := 0; j <= k && j <= i; j++ {// 如果数字之前出现过,更新 dp[i][j] 的值if pos, found := lastPos[nums[i]]; found {dp[i][j] = max(dp[i][j], dp[pos][j]+1)}// 如果允许更多的 k,考虑使用 lastMax[j-1]if j > 0 {dp[i][j] = max(dp[i][j], lastMax[j-1]+1)}// 更新 lastNew 和最终结果lastNew[j] = max(lastNew[j], dp[i][j])res = max(res, dp[i][j])}// 外循环结束时,将 lastMax 更新为本轮的 lastNewcopy(lastMax, lastNew)// 更新当前数字最后一次出现的位置lastPos[nums[i]] = i}return res
}

C++版本:

class Solution {
public:int maximumLength(vector<int>& nums, int k) {int n=nums.size();vector<vector<int>> dp(n,vector<int>(k+1,0));int res=0;vector<int> lastMax(k+1,0);vector<int> lastTemp(k+1, 0);unordered_map<int,int> lastPos;for(int i=0;i<n;i++){dp[i][0]=1;for(int j=0;j<=k;j++){if(lastPos.count(nums[i])){dp[i][j]=max(dp[i][j],dp[lastPos[nums[i]]][j]+1);}if(j>0){dp[i][j]=max(dp[i][j],lastMax[j-1]+1);}lastTemp[j]=max(lastTemp[j],dp[i][j]);res=max(res,dp[i][j]);}lastPos[nums[i]]=i;lastMax=lastTemp;}return res;}
};

Python版本:

class Solution(object):def maximumLength(self, nums, k):n = len(nums)dp = [[0] * (k + 1) for _ in range(n)]res = 0last_max = [0] * (k + 1)last_temp = [0] * (k + 1)last_pos = {}for i in range(n):dp[i][0] = 1for j in range(k + 1):if nums[i] in last_pos:dp[i][j] = max(dp[i][j], dp[last_pos[nums[i]]][j] + 1)if j > 0:dp[i][j] = max(dp[i][j], last_max[j - 1] + 1)last_temp[j] = max(last_temp[j], dp[i][j])res = max(res, dp[i][j])last_pos[nums[i]] = ilast_max = last_temp[:]return res

这篇关于LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Qt中QGroupBox控件的实现

《Qt中QGroupBox控件的实现》QGroupBox是Qt框架中一个非常有用的控件,它主要用于组织和管理一组相关的控件,本文主要介绍了Qt中QGroupBox控件的实现,具有一定的参考价值,感兴趣... 目录引言一、基本属性二、常用方法2.1 构造函数 2.2 设置标题2.3 设置复选框模式2.4 是否

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法

《springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法》:本文主要介绍springboot整合阿里云百炼DeepSeek实现sse流式打印,本文给大家介绍的非常详细,对大... 目录1.开通阿里云百炼,获取到key2.新建SpringBoot项目3.工具类4.启动类5.测试类6.测

pytorch自动求梯度autograd的实现

《pytorch自动求梯度autograd的实现》autograd是一个自动微分引擎,它可以自动计算张量的梯度,本文主要介绍了pytorch自动求梯度autograd的实现,具有一定的参考价值,感兴趣... autograd是pytorch构建神经网络的核心。在 PyTorch 中,结合以下代码例子,当你

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的

openCV中KNN算法的实现

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

OpenCV图像形态学的实现

《OpenCV图像形态学的实现》本文主要介绍了OpenCV图像形态学的实现,包括腐蚀、膨胀、开运算、闭运算、梯度运算、顶帽运算和黑帽运算,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起... 目录一、图像形态学简介二、腐蚀(Erosion)1. 原理2. OpenCV 实现三、膨胀China编程(

通过Spring层面进行事务回滚的实现

《通过Spring层面进行事务回滚的实现》本文主要介绍了通过Spring层面进行事务回滚的实现,包括声明式事务和编程式事务,具有一定的参考价值,感兴趣的可以了解一下... 目录声明式事务回滚:1. 基础注解配置2. 指定回滚异常类型3. ​不回滚特殊场景编程式事务回滚:1. ​使用 TransactionT