力扣100热题[哈希]:最长连续序列

原题:128. 最长连续序列

题解:

官方题解:. - 力扣(LeetCode)题解,最长连续序列 :哈希表

官方解题思路是先去重,然后判断模板长度的数值是否存在,存在就刷新,最终找到最大值。

这里我自己研究了下,实际也是暴力解法。纯暴力解法会超时,这里利用了二分法查找的理念

  • 首先去重
  • 然后排序
  • 固定begin,然后找最大的end,返回max=end-begin+1使用二分法理念进行查找
  • 依次遍历,在end-begin<curmax已经找到的最大值,返回curmax +1

自己尝试了下,部分通过,有些边界值不太好控制,而且输入里面有负数,也不太好计算。

还有一种解题方法,就是在官方题解上做个变化,

  • 首先去重
  • 然后排序
  • 依次遍历,找到满足nums[i + 1] = nums[i] + 1的最长子数组,返回其长度。

代码:

func longestConsecutive(nums []int) int {
    // 如果数组为空,或者只有一个元素,直接返回数组长度
	if len(nums) <= 1 {
		return len(nums)
	}

	// 去重
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}

	// 排序
	numTemp := make([]int, 0)
	for num := range numSet {
		numTemp = append(numTemp, num)
	}
	sort.Ints(numTemp)
	// fmt.Printf("numTemp %v\n", numTemp)

	// 暴力解法
	longestStreak := 0
	for begin := range numTemp {
		// 当剩余的个数,小于当前最大长度,则后面不可能有满足条件的更大的值,返回
		if begin+longestStreak > len(numTemp) {
			return longestStreak + 1
		}
		temp := BinarySearchMatch(numTemp, begin, longestStreak)
		if longestStreak < temp {
			longestStreak = temp
		}
	}
	return longestStreak + 1
}

func BinarySearchMatch(numTemp []int, begin, cur int) int {
	longestStreak := cur
	// 当前最大可用差值
	curMaxDiff := len(numTemp) - begin - 1
	// 使用二分法的理念,查询满足条件的数据
	for end := len(numTemp) - 1; end > begin; {
		// fmt.Printf("begin %v, end %v, curMaxDiff %v\n", begin, end, curMaxDiff)
		// 索引差值超过最大值,返回,end超过数组范围,返回
		if curMaxDiff >= len(numTemp) || end >= len(numTemp) {
			break
		}
		// 差值为0时,有可能会遗漏一个,判断end的下一个是否满足条件
		if curMaxDiff == 0 {
			if end < len(numTemp)-1 && numTemp[end+1]-numTemp[begin] == end+1-begin {
				longestStreak = end + 1 - begin
			}
            
			if end > begin && numTemp[end-1]-numTemp[begin] == end-1-begin {
				longestStreak = end - 1 - begin
			}

            if end > begin && numTemp[end]-numTemp[begin] == end-begin {
				longestStreak = end - begin
			}
			break
		}
		// 数值差值
		valDiff := numTemp[end] - numTemp[begin]
		// 索引差值
		indexDiff := end - begin

		// 二分法找到合适的索引end
		// 索引差值 < 数值差值,数值太大了,中间有不连续的,往前移动curMaxDiff/2
		if valDiff > indexDiff && indexDiff != 0 {
			curMaxDiff = curMaxDiff / 2
			end = end - curMaxDiff
			continue
		}

		// 索引差值 > 数值差值,这种不可能存在,因为已经去重了
		// 索引差值 = 数值差值,后面可能还有满足条件的,继续找
		if valDiff == indexDiff {
			// 刷新最大值
			if longestStreak > valDiff {
				break
			}

			longestStreak = valDiff
			// end后移curMaxDiff/2
			curMaxDiff = curMaxDiff / 2
			end = end + curMaxDiff
			continue
		}
	}

	return longestStreak
}

第二种方法

func longestConsecutive(nums []int) int {
    // 如果数组为空,或者只有一个元素,直接返回数组长度
	if len(nums) <= 1 {
		return len(nums)
	}

	// 去重
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}

	// 排序
	numTemp := make([]int, 0)
	for num := range numSet {
		numTemp = append(numTemp, num)
	}
	sort.Ints(numTemp)
	//fmt.Printf("numTemp %v\n", numTemp)

	// 暴力解法
	longestStreak := 0
	for num := range numTemp {
		if num < len(numTemp)-1 && numTemp[num]+1 == numTemp[num+1] {
			currentNum := num
			currentStreak := 1
			for currentNum < len(numTemp)-1 && numTemp[currentNum]+1 == numTemp[currentNum+1] {
				currentNum++
				currentStreak++
			}
			if longestStreak < currentStreak {
				longestStreak = currentStreak
			}
		}
	}
	return longestStreak
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/484681.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【4XVR】win11局域网共享3D影片给quest3

准备工作 首先要有一个路由器&#xff0c;使电脑和quest3处于同一个局域网下 一.创建一个离线账户 打开设置选择账户 添加账户 二.共享文件 选择要共享的文件夹&#xff0c;右键打开属性&#xff0c;点击共享 选择刚刚创建的用户&#xff0c;点击共享即可 三.使用quest观影 …

AttributeError: ‘_MSDataLoaderIter‘ object has no attribute ‘_put_indices‘

问题描述 复现代码过程中遇到错误&#xff1a;AttributeError: _MSDataLoaderIter object has no attribute _put_indices 解决方案 出错的原因是代码中使用了不存在的属性"_put_indices"。这个错误可能与你使用的版本不兼容有关。在pytorch1.x版本中&#xff0c;&q…

Unity基础框架

公共模块 单例基类 如果有很多个这样的单例模式对象,创建他们时都要重复的写单例模式代码。那么能不能利用泛型来减少这部分重复的工作量呢。 单例模式基类,最简单的写法 继承MonoBehaviour的单例基类 所以需要做一些改进 获取单例时如果为空,创建一个名字一样的物体,挂…

力扣HOT100 - 283. 移动零

解题思路&#xff1a; 双指针 指针 i 用于寻找不为零的位置 指针 j 用于寻找为零的位置 不为零时&#xff0c;自己与自己交换&#xff0c;i 和 j 同时向下一个位置移动 为零时&#xff0c;nums[ i ]与nums[ j ]交换&#xff0c;使零向后移动 class Solution {public void…

YOLOv8 | 注意力机制 | 添加ResBlock_CBAM注意力机制——论文必备(全网独家)

⭐欢迎大家订阅我的专栏一起学习⭐ 🚀🚀🚀订阅专栏,更新及时查看不迷路🚀🚀🚀 YOLOv5涨点专栏:http://t.csdnimg.cn/96Cv5 YOLOv8涨点专栏:http://t.csdnimg.cn/hmCtL YOLOv7专栏:http://t.csdnimg.cn/lA95R 💡魔改网络、复现论文、优化创新💡

python学习9:python的代码中的数据类型转换

python中数据类型的转换 1.为什么需要转换类型呢&#xff1f; 数据类型之间&#xff0c;在特定的场景下&#xff0c;是可以相互转换的&#xff0c;如字符串转数字&#xff0c;数字转字符串等&#xff1b;数据类型转换&#xff0c;在以后是我们经常使用到的功能&#xff0c;例如…

js工具方法记录

校验数字是否有效的11位手机号 function isValidPhoneNum(value: string) {return /^[1][3,4,5,6,7,8,9][0-9]{9}$/.test(value) }手机号中间4位掩码 function maskPhoneNum(phone: string, space false) {if (!phone) {return }const reg /(\d{3})\d{4}(\d{4})/return pho…

Linux常用命令和基础命令合集---非常推荐

非常好用的Linux通用基础常用命令和高级命令。 下载链接&#xff1a;https://download.csdn.net/download/lishihuijava/89026399

Python Flask 将数据传递给前端

from flask import Flask, render_templateapp Flask(__name__)app.route("/index") def index():data {name: "张三","age": 18,}return render_template("index2.html", datadata)if __name__ __main__:app.run()<!DOCTYPE ht…

OD C卷 - 分披萨

分披萨 有大小不同的奇数块披萨&#xff1b;从A开始轮流取披萨&#xff0c;第一块可以任意选取&#xff0c;其他都必须从缺口开始选&#xff1b;B每次都选最大块的&#xff0c; A知道B的想法&#xff1b;求A能获得的披萨块总和的最大值&#xff1b; 输入描述&#xff1a; 第一…

企业微信变更主体公证怎么弄?

企业微信变更主体有什么作用&#xff1f;现在很多公司都用企业微信来加客户&#xff0c;有时候辛辛苦苦积累了很多客户&#xff0c;但是公司却因为各种各样的原因需要注销&#xff0c;那么就需要通过企业微信变更主体的方法&#xff0c;把企业微信绑定的公司更改为最新的。企业…

Prometheus+Grafana 监控Tongweb嵌入式(by lqw)

文章目录 1.思路2.部署准备3.Grafana仪表盘json文件下载4.tw嵌入式jar包本地引入依赖并测试运行5.运行jmx_prometheus_javaagent-0.19.0.jar形式获取监控数据&#xff08;方法一&#xff09;6.使用Actuator 获取监听数据&#xff08;方法二&#xff09;7.Prometheus部署8.Prome…

【Nebula笔记】简介及安装

目录 一、简介 (一) 什么是图数据库 二、安装 (一) 原生安装 (二) Docker & Docker compose 1. Docker安装 Linux Window 2. 部署NebulaGraph (三) to MAC 三、Nebula Graph Studio (一) 版本兼容性 (二) 原生安装 (三) Docker compose (四) 连接Nebula Gra…

Docker(二):Docker常用命令

docker 查看docker支持的所有命令和参数。 ➜ ~ docker Management Commands:config Manage Docker configscontainer Manage containersimage Manage imagesnetwork Manage networksnode Manage Swarm nodesplugin Manage pluginssecret …

STM32之HAL开发——HAL库框架介绍

HAL库外设设计思想 HAL库借鉴面向对象的设计思想&#xff0c;将外设驱动封装为对象。 HAL库使用主线 HAL使用的主要用在俩个地方&#xff0c;无外乎外设初始化以及外设的使用。想用好这两个功能&#xff0c;我们首先得对外设的封装有一定的了解。 句柄结构体 xx_HandleTypeDef…

JAVA学习笔记19(面向对象编程)

1.面向对象编程 1.1 类与对象 1.类与对象的概念 ​ *对象[属性]/[行为] ​ *语法 class cat {String name;int age; }main() {//cat1就是一个对象//创建一只猫Cat cat1 new Cat();//给猫的属性赋值cat1.name "123";cat1.age 10; }​ *类是抽象的&#xff0c;…

蓝桥杯真题:幸运数字

这道题可以用 integer.string&#xff08;&#xff09;求每个进制的数&#xff0c;但这里要每一位数相加&#xff0c;所以用这个方法会比较麻烦&#xff0c;如下 import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner scan new Sc…

电脑不能读取移动硬盘,但是可以读取U盘解决方法

找到此电脑 右键设备管理器&#xff0c;找到其中的通用串行总线控制器。 注意&#xff0c;凡是插入到电脑当中不能读取的U盘或者移动硬盘&#xff0c;都会在通用串行总线控制器当中显示为USB大容量存储设备 鼠标选中“USB大容量存储设备”&#xff0c;右键卸载它。此时&#x…

软件应用,宠物医院兽医开的处方单管理系统软件教程,宠物店营业软件教程

软件应用&#xff0c;宠物医院兽医开的处方单管理系统软件教程&#xff0c;宠物店营业软件教程 一、前言 以下软件操作教程以 佳易王宠物医院兽医处方软件V17.0为例说明 件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 在开处方单的时候&#xff0c;可以打…

【Flink】WaterMark 实战

WaterMark 实战 1.WaterMark 触发详解2.实际案例 1.WaterMark 触发详解 例如&#xff0c;现在我们有了一个 [12:00:00-12:00:10) 的时间窗口&#xff0c;现在事件如下图所示顺序 A、B、C、D、E、F … 到达。 在未设置 WaterMark 的情况下&#xff0c;当元素 C 到达的时候&…