算法训练营Day36(贪心-重叠区间)
2024-01-07 23:43:02
都算是?重叠区间?问题,大家可以好好感受一下。?都属于那种看起来好复杂,但一看贪心解法,惊呼:这么巧妙!?
还是属于那种,做过了也就会了,没做过就很难想出来。
不过大家把如下三题做了之后,?重叠区间?基本上差不多了
435.?无重叠区间?
我这里先给一下为什么不取最大值的问题吧,我没看视频自己做的时候写的
如果用max的话,就是直接计算重复区间了,但是这道题还要删去,所以直接取右边界的最小值
答案:
这是我写的,和卡哥的也不一样,很简单
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a,b)-> {
return 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;
}
}
763.划分字母区间?
题意难,听卡哥讲,easy很多。
class Solution {
public List<Integer> partitionLabels(String s) {
int [] hash = new int[27];
//记录每个字母的最远位置
for(int i = 0;i<s.length();i++){
hash[s.charAt(i)-'a'] = i;
}
List<Integer> res = new ArrayList<>();
//找left和right
int left= 0,right=0;
for(int i = 0;i<s.length();i++){
right = Math.max(right,hash[s.charAt(i)-'a']);
if(i == right){
res.add(right-left+1);
//更新边界
left = i+1;
}
}
return res;
}
}
56.?合并区间?
这个很easy
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
List<int[]> res = new ArrayList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for(int i =1;i< intervals.length;i++){
if(intervals[i][0]<=end){
//更新右边界
end = Math.max(end,intervals[i][1]);
}else{
//收集结果
int [] subRes = new int[]{start,end};
res.add(subRes);
//更新 新的begin 和end
start = intervals[i][0];
end = intervals[i][1];
}
}
res.add(new int[]{start,end});
return res.toArray(new int[res.size()][]);
}
}
文章来源:https://blog.csdn.net/weixin_65728526/article/details/135373900
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!