唐山住房和城乡建设局网站,兴安盟网站建设,app与网站的关系,网站二次开发模板算法笔记|Day26贪心算法IV ☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球题目分析代码 ☆☆☆☆☆leetcode 435. 无重叠区间题目分析代码 ☆☆☆☆☆leetcode 763.划分字母区间题目分析代码 ☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球
题目链接#xff1a;leetcode … 算法笔记|Day26贪心算法IV ☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球题目分析代码 ☆☆☆☆☆leetcode 435. 无重叠区间题目分析代码 ☆☆☆☆☆leetcode 763.划分字母区间题目分析代码 ☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球
题目链接leetcode 452. 用最少数量的箭引爆气球
题目分析
首先对points各个范围按左端点升序排列依次比较每一个范围左端点与前一个范围右端点。若该范围左端点大于前一个范围右端点说明没有重叠需要设计次数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;}
}提示 Arrays.sort(points, (a, b) - { return a[0] - b[0]; }); 使用了简单的减法来比较两个点的x坐标。虽然这在大多数情况下可以工作但它有一个潜在的问题如果a[0]和b[0]的差值非常大那么返回的结果可能会是一个大的整数这可能会导致整数溢出Integer Overflow。 Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0])); 使用了Integer.compare方法。这个方法接受两个整数作为参数并返回一个整数表示第一个参数与第二个参数的比较结果。如果第一个参数小于第二个参数则返回负数如果它们相等则返回0如果第一个参数大于第二个参数则返回正数。使用Integer.compare方法的好处是它避免了整数溢出的问题在处理大数时更安全并且由于它是专门为比较整数而设计的所以代码的可读性也更好。
☆☆☆☆☆leetcode 435. 无重叠区间
题目链接leetcode 435. 无重叠区间
题目分析
首先对intervals各个区间按左端点升序排列依次比较每一个区间左端点与前一个区间右端点。若该区间左端点大于前一个范围右端点说明没有重叠无需操作若该区间左端点小于前一个区间右端点说明有重叠计数count加一同时更新右端点为该区间右端点与前一区间右端点的最小值。
代码
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)-Integer.compare(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][1],intervals[i][1]);}}return count;}
}☆☆☆☆☆leetcode 763.划分字母区间
题目链接leetcode 763.划分字母区间
题目分析
首先采用哈希数组记录每个字母在该字符串中最后出现的位置即遍历后序号覆盖。初始left和right赋值为0依次遍历字符串的每个元素若遍历到的元素最后出现位置大于当前right值则更新right值若遍历到right则说明得到了一个符合提议的区间记录该区间长度right-left1并加到res数组中同时更新left值为right1直至遍历结束。
代码
class Solution {public ListInteger partitionLabels(String s) {ListInteger resnew ArrayList();int last[]new int[26];int left0,right0;for(int i0;is.length();i)last[s.charAt(i)-a]i;for(int i0;is.length();i){rightMath.max(right,last[s.charAt(i)-a]);if(iright){res.add(right-left1);leftright1;}}return res;}
}
