Leetcode406/435/56之带排序的贪心

带排序的贪心例题

需要注意

• 怎么排序？降序还是升序
• 几维排序？二维数组两个维度是否需要都排序
• 是否需要辅助队列?通常需要用到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()][]);

    }