Leetcode面试经典150题-128.最长连续序列-递归版本另解

2024-09-08 06:04

本文主要是介绍Leetcode面试经典150题-128.最长连续序列-递归版本另解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本

可以看看之前的版本,两个版本面试用哪个都保过

解法都在代码里,不懂就留言或者私信

class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的连续的长度初始值都是1,后面再遍历数组,遍历过程中查找当前数+1在map中的记录,直到找不到为止,比如我们第一个示例[100,4,200,1,3,2]我们便利到1的时候会在map中找到2的记录,然后取它的value+1,找2的过程又会递归查找3,直到找不到5的时候停,5的value是0,4取0+1=13取1+1=2 2取2+1=3,1取3+1=4而对于100,我们查找101就直接失败了,所以以它连续的就是0+1=1*/public int longestConsecutive(int[] nums) {/**如果长度小于2,有多少数就有多大的连续长度*/if(nums.length < 2) {return nums.length;}/**大于等于2的情况我们先把每个数都放在map里,key是数字本身,value是以它为开始的连续长度,初始值都设置为1这样做还有另外一个原因就是可以避免重复项的干扰*/Map<Integer, Integer> countMap = new HashMap<>();for(int num : nums) {countMap.put(num, 1);}/**定义结果值,既然有数,至少也得是个1吧*/int longest = 1;/**遍历数组,计算以当前数字开始的最长的长度*/for(int num : nums) {int curAns = countConsecutive(countMap, num);longest = Math.max(longest, curAns);}return longest;}/**通过countMap查找target开始的连续数字的长度 */public int countConsecutive(Map<Integer, Integer> countMap, int target) {/**我们通过主方法调用这个方法的时候当然target肯定是存在的,但是我们会递归调用 target+1直到不存在为止,所以这里一定要判断是不是存在,不存在返回0 */if(!countMap.containsKey(target)) {return 0;}/**这里有个大的优化,一定要做,如果当前map中存的target对应的value已经大于1了,说明算过了,不用重复计算不然每次都得从头开始一个一个算,肯定会超时的,比如先找1,然后找2.。。一直找到10000肯定不行,如果之前已经有2的记录了(大于1)现在取2的记录+1就行了 */if(countMap.get(target) > 1) {return countMap.get(target);}/**如果存在,找target+1开头的最大长度 */int count = countConsecutive(countMap, target + 1) + 1;/**不要忘了记录当前的结果*/countMap.put(target, count);return count;}
}

运行时间和百分百确实有所提升,但是真的是同样的时间复杂度,也没感觉常数时间降低了多少

这篇关于Leetcode面试经典150题-128.最长连续序列-递归版本另解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)

《JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)》本文介绍了如何在Windows系统上配置多版本JDK(以JDK8和JDK17为例),并通过图文结合的方式给大家讲解了详细步骤,具有... 目录第一步 下载安装JDK第二步 配置环境变量第三步 切换JDK版本并验证可能遇到的问题前提:公司常

nvm如何切换与管理node版本

《nvm如何切换与管理node版本》:本文主要介绍nvm如何切换与管理node版本问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录nvm切换与管理node版本nvm安装nvm常用命令总结nvm切换与管理node版本nvm适用于多项目同时开发,然后项目适配no

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

Mybatis从3.4.0版本到3.5.7版本的迭代方法实现

《Mybatis从3.4.0版本到3.5.7版本的迭代方法实现》本文主要介绍了Mybatis从3.4.0版本到3.5.7版本的迭代方法实现,包括主要的功能增强、不兼容的更改和修复的错误,具有一定的参考... 目录一、3.4.01、主要的功能增强2、selectCursor example3、不兼容的更改二、

pytorch+torchvision+python版本对应及环境安装

《pytorch+torchvision+python版本对应及环境安装》本文主要介绍了pytorch+torchvision+python版本对应及环境安装,安装过程中需要注意Numpy版本的降级,... 目录一、版本对应二、安装命令(pip)1. 版本2. 安装全过程3. 命令相关解释参考文章一、版本对

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

mac安装nvm(node.js)多版本管理实践步骤

《mac安装nvm(node.js)多版本管理实践步骤》:本文主要介绍mac安装nvm(node.js)多版本管理的相关资料,NVM是一个用于管理多个Node.js版本的命令行工具,它允许开发者在... 目录NVM功能简介MAC安装实践一、下载nvm二、安装nvm三、安装node.js总结NVM功能简介N

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2