LeetCode question bank: greedy algorithm

LeetCode notes: greedy algorithm

Since the University, I have been learning some algorithms and data structures one after another. At the same time, I also began to brush questions on some platforms and participate in some algorithm competitions, large and small. However, the lack of purposefulness and systematicness of problem brushing at ordinary times eventually leads to slow progress in the algorithm. Finally, for my future, I decided to start systematic learning and Practice on LeetCode. At the same time, I sorted and recorded the track of brushing questions and shared it with you.

Reference material: LeetCode 101 - A LeetCode Grinding Guide

Reference materials: ideas / answers provided by LeetCode community officials and ideas / answers provided by various gods in the comment area / solution area

Algorithm interpretation:

As the name suggests, greedy algorithm or greedy idea adopts greedy strategy to ensure that each operation is locally optimal, so that the final result is globally optimal.

Take the simplest example: Xiao Ming and Xiao Wang like apples. Xiao Ming can eat five and Xiao Wang can eat three. It is known that there are endless apples in the apple orchard. Please ask Xiao Ming and Xiao Wang how many apples to eat together. In this example, the greedy strategy we can choose is that everyone eats the maximum number of apples they can eat, which is locally optimal for everyone. Because the global result is a simple summation of local results, and the local results are irrelevant to each other, the locally optimal strategy is also the globally optimal strategy.

455. Distribution of biscuits

Difficulty: simple

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 g[i], which is the minimum size of biscuits that can satisfy the children's appetite; And every cookie j has a size s[j]. If s[j] > = g[i], we can assign this 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.

Example:

input: g = [1,2,3], s = [1,1]
output: 1

explain: 
You have three children and two biscuits. The appetite values of the three children are: 1,2,3. 
Although you have two small biscuits, because their size is 1, you can only satisfy children with an appetite of 1.
So you should output 1.

Solution:

Because the child with the least hunger is most likely to be full, let's consider this child first. In order to make the remaining biscuits meet the children with greater hunger as much as possible, we should give the child the smallest biscuits that are greater than or equal to the child's hunger. After satisfying this child, we adopt the same strategy and consider the child with the least hunger among the remaining children until there are no cookies that meet the conditions.

Algorithm implementation: Java

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int child=0,cookie=0;
        while (child<g.length && cookie<s.length){
            if (g[child]<=s[cookie])
                child++;
            cookie++;
        }

        return child;
    }
}

135. Distribution of candy

Difficulty: difficulty

The teacher wants to distribute candy to the children. There are N children standing in a straight line. The teacher will score each child in advance according to their performance.

You need to help the teacher distribute candy to these children according to the following requirements:

  • Each child is assigned at least one candy.
  • Children with higher scores must get more candy than their neighbors on both sides.

So how many candies does the teacher need to prepare at least?

Example:

Input:[1,0,2]
Output: 5
 Explanation: you can distribute 2, 1 and 2 candies to the three children respectively.

Solution:

You only need two simple traversals:

Initialize the number of sweets for all children to 1; First traverse from left to right. If the score of the child on the right is higher than that on the left, the number of sweets of the child on the right will be updated to the number of sweets of the child on the left plus 1; Go through it again from right to left. If the score of the left child is higher than that of the right child, and the current candy number of the left child is not greater than that of the right child, the candy number of the left child will be updated to the candy number of the right child plus 1. Through these two iterations, the allocated candy can meet the requirements of the topic.

The greedy strategy here is to only consider and update the size relationship of the adjacent side in each traversal.

Algorithm implementation: Java

class Solution {
    public int candy(int[] ratings) {
        int[] tang=new int[ratings.length];
        for (int i = 0; i < tang.length; i++) {
            tang[i]=1;
        }
        //From left to right
        for (int i = 1; i < tang.length; i++) {
            if (ratings[i]>ratings[i-1]){
                tang[i]=tang[i-1]+1;
            }
        }
        //From right to left
        for (int i=tang.length-2;i>=0;i--){
            if (ratings[i]>ratings[i+1]){
                tang[i]=Math.max(tang[i],tang[i+1]+1);
            }
        }
        //Sum
        int sum=0;
        for (int i = 0; i < tang.length; i++) {
            sum+=tang[i];
        }
        return sum;
    }

}

435. Non overlapping interval

Difficulty: medium

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

be careful:

  1. It can be considered that the end of an interval is always greater than its starting point.
  2. The boundaries of intervals [1,2] and [2,3] are "in contact" with each other, but do not overlap each other.

Example:

input: [ [1,2], [2,3], [3,4], [1,3] ]
output: 1
 explain: remove [1,3] After, the remaining intervals do not overlap.

Solution:

When selecting the interval to be reserved, the end of the interval is very important: the smaller the end of the selected interval, the more space left for other intervals, and the more intervals can be reserved. Therefore, our greedy strategy is to give priority to the regions with small endings and disjoint intervals.

The specific implementation method is to sort the intervals in ascending order according to the size of the end, and select the interval with the smallest end and no overlap with the previous selected interval each time.

In the example, the sorted array is [[1,2], [1,3], [2,4]]. According to our greedy strategy, first initialize to interval [1,2]; Since [1,3] intersects with [1,2], we skip this interval; Since [2,4] does not intersect with [1,2], we keep it. Therefore, the final reserved interval is [[1,2], [2,4]].

Algorithm implementation: Java

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {

        if ((intervals == null || intervals.length == 0) 
            || (intervals.length == 1 && intervals[0].length == 0)) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

//        System.out.println(Arrays.deepToString(intervals));
        int n = intervals.length;
        int total = 0;
        int prev = intervals[0][1];

        for (int i = 1; i < n; i++) {
            if (intervals[i][0] <prev) {
                total++;
            }else {
                prev = intervals[i][1];
            }
        }

        return n - total;
    }
}

Algorithm implementation: Java

class Solution2 {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });

        int n = intervals.length;
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
}

605. Flower planting

Difficulty: simple

Suppose there is a long flower bed. Some plots are planted with flowers, while others are not. However, flowers cannot be planted on adjacent plots. They will compete for water and both will die.

Give you an integer array, flowerbed represents the flower bed, which is composed of several 0 and 1, where 0 means no flowers are planted and 1 means flowers are planted. There is another number, N. can you plant n flowers without breaking the planting rules? If yes, it returns true; if not, it returns false.

Example:

Input: flowerbed = [1,0,0,0,1], n = 1
 Output: true

Solution:

Judge whether nn flowers can be planted in the flower bed without breaking the planting rules. From the perspective of greed, plant as many flowers as possible without breaking the planting rules, and then judge whether the maximum number of flowers that can be planted is greater than or equal to nn.

Defensive programming idea: add a 0 at both ends of the flowerbed array. The advantage of this treatment is that you don't need to consider the boundary conditions. As long as there are three 0's in succession at any position, you can plant a flower.

Algorithm implementation: Java

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        //Defensive programming thinking
        int temp[]=new int[flowerbed.length+2];
        temp[0]=0;
        temp[temp.length-1]=0;
        for (int i = 1; i < temp.length-1; i++) {
            temp[i]=flowerbed[i-1];
        }

//        System.out.println(Arrays.toString(temp));
//        System.out.println(Arrays.toString(flowerbed));

        int ans=0;
        //Start planting flowers
        for (int i = 1; i < temp.length-1; i++) {
            if (temp[i] == 0 && temp[i - 1] == 0 && temp[i + 1] == 0) {
                temp[i] = 1;
                ans++;
            }
        }

        return ans>=n;
    }
}

452. Detonate the balloon with a minimum number of arrows

Difficulty: medium

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 ordinate is not important, so it is enough to know the abscissa of the beginning and end. The start coordinate is always less than the end coordinate.

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 x``start, x``end and xstart ≤ x ≤ x``end, 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.

Give you an array of points, where points [i] = [xstart,xend] returns the minimum number of bows and arrows that must be fired to detonate all balloons.

Example:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: for this example, x = 6 can explode [2,8], [1,6] two balloons, and x = 11 can explode the other two balloons

Solution idea 1:

Like other problem routines of merging intervals, they are greedy. They sort first, and then traverse to check whether the conditions of merging intervals are met. Here, it is judged whether there is a cross interval, so it is actually to calculate the intersection number of known intervals. Take [[10,16], [2,8], [1,6], [7,12]] as examples:

First, I sort by the starting position of the interval, and then: [[1,6], [2,8], [7,12], [10,16]]
Traverse the calculation cross section (arrow to be launched),
Range of arrows to be launched = [1, 6], number of arrows required = 1;
Interval [2,8] and interval with transmission [1,6] have intersection: update the transmission area to their intersection range = [2,6]
There is no intersection between the interval [7,12] and the interval to be launched [2,6], indicating that a new launch area needs to be added, and the new range = [7,12]
The interval [10,16] intersects with the area to be launched [7,12], and the area to be launched is updated to [10,12]
Returns the number of sections to be launched

Algorithm implementation: Java

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length <= 1) {
            return points.length;
        }

        Arrays.sort(points, (p1, p2) -> p1[0] != p2[0] ? Integer.compare(p1[0], p2[0]) : Integer.compare(p1[1], p2[1]));

//        System.out.println(Arrays.deepToString(points));


        //Initialize the section to be launched
        int holdStart = points[0][0]; // Starting point of intersection currently maintained
        int holdEnd = points[0][1]; // Intersection endpoint currently maintained
        int counts = 0; // Number of intersections currently collected

        for (int i = 1; i < points.length; i++) {

            int[] point=points[i];//Current point
            int curStart=point[0];
            int curEnd=point[1];

            if (curStart>holdEnd){
                //There is currently no intersection
                counts++;//Increase launch area
                //New waiting area
                holdStart=curStart;
                holdEnd=curEnd;
            }else {
                //There are currently intersections. Update the launch area to their intersection
                holdStart=Math.max(holdStart,curStart);
                holdEnd=Math.min(holdEnd,curEnd);
            }
        }

        counts++;
        return counts;
    }
}

Problem solving idea 2:

Sorting by the tail of the interval seems to be more efficient, because it has been guaranteed that the right side of the subsequent interval is larger than the current interval, so set the launch point at the right boundary. Only the left boundary of the subsequent interval is more left than it, and it can be disposed of together
Here is another example: [[10,16],[2,5],[1,6],[7,12]] as an example:

Sort first, sort by the end of the interval, and then: [[2,5], [1,6], [7,12], [10,16]]
Traverse the calculation cross section,
The launch point is initialized to pos = 5, and the number of arrows required is arrows = 1;
Interval [1, 6], 1 is less than 5. Shooting an arrow at point 5 can kill this interval
In the interval [7, 12], the arrow cannot be shot at the position of 5, indicating that a new launch point needs to be added, and the new launch point pos = 12
Interval [10,16], 10 < 12, then archery at position 12 can kill it
Return the number of shooting points required

Algorithm implementation: Java

class Solution3 {
    public int findMinArrowShots(int[][] points) {
        if(points.length < 2){
            return points.length;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                if (point1[1] > point2[1]) {
                    return 1;
                } else if (point1[1] < point2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

//        System.out.println(Arrays.deepToString(points));

        int total = 1;
        int pre = points[0][1];
        for(int i = 1;i<points.length;i++){
            if(points[i][0] <= pre){

            }else{
                pre = points[i][1];
                total++;
            }
        }
        return total;
    }
}

763. Division of letter interval

Difficulty: medium

The string S consists of lowercase letters. We should divide the string into as many segments as possible, and the same letter can appear in one segment at most. Returns a list representing the length of each string fragment.

Example:

Input: S = "ababcbacadefegdehijhklij"
Output:[9,7,8]
Explanation:
The division result is "ababcbaca", "defegde", "hijhklij". 
Each letter can appear in at most one segment.
image "ababcbacadefegde", "hijhklij" The partition of is wrong because the number of segments is small.

Solution:

In fact, the idea is very simple,
1. First look at the first letter, find its last position in the string and record it as last or the last position of a paragraph.
2. In the range from 0 to last, check other letters one by one to see if their last position is larger than the last or the last position of a paragraph.
If it is not as big as the last or the last position of a paragraph, ignore it and continue to look back.
If it is larger than the previous one, it means that the separation position of this paragraph must be moved back, so we update the last position of last or a paragraph to the last position of the current letter.
3. There must be a time when this last cannot be updated, so this position is our separation position at this time.
Note the length of the topic to be separated, so we use last - startindex + 1.
4. Find a split bit, update the starting position, and search in the same way.

Algorithm implementation: Java

class Solution {
    public List<Integer> partitionLabels(String s) {

        int[] map = new int[26];//Record the farthest position corresponding to each letter.
        Arrays.fill(map, -1);
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a'] = i;
        }

        int start = 0;//The starting position of cutting. 
        int scannedCharMaxPos = 0;//The farthest place a scanned character can go.
        
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
            int currentCharMaxPos = map[s.charAt(i) - 'a'];
            scannedCharMaxPos = Math.max(scannedCharMaxPos, currentCharMaxPos);
            if (i == scannedCharMaxPos) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }

}

122. The best time to buy and sell stocks II

Simple difficulty 1093 collection sharing switch to English to receive dynamic feedback

Given an array, its i-th element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can complete as many transactions as possible (buying and selling a stock multiple times).

**Note: * * you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

Example:

input: [7,1,5,3,6,4]
output: 7
 explain: On day 2 (stock price) = 1)Buy on day 3 (stock price) = 5)Sell at, The exchange is profitable = 5-1 = 4 . 
     Then, on day 4 (stock price) = 3)Buy on day 5 (stock price) = 6)Sell at, The exchange is profitable = 6-3 = 3 . 

Solution:

Stock trading strategy:

Separate trading day: set the price p1 today and the price p2 tomorrow, then the amount p2 - p1 that can be earned by buying today and selling tomorrow (negative value represents loss).

Continuous rising trading day: if the stock prices on this rising trading day are p1, p2,..., pn respectively, then the first day of buying and the last day of selling yield is the largest, that is, pn - p1; Equivalent to buying and selling every day, that is, pn - p1=(p2 - p1)+(p3 - p2) +... + (pn - p{n-1})

Continuous decline trading days: the maximum profit will not be obtained from trading, that is, there will be no loss of money.

Algorithm flow:

Traverse the price list of the whole stock trading day. The strategy is to buy and sell on all rising trading days (earn all profits) and not on all falling trading days (never lose money).
Let tmp be the profit earned from buying and selling on day i-1, that is, tmp = prices[i] - prices[i - 1];
When the profit of that day is positive TMP > 0, the profit will be added to the total profit profit profit; If 00 is directly skipped, it is negative or;
After traversal, return the total profit profit profit.

Algorithm implementation: Java

class Solution {
    public int maxProfit(int[] prices) {
        int profit=0;
        for (int i = 1; i < prices.length; i++) {
            int tmp=prices[i]-prices[i-1];
            if (tmp>0){
                profit+=tmp;
            }
        }
        return profit;

    }
}

406. The cohort was reconstructed according to height

Difficulty: medium

Suppose a group of people who are out of order stand in a queue, and the array people represents the attributes of some people in the queue (not necessarily in order). Each person [i] = [Hi, Ki] means that the height of the ith person is hi, and there is just ki person whose height is greater than or equal to hi in front.

Please reconstruct and return the queue represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attribute of the jth person in the queue (queue[0] is the person in front of the queue).

Example:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
The person numbered 0 is 5 in height, and no one taller or the same is ahead of him.
The person numbered 1 is 7 in height, and no one taller or the same is ahead of him.
The person with number 2 is 5 in height, and there are two people who are taller or the same in front of him, that is, the people with numbers 0 and 1.
The person with number 3 is 6 in height, and one person with higher height or the same height is in front of him, that is, the person with number 1.
The person with number 4 is 4 in height, and there are four people who are taller or the same in front of him, that is, the people with numbers 0, 1, 2 and 3.
The person numbered 5 is 7 in height, and there is a person taller or the same in front of him, that is, the person numbered 1.
therefore [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] Is the reconstructed queue.

Routine: generally, this number pair also involves sorting. Sorting according to the first element in the forward direction, sorting according to the second element in the reverse direction, or sorting according to the first element in the reverse direction and sorting according to the second element in the forward direction can often simplify the problem-solving process.

Problem solving ideas:

Sort before insert

  • 1. Sorting rule: sort according to the descending order of the first H height and the ascending order of the number of K
  • 2. Traverse the sorted array and insert it into the position of K according to K
  • Core idea: the tall man stands in position first, and the short man inserts into position K. there must be K tall men in front, and the short man inserts into the front also meets the requirements of K
Example problem solving process simulation
    
    After sorting
    [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
    Insert one by one.
    [7,0]	//Insert 7 at position 0
    [7,0], [7,1]		//Insert 7 in position 1
    [7,0], [6,1], [7,1]		//Insert 6 in position 1
    [5,0], [7,0], [6,1], [7,1]		//Insert 5 at position 0
    [5,0], [7,0], [5,2], [6,1], [7,1]		//Insert 5 in position 2
    [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]			//Insert 4 at position 4

Algorithm implementation: Java

class Solution {
    public int[][] reconstructQueue(int[][] people) {

        Arrays.sort(people,(o1, o2) -> o1[0]==o2[0]?o1[1]-o2[1]:o2[0]-o1[0]);
//        System.out.println(Arrays.deepToString(people));

        LinkedList<int[]> linkedList=new LinkedList<>();
        for (int i = 0; i < people.length; i++) {
            linkedList.add(people[i][1],people[i]);
        }

        int[][] arrayList=linkedList.toArray(new int[linkedList.size()][2]);
//        System.out.println(Arrays.deepToString(arrayList));

        return arrayList;
    }
}

665. Non decreasing column

Difficulty simple 531 collection sharing switch to English to receive dynamic feedback

Give you an integer array with a length of n. please judge whether the array can become a non subtractive column when changing up to 1 element.

We define a non decreasing column as follows: for any I in the array (0 < = I < = n-2), it always satisfies num [i] < = num [i + 1].

Example:

input: nums = [4,2,3]
output: true
 explain: You can make the first 4 a non decreasing column by making it a 1.

Solution:

reference resources: https://leetcode-cn.com/problems/non-decreasing-array/solution/3-zhang-dong-tu-bang-zhu-ni-li-jie-zhe-d-06gi/

First, let's look at the following test cases. Because of the number 2, the array is non monotonically increasing.

Example ①: 4, 2, 5
Example ②: 1, 4, 2, 5
Example ③: 3, 4, 2, 5

When 2 appears in the array, the monotonic increment of the array is destroyed. In order to make the array orderly, we need to adjust 2 or 4:

For the first use case, we can reduce 4 to < = 2 or increase 2 to 4 and 5 to make the array orderly.

In the second use case, we can reduce 4 to 1 or 2 or increase 2 to 4 or 5 to make the array orderly.

In the ③ use case, we must increase 2 to 4 and 5 to make the array orderly: we can't adjust 4 to a number < = 2, because the element in front of 4 is 3

Inductive summary

When nums[i] destroys the monotonic increase of the array, that is, when nums[i] < nums[i -1], in order to make the array orderly, we find a law (in the above three examples, nums[i] is 2 and nums[i -1] is 4):

For example ①, if i = 1, modify num[i- 1] and don't move num [i], because we don't know what the element behind num [i] is. It's better to move it less.
For example ②, when I > 1, we should give priority to reducing num [I - 1] to > = num [I - 2] and < = num [i]. Similarly, try not to modify nums[i], for the same reason.
For example ③, when I > 1 and num [i] < num [I - 2], we cannot adjust num [I - 1], we can only adjust num [i] to num [I - 1].

Algorithm implementation: Java

class Solution {
    public boolean checkPossibility(int[] nums) {
        int count=0;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i]<nums[i-1]){
                if (i==1 || nums[i]>=nums[i-2]){
                    nums[i-1]=nums[i];
                }else{
                    nums[i]=nums[i-1];
                }
                if (++count>1){
                    return false;
                }
            }
        }


        return true;


    }
}
Author: Geng GUI can't laugh
Time: February 2021

Tags: Java Algorithm queue greedy algorithm subversion

Posted by i on Mon, 18 Apr 2022 21:03:31 +0300