网站名称创意大全,wap手机建站平台,西樵乐从网站建设,wordpress首页显示全部内容目录
128.最长连续序列 228.汇总区间 56.合并区间 57.插入区间 452.用最少数量的箭引爆气球 128.最长连续序列 题意#xff1a; 给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。 请你设计并…目录
128.最长连续序列 228.汇总区间 56.合并区间 57.插入区间 452.用最少数量的箭引爆气球 128.最长连续序列 题意 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 【输入样例】 nums [100,4,200,1,3,2] 【输出样例】 4 解释最长数字连续序列是[1,2,3,4] 解题思路哈希表 1. 使用setset不包含重复元素因此我们先将nums中的元素存入到set中实现一个去重效果。 2. 遍历set当一个数num的前一位数num-1不在数组中时表示它可能是连续序列的第一位持续遍历看他的下一位num1是否在集合中如果存在统计长度直至找不到。 class Solution {public int longestConsecutive(int[] nums) {int count 0;SetInteger 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 ! ba 如果 a b 【输入样例】 nums [012457] 【输出样例】 [0-2,4-5,7] 解题思路枚举 class Solution {public ListString summaryRanges(int[] nums) {ListString list new ArrayList();if(nums.length 0){return list;}if(nums.length 1){list.add(String.valueOf(nums[0]));return list;}int i0;while(i nums.length){int low i;i;while(inums.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) {Listint[] 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 i1;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.第三种情况时除了12外的情形代表原区间第i个元素与插入区间有重叠通过判断两个区间的最大值和最小值来更新左右区间。 4. 最后一种情况时原区间已经遍历完毕后新区间还没插入直接插入到最后。 class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {boolean isInsert false;//是否已经插入Listint[] list new ArrayList();int leftBounds newInterval[0];//新区间的左边界int rightBounds newInterval[1];//新区间的右边界for(int i0;iintervals.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 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后可以无限地前进。 给你一个数组 points 返回引爆所有气球所必须射出的 最小 弓箭数 。 提示: 1 points.length 105points[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 i1;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%
