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实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Python实现自动化接收与处理手机验证码

《Python实现自动化接收与处理手机验证码》在移动互联网时代,短信验证码已成为身份验证、账号注册等环节的重要安全手段,本文将介绍如何利用Python实现验证码的自动接收,识别与转发,需要的可以参考下... 目录引言一、准备工作1.1 硬件与软件需求1.2 环境配置二、核心功能实现2.1 短信监听与获取2.

使用Python实现获取网页指定内容

《使用Python实现获取网页指定内容》在当今互联网时代,网页数据抓取是一项非常重要的技能,本文将带你从零开始学习如何使用Python获取网页中的指定内容,希望对大家有所帮助... 目录引言1. 网页抓取的基本概念2. python中的网页抓取库3. 安装必要的库4. 发送HTTP请求并获取网页内容5. 解

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

使用Python实现网络设备配置备份与恢复

《使用Python实现网络设备配置备份与恢复》网络设备配置备份与恢复在网络安全管理中起着至关重要的作用,本文为大家介绍了如何通过Python实现网络设备配置备份与恢复,需要的可以参考下... 目录一、网络设备配置备份与恢复的概念与重要性二、网络设备配置备份与恢复的分类三、python网络设备配置备份与恢复实

Java 中实现异步的多种方式

《Java中实现异步的多种方式》文章介绍了Java中实现异步处理的几种常见方式,每种方式都有其特点和适用场景,通过选择合适的异步处理方式,可以提高程序的性能和可维护性,感兴趣的朋友一起看看吧... 目录1. 线程池(ExecutorService)2. CompletableFuture3. ForkJoi