LeetCode greedy topic java code thinking solution

Constantly updating

Problem solution

455 distribution of biscuits

Suppose you are a great parent and want to give your children some cookies. However, each child can only give one biscuit at most. For each child i, there is an appetite value gi, which is the minimum size of biscuits that can satisfy the children's appetite; And every cookie j has a size sj. If sj > = gi, we can distribute the biscuit j to child i, and the child will be satisfied. Your goal is to meet as many children as possible and output this maximum value.

Topic analysis: this topic is a very classic and simple greedy problem, which can comfortably introduce greedy ideas.
Our goal is to meet as many children as possible. That is, we only consider meeting the number of children, and the children themselves have no priority. So at this time, we first meet the children with small appetite and start with small biscuits

So here's our greedy idea: start small.
Double pointers are used in the code, which will be faster. The use of double pointers is based on the fact that satisfied children or biscuits can no longer be used, and biscuits that cannot be used are no longer considered.

class Solution {
    public int findContentChildren(int[] g,int[] s){
        Arrays.sort(g);
        Arrays.sort(s);
        int result = 0;
        int gi=0,si=0;
        while (gi < g.length && si < s.length) {
            if (g[gi] <= s[si]) {
                gi++;
            }
            si++;
        }

        return gi;
    }
}

435 non overlapping interval

Topic details: given a set of intervals, find the minimum number of intervals to be removed so that the remaining intervals do not overlap each other.

Topic analysis: this topic is a regional overlapping problem. Many of the following problems are variants of it, which need to be paid great attention and understood well. Of course, this problem can also be done with dynamic programming, but the time efficiency is slightly lower, and greed is more suitable. At the same time, its variants are also very easy to do with greed.

Because it is a region, it can be said that it is distributed in one-dimensional space, so we need to sort them here. This is convenient for us to analyze. Otherwise, the problem will be very complicated.
The sorting rule is to sort according to the right boundary first. If the right boundary is equal, sort according to the left boundary, both in ascending order.

After sorting, our region can be said to be orderly distributed in one-dimensional space. There is such a simple fact that we start from the first region, which will have several situations.
In the first case, the left boundary behind is larger than it (it is obvious that the right boundary is larger than it, because we sort like this)

Obviously, we need to keep one overlapping area of area 1 (or delete others to ensure no overlap). Who should we keep? 2 and 3 overlap with 1 and which should be deleted. Obviously, it is best to keep 1, because its right boundary is the smallest, it will leave more blank areas on the right, which makes the subsequent overlap smaller. Therefore, keep 1 and delete 2 and 3.
After completing this operation, we will not consider the previous, and directly regard area 4 that does not overlap with area 1 as new area 1. In this way, we can iterate until the last one can find all the.

Of course, there will be a different situation:

Some of the left boundaries in the back area are more left than the left boundary of area 1. At this time, it is also very simple. It is the same treatment. We don't care about the left boundary, because our goal is to select the most left area from 1, 2 and 3 on the left. Then let region 4 be the new region 1 and iterate on like this.

Speaking of this, you should have understood that the greed here is to keep the left area in the overlapping areas from left to right, so as to make the blank space on the right as large as possible, so that the possibility of overlapping on the right will be small. (actually, it's a bit like the cookie distribution problem above, starting from childhood)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals){
        if(intervals.length==0){//Determine whether the array is empty
            return 0;
        }
        //Sort by start point
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {//Sort according to the right boundary. If the boundaries are equal, repeat according to the left boundary. Finally, the left boundary is small,
                if(o1[1]==o2[1]){
                    return o1[0]-o2[0];
                }
                return o1[1]-o2[1];
            }
        });
        int count = 0;
        int temp=0;
        //Greedy thoughts look for the shortest every time, because they have been arranged in order
        //How to say this greedy thought? If it is repeated, it is better to choose the one that ends the earliest in the current situation than others
        for(int i =0;i<intervals.length;i++){
            if(i==0){
                count++;
            }
            //Compare to see if it repeats
            else {
                if(intervals[i][0]>=intervals[temp][1]){//The reason for this comparison is that the order is arranged according to the right boundary, and only the left boundary is considered
                    temp = i;
                    count++;
                }
            }
        }
        return intervals.length-count;
    }
}

452. Detonate the balloon with a minimum number of arrows

There are many spherical balloons in two-dimensional space. For each balloon, the input provided is the start and end coordinates of the balloon diameter in the horizontal direction. Because it is horizontal, the y coordinate is not important, so it is enough to know the x coordinates of the beginning and end. The start coordinate is always less than the end coordinate. There are up to 104 balloons in the plane.

A bow and arrow can be shot completely vertically from different points along the x-axis. Shoot an arrow at the coordinate X. if the start and end coordinates of the diameter of a balloon are xstart, xend and xstart ≤ x ≤ xend, the balloon will be detonated. There is no limit to the number of bows and arrows you can shoot. Once a bow and arrow is shot, it can move forward indefinitely. We want to find the minimum number of bows and arrows needed to detonate all balloons


Topic analysis: this topic can be said to be a variant of 435 questions, and it is also a regional overlap problem. Understand 435, the problem is very simple. For this question, its goal is actually to find which areas repeat the most at the same time.

Topic idea: for this topic, we also sort it first, which is the same as 435. We won't repeat it here.
Then traverse each region from left to right. We adhere to this idea, because the regions have been sorted and mapped to one-dimensional space. Then the region we are currently traversing must shoot an arrow. The more we can find and repeat it, the better. Then we can shoot them together. With such an idea, we can shoot all balloons at least.

Therefore, the greed here is that for each unbroken balloon traversed from left to right, the balloon repeated with it will be shot and exploded every time (when traversing the balloon, shoot and explode more balloons as much as possible, or the shooting position is as close to the right as possible, so as to shoot and explode more).

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        //Sort the array
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {//Sort according to the right boundary. If the boundaries are equal, repeat according to the left boundary. Finally, the left boundary is small,
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });
        int result = 0;//result
        int area = 0;//Currently accessed area
        while(area<points.length){
            //Determine the area that is repeated with the current area
            int i =area+1;
            while(i<points.length){
                if(points[i][0]<=points[area][1]){
                    i++;
                }
                else {//Once there is no possibility of overlap, stop
                    break;
                }
            }
            result++;
            area=i;
        }
        return result;
    }
}

Of course, the ranking here can be based on the left bound (yes for this problem, but the result remains the same).

Tags: Java Algorithm leetcode leetccode

Posted by mechamecha on Wed, 18 May 2022 06:40:12 +0300