greedy
Greedy algorithm or greedy idea adopts greedy strategy to ensure that each operation is locally optimal, so that the final result is globally optimal.
assignment problem
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 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.
Idea:
Children and biscuits are sorted in ascending order according to appetite and size respectively. Biscuits are matched according to appetite. If they are insufficient, they will skip the biscuit
code:
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int j = 0, cnt = 0;
for (int i = 0; i < g.size() && j < s.size(); j++)
g[i] <= s[j] ? i++, cnt++ : true;
return cnt;
}
};
135. Distribution of candy
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?
Idea:
Greedy principle: initialize the number of sweets for all children as 1. First traverse from left to right. If the score on the right is higher than that on the left, update the number of sweets as the number of sweets on the left plus 1. Then traverse from right to left, and the score on the left is higher than that on the right. If the number of sweets on the left is higher than that on the right, there is no need to update. Instead, the number of sweets is the number of sweets on the right plus 1
code:
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> score(ratings.size(), 1);
int cnt = 0;
for (int i = 0; i < ratings.size() - 1; i++)
ratings[i + 1] > ratings[i] ? score[i + 1] = score[i] + 1 : true;
for (int i = ratings.size() - 1; i > 0; i--) {
cnt += score[i];
(ratings[i - 1] > ratings[i]) && (score[i - 1] <= score[i]) ? score[i - 1] = score[i] + 1 : true;
}
return cnt + score[0];
}
};
Interval problem
435. Non overlapping interval
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:
It can be considered that the end of an interval is always greater than its starting point. section [1,2] and [2,3] The boundaries of are "in contact" with each other, but do not overlap each other.
Idea:
Greedy principle: arrange in ascending order at the end and traverse from left to right. If the left interval overlaps with the right interval, discard the right interval and compare the next one
(ascending order at the end is the essence, ensuring that the first one is left in the front, leaving more space for the back and getting more intervals)
code:
class Solution {
public:
static bool comp(vector<int>& a, vector<int>& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), comp);
int cnt = 0;
for (int i = 0, j = 1; i < intervals.size() && j < intervals.size();) {
if (intervals[j][0] < intervals[i][1])
j++, cnt++;
else
i = j++;
}
return cnt;
}
};
practice
605. Flower planting
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.
Idea:
Greedy principle: traverse from left to right. If there are two consecutive zeros, judge whether it is at the beginning or whether the previous one is 0. If yes, make the first one 1. If not, make the second one 1; If there are two consecutive 1s, it proves that the previous update is invalid and the previous update is restored
(another simple logic: record the subscript of each flower, starting from the largest one, judge whether the subscript + 2 exceeds, and set it as 1 if it does not exceed. Then continue to judge with + 2, and then return to the largest one, subscript - 2 to see if it is 0. If it is 0, compare whether the subscript of the second largest flower is the subscript after - 2 or the subscript of - 3, and record it as 1 if it is not)
code:
class Solution {
public:
int count(vector<int>& flowerbed, int first, int l) {
int cnt = 0, k = 1, si;
l > 0 ? si = flowerbed.size() - 1 : si = 0;
for (int i = first; l > 0 ? i < flowerbed.size() - 1 : i > 0; ) {
if (i + k * l == si)
break;
if (!flowerbed[i + (k + 1) * l]) {
if (i + (k + 1) * l == si) {
cnt++;
break;
}
else if (flowerbed[i + (k + 2) * l])
i += (k + 2) * l;
else
cnt++, i += (k + 1) * l;
}
else
i += (k + 1) * l;
}
return cnt;
}
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int first = -1, cnt = 0;
for (int i = 0; i < flowerbed.size(); i++){
if (flowerbed[i] == 1) {
first = i;
break;
}
}
if (first < 0) {
for (int i = 0; i < flowerbed.size(); i += 2)
cnt++;
}
else {
cnt += count(flowerbed, first, 1);
cnt += count(flowerbed, first, -1);
}
return cnt >= n;
}
};
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 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 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. After being arched, you 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.
Idea:
According to the greedy principle, sort according to the end diameter, and then push back according to the solution similar to 435: non overlapping interval, because all balloons have to be hit, so all intervals overlapping with the current interval are eliminated from left to right, You can ensure that the last thing left is the number of balloons with the least bullets (Note: in this problem, if the end of the previous interval is the same as the beginning of the next interval, it is also considered to overlap)
(why can this problem be solved with non overlapping intervals? Removing the duplicate means that you can kill all balloons with one shot for each remaining interval)
code:
class Solution {
public:
static bool comp(vector<int>& a, vector<int>& b) {
return a[1] < b[1];
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), comp);
int cnt = 0;
for (int i = 0, j = 1; i < points.size() && j < points.size();) {
if (points[j][0] <= points[i][1])
j++, cnt++;
else
i = j++;
}
return points.size() - cnt;
}
};
763. Division of letter interval
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.
Idea:
First traverse, record the occurrence interval of each letter, and sort it according to the first occurrence order. According to the principle of greed, if the same letter appears in one interval at most, then this interval will be greater than the interval of all letters, so traverse from left to right, starting from the interval of the first letter, If the start subscript of the next letter interval is less than the end subscript of the current interval and the end subscript is greater than the end subscript of the current interval, it will be updated to the new end subscript of the current interval. Until the next letter interval does not overlap with the current interval, we will get a minimum interval, such as: [1,5], [2,3], [4,6], [7,8], and divide the interval into [1,6], [7,8]
(if the character can only be in one segment, record the intervals of all characters. According to the ascending order of the end interval, find that the beginning of an interval is greater than the end of the previous interval, which proves that the characters contained in the string before the previous interval will no longer appear in the subsequent interval. This is a field)
code:
class Solution {
public:
static bool comp(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
vector<int> partitionLabels(string s) {
int cnt = 0;
vector<vector<int>> n;
vector<int> re, hash(26, -1);
int first = 0, last = 0;
for (int i = 0; i < s.size(); i++) {
if (hash[s[i] - 'a'] == -1) {
hash[s[i] - 'a'] = cnt++;
n.push_back({ i,i });
}
else
n[hash[s[i] - 'a']][1] = i;
}
sort(n.begin(), n.end(), comp);
first = n[0][0], last = n[0][1];
for (int i = 0, j = 1; i < n.size() && j < n.size();j++) {
if (n[j][0] > last)
re.push_back(last - first + 1), i = j, first = n[i][0], last = n[i][1];
else if (n[j][1] > last)
last = n[j][1];
}
re.push_back(last - first + 1);
return re;
}
};
122. The best time to buy and sell stocks II
Give an array prices, where prices[i] 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).
Idea:
Greedy principle: buy at a low price and sell at a high price. Traverse from left to right. When the price decreases continuously, record the lowest price at all times. Once the decline stops, buy at the lowest price. When the price continues to rise, record the highest price at all times. Once it begins to fall, sell at the highest price
(it requires more profits and does not limit the number of transactions, so it is to buy low and sell high as much as possible. If the stock price increases, buy the day before, sell at Gu Feng, and buy at the bottom of the valley if it decreases)
code:
class Solution {
public:
int ftop(vector<int>& prices,int n, int pos) {
for (int i = n; i < prices.size()-1; i++) {
if (pos == 1 ? prices[i] > prices[i + 1] : prices[i] < prices[i + 1])
return i;
}
return prices.size()-1;
}
int maxProfit(vector<int>& prices) {
int sum = 0;
for (int i = 0; i < prices.size() - 1; i++) {
if (prices[i] < prices[i + 1])
sum += (-prices[i] + prices[i = ftop(prices, i + 1, 1)]);
else
i = ftop(prices, i + 1, -1) - 1;
}
return sum;
}
};
406. Reconstruction of the cohort according to height
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).
Idea:
It is processed in descending order according to height first, and then in ascending order according to the coefficient of the second term. Out of the principle of greed, priority is given to those who are tall, and there are fewer people who are taller than him, so it is more convenient to insert into the queue. The ascending order of the second term is also the same. In this way, there must be i people who are taller than him in front of the i person. If i is less than the coefficient of the second term, it will be inserted into the tail of the new queue, Otherwise, it will be inserted into the i in the new queue. In this way, the height of the later inserted person is less than or equal to him, and the coefficient of the second term is greater than or equal to him, which will not affect him. In this way, it is very convenient to sort
(dual attributes are generally ranked according to two attributes. In this case, it must be in descending order of height first, because the second attribute is higher than yourself, so it must be better to deal with those with higher height first, and then the second attribute is in ascending order naturally, because the fewer those higher than yourself, the better. After such a row, it is found that the people who deal with each time are less than or equal to those who have been dealt with If there are several people taller than him, just insert them in the first one. For convenience, use other data structures and then convert them to array output)
code:
class Solution {
public:
static bool comp(vector<int>& a, vector<int>& b) {
return a[0] == b[0] ? a[1] < b[1]:a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
vector<vector<int>> re;
sort(people.begin(), people.end(), comp);
for (int i = 0; i < people.size();i++) {
if (people[i][1] < re.size())
re.insert(re.begin() + people[i][1],people[i]);
else
re.push_back(people[i]);
}
return re;
}
};
665. Non decreasing column
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].
Idea:
According to the meaning of the question, the non decreasing sequence is defined as num [i] < = num [i + 1], so when the sequence drops at I (Num [i] > num [i + 1]), if num [i] > num [i + 1], Num [I] = num [I - 1], otherwise modify num [i + 1] = num [i], so that according to the principle of greed, the non decreasing sequence can be maintained before the falling position. When the modification is greater than once, FALSE is returned
(ps: special case: directly modify num [i] = num [i + 1] when i=0)
(this kind of problem is ergodic. If the first one is inconsistent, judge whether it is not decreasing with the previous one. If not, reduce the previous one to the same level as yourself. If not, rise to the previous level. This is the most greedy change, because if it is decreasing, it is useless for you to change the previous one. If it is not decreasing, only changing the previous one will have the least impact on the later.)
code:
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int cnt = 0;
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (!i || nums[i + 1] > nums[i - 1])
nums[i] = nums[i+1];
else if (nums[i + 1] < nums[i - 1])
nums[i + 1] = nums[i];
if (++cnt > 1)
return false;
}
}
return true;
}
};