解释seo网站推广,wordpress+move插件,如何生成自己的网站,龙岩天宫山缆车收费452.用最少数量的箭引爆气球
贪心算法
重合最多的气球射一箭#xff0c;就是局部用箭数量最少的#xff0c;全局的用箭数量就是最少的。
首先对二维数组进行排序#xff0c;这样就可以让气球更加紧凑。
思路#xff1a;当前气球是否和上一个气球区间重合#xff0c;如…452.用最少数量的箭引爆气球
贪心算法
重合最多的气球射一箭就是局部用箭数量最少的全局的用箭数量就是最少的。
首先对二维数组进行排序这样就可以让气球更加紧凑。
思路当前气球是否和上一个气球区间重合如果不重合那就count如果重合要去更新重合气球的重合区间最小的右边界。因为这样就可以叠加重合的气球直到有不重合的气球出现就可以射一箭将重合的气球射爆。
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a,b)-Integer.compare(a[0],b[0]));int count1;for(int i1; ipoints.length; i){if(points[i][0]points[i-1][1]){count;}else{points[i][1]Math.min(points[i-1][1],points[i][1]);}}return count;}
}
435.无重叠区间
与上一题一模一样
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)-a[0]-b[0]);int count0;for(int i1; iintervals.length; i){if(intervals[i][0]intervals[i-1][1]){count;intervals[i][1]Math.min(intervals[i][1],intervals[i-1][1]);}}return count;}
}
763.划分字母空间
思路遍历字符数组找到每个元素出现的最大位置然后遍历数组找到所有遍历过的字母最大出现的位置并且当前在数组的位置等于其元素最大位置就是边界位置。
class Solution {public ListInteger partitionLabels(String s) {ListInteger listnew ArrayList();int[] edgenew int[26];char[] charss.toCharArray();for(int i0; ichars.length; i){edge[chars[i]-a]i;}int idx0;int last-1;for(int i0; ichars.length; i){idxMath.max(idx,edge[chars[i]-a]);if(iidx){list.add(i-last);lasti;}}return list;}
}
