【LeetCode-经典面试150题-day11】

目录

128.最长连续序列

 228.汇总区间

 56.合并区间

 57.插入区间

 452.用最少数量的箭引爆气球

---

 

128.最长连续序列

题意：

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

【输入样例】

nums = [100,4,200,1,3,2]

【输出样例】

4

解释：最长数字连续序列是[1,2,3,4]

解题思路：哈希表

1. 使用set，set不包含重复元素；因此我们先将nums中的元素存入到set中，实现一个去重效果。

2. 遍历set，当一个数num的前一位数num-1不在数组中时，表示它可能是连续序列的第一位，持续遍历看他的下一位num+1是否在集合中，如果存在统计长度，直至找不到。

class Solution {public int longestConsecutive(int[] nums) {int count = 0;Set<Integer> numSet = new HashSet<>();for(int num : nums){numSet.add(num);}int tempCount;for(int num : numSet){if(!numSet.contains(num-1)){tempCount = 1;//第一个数while(numSet.contains(++num)){++tempCount;//继续查找}count = Math.max(count,tempCount);}}return count;}
}

时间： 击败了84.51%

内存： 击败了89.54%

 228.汇总区间

题意：

给定一个  无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b" ，如果 a != b
• "a" ，如果 a == b

【输入样例】

nums = [0，1，2，4，5，7]

【输出样例】

["0->2","4->5","7"]

解题思路：枚举

class Solution {public List<String> summaryRanges(int[] nums) {List<String> list = new ArrayList<>();if(nums.length == 0){return list;}if(nums.length == 1){list.add(String.valueOf(nums[0]));return list;}int i=0;while(i < nums.length){int low = i;++i;while(i<nums.length && nums[i] == nums[i-1]+1){++i;}int high = i-1;String str;if(low == high){str = String.valueOf(nums[low]);}else{str = nums[low]+"->"+nums[high];}list.add(str);}return list;}
}

时间： 击败了51.34%

内存： 击败了16.07%

 56.合并区间

题意：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

【输入样例】

intervals = [[1,3],[2,6],[8,10],[15,18]]

【输出样例】

[[1,6],[8,10],[15,18]]

解题思路：排序+枚举判断

1.首先，按照给出的二维数组的左区间进行升序排序

2.枚举判断，变量leftBound和rightBound记录当前的左边界和右边界；枚举，如果下一个区间的左边界小于当前的rightBound，证明两个区间可以合并在一起，修改右边界（不是盲目的修改，要修改成较大值，如(1,6),(2,4),直接修改会变成(1,4)，所以要判断）；如果下一个区间的左边界大于rightBound，证明当前的区间没法合并了，添加到数组中。

class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new ArrayList<>();    //按照左边界排序Arrays.sort(intervals, (x,y)-> Integer.compare(x[0],y[0]));//initial start 是最小左边界int leftBound = intervals[0][0];int rightBound = intervals[0][1];//右边界for(int i=1;i< intervals.length;++i){//如果左边界大于上一个有边界if(intervals[i][0] > rightBound){//加入区间，更新start，加入的是上一个区间res.add(new int[]{leftBound,rightBound});leftBound = intervals[i][0];rightBound = intervals[i][1];}else{//更新右边界rightBound = Math.max(rightBound, intervals[i][1]);}}res.add(new int[]{leftBound,rightBound});return res.toArray(new int[res.size()][]);}
}

时间： 击败了80.99%

内存： 击败了92.51%

 57.插入区间

题意：

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

【输入样例】

intervals = [[1,3],[6,9]], newInterval = [2,5]

【输出样例】

[[1,5],[6,9]]

解题思路：与上一题类似，但是这一题不需要排序

枚举原区间，考虑四种情况：

1. 当原区间第i个元素的右边界小于插入区间的左边界时，直接插入原区间第i个元素；

2.当原区间第i个元素的左边界大于插入区间的右边界时，插入新区间，并标注已经插入，后续判断到此情况时直接添加原区间的元素；

3.第三种情况时除了1，2外的情形，代表原区间第i个元素与插入区间有重叠，通过判断两个区间的最大值和最小值来更新左右区间。

4. 最后一种情况时原区间已经遍历完毕后，新区间还没插入，直接插入到最后。

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {boolean isInsert = false;//是否已经插入List<int[]> list = new ArrayList<>();int leftBounds = newInterval[0];//新区间的左边界int rightBounds = newInterval[1];//新区间的右边界for(int i=0;i<intervals.length;++i){if(intervals[i][0] > rightBounds){if(!isInsert){list.add(new int[]{leftBounds,rightBounds});isInsert = true;}list.add(new int[]{intervals[i][0],intervals[i][1]});}else if(intervals[i][1] < leftBounds){//在插入区间的左侧list.add(new int[]{intervals[i][0],intervals[i][1]});}else{//有交集，要合并区间leftBounds = Math.min(leftBounds,intervals[i][0]);rightBounds = Math.max(rightBounds,intervals[i][1]);}}//如果遍历完还没有插入，添加到最后if(!isInsert){list.add(new int[]{leftBounds,rightBounds});}return list.toArray(new int[list.size()][]);}
}

时间： 击败了97.50%

内存： 击败了67.95%

 452.用最少数量的箭引爆气球

题意：

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

【输入样例】

points = [[10,16],[2,8],[1,6],[7,12]]

【输出样例】

2

解题思路：与56.合并区间类似，区别是现在更新右边界的时候，要按小的来。

class Solution {public int findMinArrowShots(int[][] points) {  //按照左边界排序Arrays.sort(points, (x,y)-> Integer.compare(x[0],y[0]));int result = 1;for(int i=1;i< points.length;++i){//如果左边界大于上一个有边界if(points[i][0] > points[i-1][1]){//加入区间，更新start，加入的是上一个区间++result;}else{//更新右边界points[i][1] = Math.min(points[i-1][1], points[i][1]);}}// int result = res.size;return result;}
}

时间： 击败了18.88%

内存： 击败了82.02%