南京模板建站定制网站,wordpress排名,裕华区建设局网站,设计网站名字前言#xff1a;今天的三道题目都是重叠区间的问题。
452. 用最少数量的箭引爆气球
思路#xff1a;局部最优#xff1a;当气球出现重叠#xff0c;一起射#xff0c;所用弓箭最少#xff1b; 全局最优#xff1a;把所有气球射爆所用弓箭最少。 按照起始位置排序…前言今天的三道题目都是重叠区间的问题。
452. 用最少数量的箭引爆气球
思路局部最优当气球出现重叠一起射所用弓箭最少 全局最优把所有气球射爆所用弓箭最少。 按照起始位置排序如果气球重叠了重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
注意这个解法的以巧妙之处是一直在比较当前气球的左边界和前一个气球的右边界如果当前气球的左边界大于前一个气球的右边界则需要多加一支箭否则的话就更新当前气球的右边界为两个气球右边界较短的那一个再去进行比较看看是不是还有重叠的气球。
代码如下
class Solution {public int findMinArrowShots(int[][] points) {if(points.length0) return 0;int result1;Arrays.sort(points,(a,b)-Integer.compare(a[0],b[0]));for(int i1;ipoints.length;i){if(points[i][0]points[i-1][1]) result;else points[i][1]Math.min(points[i][1],points[i-1][1]);}return result;}
}454. 无重叠区间
思路这个题和气球题的思路差不多先根据左边界的值进行排序遍历i的左边界和i-1的右边界如果i的左边界小于i-1的右边界需要删除的区间数加一并将i和i-1中较小的右边界赋值给i的右边界贪心尽量留下右边界小的减少重叠的概率。
注意这个题有一个和气球题不同的点气球打破之后就没有了且要求重叠区间因此可以将i和i-1中较小的右边界赋值给i的右边界但这个题
代码如下
class Solution {public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length1) return 0;Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0]));int result0;for(int i1;iintervals.length;i){if(intervals[i][0]intervals[i-1][1]){result;intervals[i][1]Math.min(intervals[i][1],intervals[i-1][1]);}}return result;}
}763.划分字母区间
这个题目不太有思路。看题解发现在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。 步骤如下
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点记录该区间的长度。
代码如下
class Solution {public ListInteger partitionLabels(String s) {int[] edgenew int[26];LinkedListInteger resultnew LinkedList();for(int i0;is.length();i){edge[s.charAt(i)-a]i;}int idx0;int last-1;for(int i0;is.length();i){idxMath.max(edge[s.charAt(i)-a],idx);if(idxi){result.add(i-last);lasti;}}return result;}
}
