- 浏览: 172565 次
- 性别:
- 来自: 济南
文章分类
最新评论
leetcode中有关并查集的题目不多,这里现列举一道简单的题目,理解并查集的思想。
Longest Consecutive Sequence
给定一个未排序的整型数组,找出最长的连续子序列。要求时间复杂度为O(n)。
例如:给定nums[] = {100, 4, 200, 1, 3, 2}
输出:4 最长连续子序列为(1,2,3,4)
我们用哈希处理元素是否被访问过,然后从第一个元素开始,分别检查它两边的元素,也就是对它进行加1和减1的操作,检查哈希表中是否存在,记录最大的个数。这就好像以节点构造了几棵树,只要找到最大的那棵树就是结果了。代码如下:
Longest Consecutive Sequence
给定一个未排序的整型数组,找出最长的连续子序列。要求时间复杂度为O(n)。
例如:给定nums[] = {100, 4, 200, 1, 3, 2}
输出:4 最长连续子序列为(1,2,3,4)
我们用哈希处理元素是否被访问过,然后从第一个元素开始,分别检查它两边的元素,也就是对它进行加1和减1的操作,检查哈希表中是否存在,记录最大的个数。这就好像以节点构造了几棵树,只要找到最大的那棵树就是结果了。代码如下:
public class Solution { public int longestConsecutive(int[] nums) { HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); int max = 1; if(nums == null || nums.length == 0) return 0; for(int i : nums) hm.put(i, 0); for(int i = 0; i < nums.length; i++) { int count = 1; int left = -1; int right = 1; if(hm.get(nums[i]) == 1) { continue; } hm.put(nums[i], 1); while(hm.containsKey(nums[i] + left)) { hm.put(nums[i] + left, 1); count ++; left --; } while(hm.containsKey(nums[i] + right)) { hm.put(nums[i] + right, 1); count ++; right ++; } max = Math.max(count, max); } return max; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 446Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 424Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 857Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 549Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
很多有用的资料,,做题时遇到的--- ,acm题里遇到的
并查集(Union-Find Set): 一种用于管理分组的数据结构。它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。 注意:并查集不能将在同一组的元素拆分为两组。 并查集的实现: 用树来实现...
总结信息学竞赛中并查集的拓展应用,详细讲解了两个例题,并给出了同类题目的链接
并查集 Quick Find Quick Union 基于size的优化 基于rank的优化 路径压缩(Path Compression) 图的基础 图的表示(稀疏图和稠密图), 使用邻接表和邻接矩阵 相邻节点迭代器 图的算法框架 深度优先遍历和联通分量 寻路 ...
我这里总结了几道并查集的题目: 547.朋友圈 721. 账户合并 990. 等式方程的可满足性 并查集概述 并查集算法,主要是解决图论中「动态连通性」问题的 Union-Find 算法解决的是图的动态连通性问题,这个算法本身不难...
并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题。 有一个联合- 查找算法定义了两个用于此数据结构的操作: Find :确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union...
本人2年来ACM经验分类总结,各个分类附有多种类型的例子,从浅到深,循序渐进,希望对你能有所帮助主要包括以下几类: 素数因子组合 字典树 树状数组 并查集 最大匹配
包含高精计算、快速幂、背包问题、区间DP、并查集、树状结构等算法模板
两年ACM竞赛所有算法总结,这里包含最短路、最小生成树、动态规划、字符串匹配、博弈、大数、Hash、排序、二分匹配、并查集、最大流、欧拉函数、扩展欧几里得等
并查集扩展(friend_enemy) 堆(binary) 堆(mapped) 矩形切割 线段树 线段树扩展 线段树应用 子段和 子阵和 其他\ 大数(整数类封装) 分数 矩阵 线性方程组(gauss) 日期 线性相关 数论\ 阶乘最后非零位...
Leetcode经典01背包 LeetCode-2020 马上进入2020找实习冲刺阶段,我决定以天为单位,记录每天做的LeetCode习题,方便后期整理。 C++文档神器推荐:cppreference.chm 1 LeetCode刷题记录(每日...并查集是一种树形数据结
并查集 图 设计 拓扑排序 字典树 树状数组 线段树 二叉搜索树 递归 脑筋急转弯 记忆化 队列 极小化极大 蓄水池抽样 几何 Map 数组 哈希表 链表 数学 双指针 字符串 二分查找 分治算法 动态规划 回溯算法 Random ...
1.5 总结 第2章 集合论和谓词逻辑 2.1 自然语言表述到数学表示的转换 2.1.1 严格定义(well-Definedness) 2.1.2 相等、恒等和同一性 2.1.3 数学命名约定 2.1.4 数字 2.1.5 上下文 2.1.6 函数、参数和变量 ...
用于总结刷题经验,帮助后面使用参考,尤其是常用的二分法、动态规划、线段树、滑动窗口、BFS、DFS、并查集、分支限界法
访问各个部委的网站,也能查到很多业务数据,如发改委的项目立项库、工商局的企业信用库、国土资源部的土地证库、国家安监总局的煤矿安全预警信息库、各类工程招标信息库等等。这是一个非常大的进步,也是这么多年...
使用Top语句限制返回的数据集 SELECT ID,TITLE,UNITPRICE FROM BOOKS WHERE AUTHOR = '马骏 主编' --数据库会扫描整个Books表的数据 修改为: SELECT TOP 1 ID,TITLE,UNITPRICE FROM BOOKS WHERE AUTHOR = '马骏 ...
函数依赖的公理系统Amstrong公理的内容及其正确性、逻辑蕴含和闭包、公理的完备性、闭包的计算、函数依赖集的等价和最小化;规范化1NF、2NF、3NF、BCNF;模式分解。 第三部分是第十章:数据库设计。完善E-R模型中的...