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

相关文章

数据库面试必备之MySQL中的乐观锁与悲观锁

《数据库面试必备之MySQL中的乐观锁与悲观锁》:本文主要介绍数据库面试必备之MySQL中乐观锁与悲观锁的相关资料,乐观锁适用于读多写少的场景,通过版本号检查避免冲突,而悲观锁适用于写多读少且对数... 目录一、引言二、乐观锁(一)原理(二)应用场景(三)示例代码三、悲观锁(一)原理(二)应用场景(三)示例

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

Linux卸载自带jdk并安装新jdk版本的图文教程

《Linux卸载自带jdk并安装新jdk版本的图文教程》在Linux系统中,有时需要卸载预装的OpenJDK并安装特定版本的JDK,例如JDK1.8,所以本文给大家详细介绍了Linux卸载自带jdk并... 目录Ⅰ、卸载自带jdkⅡ、安装新版jdkⅠ、卸载自带jdk1、输入命令查看旧jdkrpm -qa

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

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