Leetcode40643556题解：如何实现带排序的贪心算法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计800个文字，预计阅读时间需要4分钟。
带排序的贪心例题+需要注意+如何排序？降序还是升序+几维排序？二维数组两个维度是否都需要排序+是否需要辅助队列？通常需要用到位移数组+list.add(index, value); // 在指定Index插入value
带排序的贪心例题
需要注意
- 怎么排序？降序还是升序
- 几维排序？二维数组两个维度是否需要都排序
- 是否需要辅助队列?通常需要用到LinkedLIst
- list.add(index,value);//在指定Index插入value
- list.toArray(new int[list.size()][]);//需要指定二维中第一维的长度，第二维可不用显示指定
Leetcode406-根据身高重建队列
- 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
- 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
- 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
- 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(p1,p2)->{
if(p1[0]==p2[0]){
return p1[1]-p2[1];
}else{
return p2[0]-p1[0];
}
});
LinkedList<int[]> list=new LinkedList<>();
for(int i=0;i<people.length;i++){
list.add(people[i][1],people[i]);
}
return list.toArray(new int[people.length][]);
}
Leetcode435-无重叠区间
- 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
- 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
- 输出: 1
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a1,a2)->{
if(a1[1]==a2[1]){
return a2[0]-a1[0];
}else{
return a1[1]-a2[1];
}
});
int num=1;
int lastIndex=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>=lastIndex){
num++;
lastIndex=intervals[i][1];
}
}
return intervals.length-num;
}
Leetcode56-合并区间
- 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
- 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出：[[1,6],[8,10],[15,18]]
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(a1,a2)->{
if(a1[0]==a2[0]){
return a2[1]-a1[1];
}else{
return a1[0]-a2[0];
}
});
LinkedList<int[]> list=new LinkedList<>();
int lastIndex=intervals[0][1];
int beginIndex=intervals[0][0];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]<=lastIndex){
lastIndex=Math.max(lastIndex,intervals[i][1]);
}else{
list.add(new int[]{beginIndex,lastIndex});
lastIndex=intervals[i][1];
beginIndex=intervals[i][0];
}
}
list.add(new int[]{beginIndex,lastIndex});//最后一个元素
return list.toArray(new int[list.size()][]);
}
本文共计800个文字，预计阅读时间需要4分钟。
带排序的贪心例题+需要注意+如何排序？降序还是升序+几维排序？二维数组两个维度是否都需要排序+是否需要辅助队列？通常需要用到位移数组+list.add(index, value); // 在指定Index插入value
带排序的贪心例题
需要注意
- 怎么排序？降序还是升序
- 几维排序？二维数组两个维度是否需要都排序
- 是否需要辅助队列?通常需要用到LinkedLIst
- list.add(index,value);//在指定Index插入value
- list.toArray(new int[list.size()][]);//需要指定二维中第一维的长度，第二维可不用显示指定
Leetcode406-根据身高重建队列
- 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
- 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
- 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
- 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(p1,p2)->{
if(p1[0]==p2[0]){
return p1[1]-p2[1];
}else{
return p2[0]-p1[0];
}
});
LinkedList<int[]> list=new LinkedList<>();
for(int i=0;i<people.length;i++){
list.add(people[i][1],people[i]);
}
return list.toArray(new int[people.length][]);
}
Leetcode435-无重叠区间
- 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
- 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
- 输出: 1
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a1,a2)->{
if(a1[1]==a2[1]){
return a2[0]-a1[0];
}else{
return a1[1]-a2[1];
}
});
int num=1;
int lastIndex=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>=lastIndex){
num++;
lastIndex=intervals[i][1];
}
}
return intervals.length-num;
}
Leetcode56-合并区间
- 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
- 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出：[[1,6],[8,10],[15,18]]
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(a1,a2)->{
if(a1[0]==a2[0]){
return a2[1]-a1[1];
}else{
return a1[0]-a2[0];
}
});
LinkedList<int[]> list=new LinkedList<>();
int lastIndex=intervals[0][1];
int beginIndex=intervals[0][0];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]<=lastIndex){
lastIndex=Math.max(lastIndex,intervals[i][1]);
}else{
list.add(new int[]{beginIndex,lastIndex});
lastIndex=intervals[i][1];
beginIndex=intervals[i][0];
}
}
list.add(new int[]{beginIndex,lastIndex});//最后一个元素
return list.toArray(new int[list.size()][]);
}