​

Algorithm explanation:

The strategy of the greedy algorithm is to ensure that every operation is locally optimal, so that the final result is globally optimal.

For example: A and B like to eat apples, A can eat 5, B can eat 3, there is no limit to the number of apples, so the two people can eat A maximum of how many apples, this is obvious, 5+3, this is the local optimization leads to the overall optimization, this is greedy strategy.

Distribution problem:

455. Biscuits were distributed

Difficulty is simple

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child.

For each child I, there is an appetite value g[I], which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie J has a size S [J]. If s[j] >= g[I], we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have three children and two cookies. Even though you have two little cookies, since they're both size 1, you can only satisfy a child with an appetite of 1. So you should print 1.Copy the code

Example 2:

Input: g = [1,2], s = [1,2,3] output: 2 explanation: you have two children and three cookies, each with an appetite value of 1,2. The number and size of cookies you have is enough to satisfy all children. So you should print 2.Copy the code

AC code:

class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(),g.end()); sort(s.begin(),s.end()); int g1 =0 ,s1 =0; while(g1<g.size()&&s1<s.size()){ if(g[g1]<=s[s1]) g1++; s1++; } return g1; }};Copy the code

Ideas:

First of all, we know the number of children and the food they need, the size of each food, and only one food per child. So in order to feed more children, we certainly can’t start feeding the children who eat the most, so we have to start feeding the children who eat the least. We start with the child who eats the least, so we can’t start with the child who eats the least, so we have to compare the smallest piece of food with the child who is the least hungry, so that the child who eats the most is full.

135. Give out candy

Difficult difficult

The teacher wants to give out candy to the children. Yes

N

Each child stood in a straight line, and the teacher graded each child in advance according to their performance.

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

  • Each child gets at least one candy.
  • The child who scored higher had to get more candy than the child on either side of him.

So how many candies should the teacher prepare?

Example 1:

Input: [1,0,2] Output: 5 Explanation: You can give two, one, two sweets to each of the three children.Copy the code

Example 2:

Input: [1,2,2] Output: 4 Explanation: You can give 1,2, 1 candy to each of the three children. The third child received only one candy, which satisfied both conditions.Copy the code

AC code:

class Solution { public: int candy(vector<int>& ratings) { int size=ratings.size(); if(size<2){ return size; } vector<int> num(size,1); for(int i=1; i<size; i++){ if(ratings[i]>ratings[i-1]){ num[i]=num[i-1]+1; } } for(int i=size-1; i>0; i--){ if(ratings[i]<ratings[i-1]){ num[i-1]=max(num[i]+1,num[i-1]); } } return accumulate(num.begin(), num.end(), 0); // STD ::accumulate is a convenient summation}};Copy the code

Ideas:

Num [I]=num[i-1]+1; num[I]=num[i-1]+1; If the two numbers are the same size, then the result is +1.

PDD two face algorithm problem

Given an array where the difference between each value in the array and its neighbor is m, you are now given a target value k, find the index of all elements in the array equal to k, and return it using a collection. Unordered List fun(List List,int m,int k) as in [1,2,3,2,1,0,-1,0,1] m=1 k=3 returns [2], k must be some value in the array

I wrote the reference code:

class Solution { public: int getK(vector<int>& list,int m,int k) { int index=0; int len=list.size(); while(index<len){ int cur=list[index]; int step=Math.abs(cur-k)/m; if(step==0){ return ++index; } else{ index+=step; }; }}Copy the code

First of all, this is the algorithm of Dachang, I feel that the investigation is almost greedy, not quite understand what it is, anyway, the idea is very clear.

The difference between the neighboring elements in this unordered array is m, so we start with the first element and keep looking as long as the current element minus the target element is not equal to 0. This code uses m to do the jump, index+=step; This greatly reduces the number of times, in line with the requirements of the interviewer.

435. No overlap interval

The difficulty of medium

Given a set of intervals, find the minimum number of intervals to remove so that the remaining intervals do not overlap.

Note:

  1. You can assume that the end of an interval is always greater than its beginning.
  2. The boundaries of the intervals [1,2] and [2,3] “touch” each other, but do not overlap each other.

Example 1:

Input: [[1, 2], [2, 3], [3, 4], [1, 3]] output: 1: after removing [1, 3], the rest of the band didn't overlap.Copy the code

Example 2:

Input: [[1,2], [1,2]] output: 2 explanation: you need to remove both [1,2] to make the remaining intervals not overlap.Copy the code

Example 3:

Input: [[1,2], [2,3]] output: 0 explanation: you do not need to remove any intervals because they are already non-overlapping.Copy the code

AC code:

class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { if (intervals.empty()) { return 0; } sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) { return u[1] < v[1]; }); int count=0,cur=intervals[0][1],size=intervals.size(); for(int i=1; i<size; ++i){ if(intervals[i][0]<cur){ ++count; } else{ cur=intervals[i][1]; } } return count; }};Copy the code

Ideas:

This problem a lot of big guys are using dynamic programming, but greedy is also ok. Given that the problem requires a minimum number of arrays to be removed, this is where we find the greedy strategy: sort the second element of each array, and then compare the first element of the adjacent array.

605. The problem of growing flowers

Difficulty is simple

Suppose you have a very long flower bed, and one part of the plot is planted with flowers, but the other part is not. However, flowers cannot grow in adjacent plots. They compete for water and both die.

Flowerbed gives you an array of integers representing a flowerbed, consisting of zeros and ones, where 0 indicates no flowers and 1 indicates flowers. Another number, n, can I plant n flowers without breaking the planting rules? Returns true if yes, false if no.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: trueCopy the code

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2 output: falseCopy the code

AC code:

class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { for(int i=0; i<flowerbed.size(); i++) { if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.size()-1 || flowerbed[i+1] == 0)) { n--; if(n <= 0) return true; flowerbed[i] = 1; } } return n <= 0; }};Copy the code

Ideas:

The greedy strategy of this problem is very simple, it is to plant flowers if you can, and the conditions of planting flowers are as follows: it is zero and the right side is zero and the left side is zero and the right side is zero, so as to ensure the maximum number of flowers.

Detonate the balloon with the minimum number of arrows

Difficulty Medium 456

There are many spherical balloons in two dimensions. For each balloon, the input provided is the start and end coordinates of the balloon diameter in the horizontal direction. Since it’s horizontal, the y-coordinate doesn’t matter, so it’s enough to know where the x-coordinate starts and ends. 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 coordinate X. If there is a balloon whose diameter starts and ends at coordinates X “” start, x” “end, and xstart ≤ x ≤ x” “end, the balloon will be exploded. There is no limit to the number of bows and arrows that can be fired. Once a bow is fired, it can go indefinitely. We want to find the minimum number of arrows needed to detonate all the balloons.

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

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]Copy the code

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]Copy the code

Example 3:

Points = [[1,2],[2,3],[3,4],[4,5]] output: 2Copy the code

Example 4:

Input: points = [[1,2]] Output: 1Copy the code

Example 5:

Input: points = [[2,3],[2,3]] output: 1Copy the code

AC code:

class Solution { public: int findMinArrowShots(vector<vector<int>>& intervals) { if (intervals.empty()) { return 0; } sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) { return u[0] < v[0]; }); int count=1,size=intervals.size(); for(int i=1; i<size; ++i){ if(intervals[i][0]<=intervals[i-1][1]){ intervals[i][1]=min(intervals[i-1][1],intervals[i][1]); } else{ ++count; } } return count; }};Copy the code

Ideas:

The strategy of this problem is to sort the starting position of each balloon, and then judge whether the starting and ending position of adjacent balloons is appropriate. Once two balloons can be exploded together, the ending position of the two balloons should take the minimum value, and then judge whether the next balloon can also be exploded together.

763. Divide letter intervals

The difficulty of medium

The string S consists of lowercase letters. We want to divide the string into as many fragments as possible, with the same letter appearing in at most one fragment. Returns a list representing the length of each string fragment.

Example:

Input: S = "ababcbacadefegdehijhklij" output: [9,7,8] explanation: partition result is "ababcbaca", "defegde", "hijhklij". Each letter appears in at most one fragment. The division of "ababcbacadefegde", "hijhklij" is wrong because the number of segments divided is small.Copy the code

AC code:

class Solution { public: vector<int> partitionLabels(string s) { int map[26]={0},cur=0,pre=0; vector<int> arr; for(int i=0; i<s.size(); i++){ map[s[i]-'a']=i; } for(int i=0; i<s.size(); i++){ cur=max(cur,map[s[i]-'a']); if(i==cur){ arr.push_back(cur-pre+1); pre=cur+1; } } return arr; }};Copy the code

Ideas:

Facing this problem, we for each letter of the final location is the most sensitive, because if you don’t know this place, you how to find the smallest array, so let it be seek out each letter of the last occurrence position, starting from the first letter again, to form a closed array, using the pre and cur calculate the length.

122. The best time to Buy and sell stocks II

The difficulty is medium 1355

Given an array prices, 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 make as many trades (buying and selling a stock multiple times) as possible.

** Note: ** You cannot participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

Example 2:

Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

AC code:

class Solution { public: int maxProfit(vector<int>& prices) { int count=0; for(int i=0; i<prices.size()-1; i++){ if(prices[i]<prices[i+1]){ count+=prices[i+1]-prices[i]; } } return count; }};Copy the code

Ideas:

It is not easy to get a result from such details, but from a greedy point of view, in order to maximize profits, I can even buy or sell once every day and not operate when the price drops, so as to maximize profits.

406. Reconstruct the queue according to height

The difficulty of medium

Suppose you have an out-of-order group of people standing in a queue, and the array people represents the attributes of some people in the queue (not necessarily in order). Each people[I] = [hi, ki] means that the ith person is hi, and there are exactly ki people in front of them who are hi or higher.

You 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 property of the JTH person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [(7, 0], [4], [7, 1], [5, 0], [6, 1], [5, 2]] output: [[5, 0), (7, 0], [5, 2], [6, 1], [4], [7, 1]] : The person numbered 0 is 5 tall, and no one is taller or the same height. The person numbered 1 is 7, and no one is taller or the same height. Number 2 is 5 tall, and there are two taller or equal people in front of him, number 0 and number 1. Person number 3 is 6 tall, and there is a taller or equal person in front of him, person number 1. The person numbered 4 is 4 in height, and there are 4 taller or equal people in front of him, namely, 0, 1, 2 and 3. Person number 5 is 7 tall, and there is a taller or equal person in front of him, person number 1. Therefore [(5, 0), (7, 0], [5, 2], [6, 1], [4], [7, 1]] is the queue after restructuring.Copy the code

Example 2:

Input: people = [[6, 0], [5, 0], [4, 0], [3, 2], [2], [1, 4]] output: [[4, 0], [5, 0], [2], [3, 2], [1, 4], [6, 0]]Copy the code

AC code:

class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { vector<vector<int>> arr; sort(people.begin(), people.end(), [](const auto& u, const auto& v) { if (u[0] == v[0]) return u[1] < v[1]; return u[0] > v[0]; }); for(int i=0; i<people.size(); i++){ if(arr.size()<=people[i][1]) arr.push_back(people[i]); else{ arr.insert(arr.begin() +people[i][1], people[i]); } } return arr; }};Copy the code

Ideas:

If the height is the same, the second parameter is sorted in ascending order. In this case, we can make a clear decision about the number of people in front who are taller than this person. First, we put the people in front of us, and use the second parameter as their index, and then let the people behind us plug forward according to the second parameter. Why can we do this? Because when the person behind you enters the two-dimensional array, you will find that everyone who has already taken a seat is taller than you, so your second parameter can be used as an index to let you jump the queue.

665. Non-decreasing sequence

The difficulty is medium 608

Given an array of integers of length n, determine whether the array can become a non-decrement array with at most one element changed.

We define a nondecreasing sequence like this: for any I in the array (0 <= I <= n-2), nums[I] <= nums[I + 1].

Example 1:

Input: nums = [4,2,3] Output: true Explanation: You can make the first 4 a non-decreasing sequence by changing it to a 1.Copy the code

Example 2:

Input: nums = [4,2,1] output: false explanation: you cannot change an element to a non-decrement sequence without changing it.Copy the code

AC code:

class Solution { public: bool checkPossibility(vector<int>& nums) { if (nums.size() <= 1) { return true; } int cnt = 0; for (int i = 1; i < nums.size() && cnt < 2; i++) { if (nums[i-1] <= nums[i]) { continue; } cnt++; if (i-2>=0 && nums[i-2] > nums[i]) { nums[i] = nums[i-1]; }else { nums[i-1] = nums[i]; } } return cnt <= 1; }};Copy the code

Ideas:

This problem is difficult, considering the situation is more, the main idea is: one element is less than its previous known elements, if it before another element does not exist, then make before an element is equal to the element, if again before an element, and this element is greater than the elements, so that the element is equal to the previous element; If the previous element is less than this element, making the previous element equal to this element will solve the problem perfectly.

Greedy algorithm seems simple, in fact, there is no fixed routine, add a graph, later brush the question will have to come back to see again:

​

​

​

​