力扣100热题[哈希]:最长连续序列
原题:128. 最长连续序列
题解:
官方题解:. - 力扣(LeetCode)题解,最长连续序列 :哈希表
官方解题思路是先去重,然后判断模板长度的数值是否存在,存在就刷新,最终找到最大值。
这里我自己研究了下,实际也是暴力解法。纯暴力解法会超时,这里利用了二分法查找的理念
- 首先去重
- 然后排序
- 固定begin,然后找最大的end,返回
使用二分法理念进行查找
- 依次遍历,在
已经找到的最大值,返回
自己尝试了下,部分通过,有些边界值不太好控制,而且输入里面有负数,也不太好计算。
还有一种解题方法,就是在官方题解上做个变化,
- 首先去重
- 然后排序
- 依次遍历,找到满足
的最长子数组,返回其长度。
代码:
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 := 0for 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/2if valDiff > indexDiff && indexDiff != 0 {curMaxDiff = curMaxDiff / 2end = end - curMaxDiffcontinue}// 索引差值 > 数值差值,这种不可能存在,因为已经去重了// 索引差值 = 数值差值,后面可能还有满足条件的,继续找if valDiff == indexDiff {// 刷新最大值if longestStreak > valDiff {break}longestStreak = valDiff// end后移curMaxDiff/2curMaxDiff = curMaxDiff / 2end = end + curMaxDiffcontinue}}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 := 0for num := range numTemp {if num < len(numTemp)-1 && numTemp[num]+1 == numTemp[num+1] {currentNum := numcurrentStreak := 1for currentNum < len(numTemp)-1 && numTemp[currentNum]+1 == numTemp[currentNum+1] {currentNum++currentStreak++}if longestStreak < currentStreak {longestStreak = currentStreak}}}return longestStreak
}
相关文章:
力扣100热题[哈希]:最长连续序列
原题:128. 最长连续序列 题解: 官方题解:. - 力扣(LeetCode)题解,最长连续序列 :哈希表 官方解题思路是先去重,然后判断模板长度的数值是否存在,存在就刷新,…...
python笔记基础--文件和存储数据(7)
目录 1.从文件中读取数据 2.写入文件 3.存储数据 3.1使用json.dump()和json.load() 3.2保存和读取用户生成的数据 3.3重构 1.从文件中读取数据 读取整个文件 with open(data.txt) as file_object: contents file_object.read()print(contents)print(contents.rstrip…...
Vue黑马笔记(最新)
VUE vue是一个用于构建用户界面的渐进式框架 创建一个VUE实例 核心步骤: 准备容器引包(官网)-开发版本/生产版本创建一个vue实例 new vue()指定配置项->渲染数据 el指定挂载点(选择器),指定管理的是哪个容器。dat…...
安全工具介绍 SCNR/Arachni
关于SCNR 原来叫Arachni 是开源的,现在是SCNR,商用工具了 可试用一个月 Arachni Web Application Security Scanner Framework 看名字就知道了,针对web app 的安全工具,DASTIAST吧 安装 安装之前先 sudo apt-get update sudo…...
赋能数据收集:从机票网站提取特价优惠的JavaScript技巧
背景介绍 在这个信息时代,数据的收集和分析对于旅游行业至关重要。在竞争激烈的市场中,实时获取最新的机票特价信息能够为旅行者和旅游企业带来巨大的优势。 随着机票价格的频繁波动,以及航空公司和旅行网站不断推出的限时特价优惠ÿ…...
【大模型】在VS Code(Visual Studio Code)上安装中文汉化版插件
文章目录 一、下载安装二、配置显示语言(一)调出即将输入命令的搜索模式(二)在大于号后面输入:Configure Display Language(三)重启 三、总结 【运行系统】win 11 【本文解决的问题】 1、英文不…...
自定义WordPress顶部的菜单的方法
要自定义WordPress顶部的菜单,你需要使用WordPress的菜单系统。首先,你需要创建自定义菜单,然后将其设置为顶部导航菜单。 以下是创建自定义菜单并设置其为顶部导航菜单的步骤: 登录到WordPress管理界面。转到“外观”>“菜单…...
独孤思维:流量暴涨,却惨遭违规
最近独孤操作虚拟资料短视频,有个很深的感悟。 每天发10条短视频,积累到20天左右,播放量和粉丝数开始暴涨。 虽然很多牛比的比我数据好,但是对于刚做短视频的独孤来说,我已经满足了。 但是又发了10来天,…...
【python 装饰器 - 重试】做一个简易重试装饰器,如果函数执行错误则会自动重新执行,可设置重试次数,对爬虫比较友好
文章日期:2024.03.19 使用工具:Python 类型:装饰器 文章全程已做去敏处理!!! 【需要做的可联系我】 AES解密处理(直接解密即可)(crypto-js.js 标准算法)&…...
Linux线程补充之——同步
一、Linux线程同步 同步是相对于竞争的概念; 同步就是在保证安全的前提下啊,按照一定的顺序访问临界资源; 所有的资源一定是先访问的临界资源,申请失败然后才进行排队的;互斥锁保证的是来访问的进程只允许…...
面试九 设计模式
单例模式通常被归类为创建型设计模式,因为它主要关注如何创建对象的实例,以及如何确保在整个应用程序生命周期中只有一个实例存在。 1.为什么日志模块和数据库连接池需要单例模式 使用单例模式来实现数据库连接池主要有以下几个原因: 全局唯…...
c++和c语言的区别实例
C和C语言在程序设计领域内具有深远的影响,它们不仅丰富了编程的世界,也为软件开发人员提供了强大的工具。虽然C是在C语言的基础上发展起来的,但两者之间存在着一些关键的区别。为了更深入地理解这些不同,本文将从多个维度探讨C和C…...
图论基础|841.钥匙和房间、463. 岛屿的周长
目录 841.钥匙和房间 思路:本题是一个有向图搜索全路径的问题。 只能用深搜(DFS)或者广搜(BFS)来搜。 463. 岛屿的周长 841.钥匙和房间 力扣题目链接 (opens new window) 有 N 个房间,开始时你位于 0…...
把 Taro 项目作为一个完整分包,Taro项目里分包的样式丢失
现象: 当我们把 Taro 项目作为原生微信小程序一个完整分包时,Taro项目里分包的样式丢失,示意图如下: 原因: 在node_modules/tarojs/plugin-indie/dist/index.js文件里,限制了只有pages目录下会被引入app.w…...
腾讯云服务器价格查询系统,2024年1年、3年和5年活动价格表
腾讯云服务器多少钱一年?61元一年起。2024年最新腾讯云服务器优惠价格表,腾讯云轻量2核2G3M服务器61元一年、2核2G4M服务器99元一年可买三年、2核4G5M服务器165元一年、3年756元、轻量4核8M12M服务器646元15个月、4核16G10M配置32元1个月、312元一年、8核…...
第十四届蓝桥杯大赛软件赛省赛Java大学B组
最近正在备考蓝桥杯,报的java b组,顺便更一下蓝桥的 幸运数字 题目 思路:填空题,暴力即可 import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改public class Main {static int trans(int x, int y){int …...
Java二阶知识点总结(七)SVN和Git
SVN 1、SVN和Git的区别 SVN是集中式的,也就是会有一个服务器保存所有代码,拉取代码的时候只能从这个服务器上拉取;Git是分布式的,也就是说每个人都保存有所有代码,如果要获取代码,可以从其他人手上获取SV…...
Java后端八股------设计模式
Coffee可以设计成接口。...
DBO优化GRNN回归预测(matlab代码)
DBO-GRNN回归预测matlab代码 蜣螂优化算法(Dung Beetle Optimizer, DBO)是一种新型的群智能优化算法,在2022年底提出,主要是受蜣螂的的滚球、跳舞、觅食、偷窃和繁殖行为的启发。 数据为Excel股票预测数据。 数据集划分为训练集、验证集、测试集,比例…...
Day 31 贪心01
理论基础 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧。 贪心算法一般分为如下四步: 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
