435
题目:
给定一个区间的集合 intervals
,其中 intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
题目链接:435. 无重叠区间 - 力扣(LeetCode)
思路:
先按起始位置升序排列,然后判断是否有重合,如果重合就count+1,然后判断哪个区间的end更大,两个区间肯定要删除一个,end更大的容易和后续重合故删。
详情:代码随想录 (programmercarl.com)
代码:
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])
continue;
else{
count++;
if(intervals[i-1][1]<=intervals[i][1]) //i的终止位置大,更容易影响后续故删
{
intervals[i][0]=intervals[i-1][0];
intervals[i][1]=intervals[i-1][1];
}
else{//i-1的终止位置大,更容易影响后续故删
intervals[i-1][0]=intervals[i][0];
intervals[i-1][1]=intervals[i][1];
}
}
}
return count;
}
}
763
题目:
给你一个字符串 s
。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s
。
返回一个表示每个字符串片段的长度的列表。
题目链接:763. 划分字母区间 - 力扣(LeetCode)
思路:
使用for循环,在其中判断当前对应的字符在字符串最后一次出现下标,在这个下标之前的所有字符都要计算lastindexof,当i==index则是一个分段。
详情:代码随想录 (programmercarl.com)
代码:
class Solution {
public List<Integer> partitionLabels(String s) {
List <Integer> len =new ArrayList<Integer>();
int index =-1;//片段的end
int flag=0;//辅助标识片段start
int start=-1;
for(int i=0;i<s.length();i++)
{
if(flag==0)
{
start=i;
flag=1;
}
String str =Character.toString(s.charAt(i));
int last =s.lastIndexOf(str);
if(last > index)
index = last;
if(i==index)
{
int temp =index-start+1;
len.add(temp);
flag =0;
start=-1;
index =-1;
}
}
return len;
}
}
56
题目:
以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
题目链接:56. 合并区间 - 力扣(LeetCode)
思路:
先判断前者和后者是否有交集,有的话将合并的结果存在后者,然后另开一个动态数组存储结果,只需要存合并后的区间和不相交的区间。
详情:代码随想录 (programmercarl.com)
代码:
class Solution {
public int[][] merge(int[][] intervals) {
int index = intervals.length - 1;//为了处理24行的边界情况
if(index==0) return intervals;//只有一个区间
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));//按start升序排序
for (int i = 1; i < index + 1; i++) { //有交集则将i-1和i的区间合并存储到i里
if (intervals[i][0] > intervals[i - 1][1])
continue;
else {
intervals[i][0] = Math.min(intervals[i - 1][0],intervals[i][0]);
intervals[i][1] = Math.max(intervals[i-1][1],intervals[i][1]);
}
}
LinkedList<int[]> que = new LinkedList<>();
int count = 0;
for (int i = 0; i < index; i++) { //判断前者是否是后者子区间,如果是则继续,如果不是则保存
if (intervals[i][0] >= intervals[i + 1][0] && intervals[i][1] <= intervals[i + 1][1])
continue;
else {
que.add(intervals[i]);
count++;
}
}
//边界情况
if (intervals[index - 1][0] >= intervals[index][0] && intervals[index - 1][1] <= intervals[index][1]) {
que.add(intervals[index]);
count++;
} else {
que.add(intervals[index]);
count = count + 1;
}
return que.toArray(new int[count][]);
}
}