制作网页的网站费用属于资本性支出吗,网络规划与设计专业,做网站充值系统,十八款禁用黄台入口app力扣爆刷第148天之贪心算法五连刷#xff08;区间合并#xff09; 文章目录 力扣爆刷第148天之贪心算法五连刷#xff08;区间合并#xff09;一、406. 根据身高重建队列二、452. 用最少数量的箭引爆气球三、435. 无重叠区间四、763. 划分字母区间五、56. 合并区间六、738.…力扣爆刷第148天之贪心算法五连刷区间合并 文章目录 力扣爆刷第148天之贪心算法五连刷区间合并一、406. 根据身高重建队列二、452. 用最少数量的箭引爆气球三、435. 无重叠区间四、763. 划分字母区间五、56. 合并区间六、738. 单调递增的数字 一、406. 根据身高重建队列
题目链接https://leetcode.cn/problems/queue-reconstruction-by-height/description/ 思路本题身高排序有两个维度一个是身高一个是排队人数让我们按照这两个维度对数组进行排序使其满足要求。 维度要分开看当身高相同时排队元素需要升序排列当身高不同时身高需要降序排列如果身高升序排列将导致排在前面的人数为0。 按照以上要求排列好以后一定是身高高的都排在前面身高矮的排在后面身高相同的排队人数升序所以这个时候就按照排队人数把元素插入新数组即可实现排序。
class Solution {public int[][] reconstructQueue(int[][] people) {Listint[] list new ArrayList();// 身高相同数量升序身高不同身高降序Arrays.sort(people, (a, b) - {if(a[0] b[0]) return a[1] - b[1];else return b[0] - a[0];});for(int[] nums : people) {list.add(nums[1], nums);}return list.toArray(new int[list.size()][]);}
}
二、452. 用最少数量的箭引爆气球
题目链接https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/ 思路求用最少数量的箭引爆气球本质上是求区间的交集有几个交集有几个就需要几个箭求交集只需要先按照左区间进行排序然后选择最小的右边界即可。
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));int count 1, right points[0][1];for(int[] nums : points) {if(nums[0] right) {count;right nums[1];}else{right Math.min(right, nums[1]);}}return count;}
}三、435. 无重叠区间
题目链接https://leetcode.cn/problems/non-overlapping-intervals/description/ 思路本题其实求的是无重叠区间的个数用总区间个数减去无重叠区间的个数即为要去掉的区间的个数。 求把多个区间去掉最少区间成为无重叠区间首先先把所有的区间按照左边界排序然后维护一个区间进行比较如果当前区间的左边界位于其中说明区间重叠了是需要计数的作为去掉一个区间然后右边界改成相交的两个区间的最小的右边界这样可以尽最大努力避免区间重叠如果当前区间的左边界位于维护区间的右边界之外则说明无重叠区间又因为都是按照左边界排序的只需要把右边界改成最右边的边界即可。
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]));int count 0, left intervals[0][0], right intervals[0][1];for(int i 1; i intervals.length; i) {if(intervals[i][0] right) {right intervals[i][1];}else{count;right Math.min(right, intervals[i][1]);}}return count;}
}四、763. 划分字母区间
题目链接https://leetcode.cn/problems/partition-labels/description/ 思路划分字母区间尽可能划分较大的区间让所有字母只出现在一个区间中所以只需要先遍历一遍字符串然后记录下来各个字母出现的最远距离然后再遍历一遍字符串不断更新当前字母最远出现的距离只要遍历到这个距离就划分出了一个区间。以此往复即可。
class Solution {ListInteger list new ArrayList();public ListInteger partitionLabels(String s) {int[] nums new int[26];for(int i 0; i s.length(); i) {int t s.charAt(i) - a;nums[t] i;}int max 0, pro -1;for(int i 0; i s.length(); i) {max Math.max(max, nums[s.charAt(i)-a]);if(i max) {list.add(i-pro);pro i;}}return list;}
}五、56. 合并区间
题目链接https://leetcode.cn/problems/merge-intervals/ 思路和前面的几道区间相关的题来说非常简单就是判断当前区间的左边界是否位于上一个区间之中位于就合并不位于就是单独的区间。
class Solution {public int[][] merge(int[][] intervals) {if(intervals.length 1) return intervals;Arrays.sort(intervals, (a, b) - a[0] - b[0]);Listint[] list new ArrayList();for(int i 1; i intervals.length; i) {if(intervals[i][0] intervals[i-1][1]) {intervals[i][0] intervals[i-1][0];intervals[i][1] Math.max(intervals[i][1], intervals[i-1][1]);}else{int[] temp {intervals[i-1][0], intervals[i-1][1]};list.add(temp);}}list.add(new int[]{intervals[intervals.length-1][0], intervals[intervals.length-1][1]});int[][] result new int[list.size()][2];for(int i 0; i list.size(); i) {result[i] list.get(i);}return result;}
}六、738. 单调递增的数字
题目链接https://leetcode.cn/problems/monotone-increasing-digits/description/ 思路将一个数改成距离它最小的单调递增的数其实很简单如果两个数逆序如53那么最大的递增数为49那么只需要从右边往左边找找到第一个逆序逆序后面的都改成9即可。
class Solution {public int monotoneIncreasingDigits(int n) {String s String.valueOf(n);char[] cnum s.toCharArray();int k cnum.length;for(int i cnum.length-2; i 0; i--) {if(cnum[i] cnum[i1]){cnum[i]--;k i 1;}}for(int i k; i cnum.length; i) {cnum[i] 9;}return Integer.parseInt(String.valueOf(cnum));}
}
