算法笔记|Day26贪心算法IV
算法笔记|Day26贪心算法IV
-
☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球
-
- 题目分析
- 代码
-
☆☆☆☆☆leetcode 435. 无重叠区间
-
- 题目分析
- 代码
-
☆☆☆☆☆leetcode 763.划分字母区间
-
- 题目分析
- 代码
☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球
题目链接：leetcode 452. 通过最小数目箭头穿透气球
题目分析
首先将points中的各个区间按照左起始位置进行升序排序。随后依次比较每一个区间的起始位置与其前驱区间的结束位置。如果某区间起始位置超出其前后驱区间结束位置，则表明两者之间无交集，并且计数器count需增加1次。反之若某区间起始位置低于其前后驱区间结束位置时，则两者存在交集，并且只需更新当前区间的结束位置为其自身结束位置与上驱区间结束位置的较小者。
代码
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
int count=1;
for(int i=1;i<points.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. 无重叠区间** 标签编号：435** 问题简述：请在给定的无重叠区间列表中找到满足特定条件的最大子集。
题目分析
首先将intervals中的各个区间按照左起始位置从小到大排序；随后依次进行比对：针对每个区间的起始位置与它前面相邻区间的结束位置进行比对；如果当前区间的起始位置大于其后继相邻区间的结束位置，则表示这两个相邻区域没有交集；反之则表示存在交集，在这种情况下就需要将计数器count增加1，并将结束位置设定为这两个相邻区域中较早的那个结束的位置。
代码
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
int count=0;
for(int i=1;i<intervals.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-left+1），将其累加到结果数组res中；同时将左指针设置为右指针加一（即 left = right + 1），以此类推直到完成整个字符串的所有遍历操作。
代码
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res=new ArrayList<>();
int last[]=new int[26];
int left=0,right=0;
for(int i=0;i<s.length();i++)
last[s.charAt(i)-'a']=i;
for(int i=0;i<s.length();i++){
right=Math.max(right,last[s.charAt(i)-'a']);
if(i==right){
res.add(right-left+1);
left=right+1;
}
}
return res;
}
}