-
This article series is the record, review and share of the author’s leetcode brush questions. Welcome to correct any mistakes.
Greedy algorithms (also known as greedy algorithms) are those that always make the best choice for the moment when solving a problem. In other words, instead of thinking about global optimality, what he makes is a local optimal solution in a sense. Greedy algorithm can not get the overall optimal solution for all problems, the key is the choice of greedy strategy, the choice of greedy strategy must have no aftereffect, that is, the process before a state does not affect the future state, only related to the current state.
Allocation problem
Distribution of biscuits
Idea: Put children and cookies in order, and assign the smallest filling cookie to the child with the least hunger.
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int child = 0;
int cookies = 0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
while(child < g.size() && cookies < s.size()) {if(g[child]<=s[cookies]) child++;
cookies++;
}
returnchild; }};Copy the codecandy
Do a simple double loop to initialize the candy count for all children to 1. If the child on the right scores higher than the child on the left, the number of sweets on the right is updated to the number of sweets on the left plus 1. If the child on the left has a higher rating than the child on the right, and the number of sweets currently on the left is no greater than the number of sweets on the right, the number of sweets on the left is updated to the number of sweets on the right plus 1.
The greedy strategy here is to consider and update only the size relationships of adjacent sides in each iteration.
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size(a);if(size<2) return size;
vector<int> candy(size,1);
for(int i =0; i <size- 1; i++){if(ratings[i+1]>ratings[i]){
candy[i+1] = candy[i]+1; }}for(int i = size - 1; i>0; i--){if(ratings[i- 1]>ratings[i]){
candy[i- 1] = max(candy[i- 1],candy[i]+1); }}return accumulate(candy.begin(),candy.end(),0); }};Copy the codeProblems and flowers
Thinking: It is greedy to traverse the flower bed from left to right, planting only one flower where it can be planted, and planting only one flower where it can be planted (because at any time you will not be better off if you do not plant one).
The conditions for growing flowers here are:
- His is empty
- The left side is empty or the left most
- The right-hand side is empty or the rightmost itself
The code is as follows:
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int s = flowerbed.size(a);for(int i =0; i<s; i++){if(flowerbed[i] ==0 && (i==0 || flowerbed[i- 1] = =0 ) && (i==s- 1 || flowerbed[i+1] = =0)){
n--;
if(n<=0) return true;
flowerbed[i] =1; }}return n<=0; }};Copy the codeThe best time to buy and sell stocks
If we buy and sell on all the rising days and not on all the falling days, we will maximize our profits. Therefore, we can collect all the ups. Breaking all trades that might span multiple days into two adjacent trades is equivalent to buying and selling every day. (Note that this calculation is not an actual trading process. Four buys and four sells are equivalent to buying on day 1 and selling on day 5.)
The code is as follows:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for(int i = 1; i < prices.size(a); i++){ ans +=max(0, prices[i] - prices[i- 1]);
}
returnans; }};Copy the codeRebuild the queue based on height
Ideas: The front node must be higher than the current node after sorting, so the current node can be safely inserted into the position with the subscript N. If the height is the same, the front node must be higher than the current node. This confirms that the current node must have n elements higher than it, so after sorting by height from largest to smallest:
- Local optimal: the priority is to insert according to the k of the tall people. The people after the insert satisfies the queue attribute
- Global optimality: at the end of the insertion operation, the entire queue meets the problem queue attribute
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](vector<int> A, vector<int> B) {
if (A[0] == B[0]) return A[1] < B[1];
return A[0] > B[0];
});
vector<vector<int>> ans;
for (int i = 0; i < people.size(a); i++) { ans.insert(ans.begin() + people[i][1], people[i]);
}
returnans; }};Copy the codeBut use vector is very time-consuming, the vector in the c + + (is a dynamic array is understandable, the bottom is ordinary array) if inserted element is greater than the ordinary array size in advance, there will be a scale at the bottom of the vector operation, namely the application twice the original size of an array of ordinary, then copy the data to another larger array, Finally, the original array memory is freed.
So using a vector to insert is time consuming, and then copying is O(n^2), or maybe even copying several times, not O(n^2).
So variable size, frequent inserts are better for linked lists
class Solution {
public:
// From large to small (the same height and k small stand in front)
static bool cmp(const vector<int> a, const vector<int> b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort (people.begin(), people.end(), cmp);
list<vector<int>> que; // List is a list implementation that is much more efficient than vector
for (int i = 0; i < people.size(a); i++) {int position = people[i][1]; // Insert into position subscript position
std::list<vector<int>>::iterator it = que.begin(a);while (position--) { // Find the insertion position
it++;
}
que.insert(it, people[i]);
}
return vector<vector<int>>(que.begin(), que.end()); }};Copy the codeList encapsulates a linked List, while Vector encapsulates an array. The main difference between List and Vector is that Vector uses contiguous memory. Vector supports the [] operator, whereas List is implemented as a linked List. But for insertions especially in the head insertions are slow, in the tail insertions are fast. A list container is a bidirectional list. Lists are much slower for random access because you might have to traverse the list, but much more efficient for insertion and deletion, where you don’t need to copy and move data, just change the pointer. In addition, Vector has an algorithm for newly added elements, while List can be added arbitrarily.
Range of problems
Unoverlapping interval
Firstly, the interval is sorted in incrementing order according to the size of the end, and the interval with the smallest end that does not overlap with the previous interval is selected each time.
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.empty()) return 0;
int n = intervals.size(a);if(n<2) return 0;
sort(intervals.begin(),intervals.end(), [](vector<int> a,vector<int>b){
return a[1]<b[1];
});
int count =0,prev = intervals[0] [1];
for(int i = 1; i<n; i++){if(intervals[i][0]<prev){
count++;
} else {
prev = intervals[i][1]; }}returncount; }};Copy the codeDetonate the balloon with the minimum number of arrows
Given n closed intervals [x,y], insert a point to fall into the most closed intervals, ask how many points need to determine the minimum
- Interval ending sort
- Take the right end of the current range as a benchmark (find as much overlap as you can without getting shot in front of the range).
- As long as the left end of the next interval <= the benchmark, then overlap, continue to seek to overlap with the next interval
- Until you hit a discoincidence interval, the arrow count is +1
- Repeat with the right end of the new range as your benchmark
The code is as follows:
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int n = points.size(a);if(n<=1) return n;
sort(points.begin(), points.end(), [](vector<int> A, vector<int> B){
return A[1]<B[1];[0,9],[0,6],[7,8]
});
int cur = points[0] [1],count = 1;
for(int i = 1; i<n; i++){if(points[i][0]>cur){
count++;
cur = points[i][1]; }}returncount; }};Copy the codeLetter interval
Since the same letter can only appear in the same fragment, it is obvious that the first and last subscripts of the same letter must appear in the same fragment. So you need to traverse the string to get the last subscript position of each letterOnce you have the last subscript position of each letter, you can use the greedy method of dividing the string into as many fragments as possible, as follows.
-
Traverses the string from left to right, maintaining the start and end subscripts of the current fragment, starting with start=end=0
-
For each accessed letter, get the last subscript position of the current letter and make end= Max (end,end1)
-
The length of the current fragment is end−start+1. Add the length of the current fragment to the return value, and then make start=end+1 to continue looking for the next fragment.
Repeat the process until the string is iterated.
class Solution {
public:
vector<int> partitionLabels(string S) {
int map[26] = {- 1};
vector<int> res;
int star = 0, end = 0;
for(int i = 0; i < S.size(a); i++) { map[S[i] -'a'] = i;
}
for(int i = 0; i < S.size(a); i++){ end =max(end, map[S[i] - 'a']);
if(i == end){
res.push_back(end-star+1);
star = i+1; }}returnres; }};Copy the codeNondecreasing sequence
Ideas: Nums [I] > nums[I + 1] = nums[I + 1] = nums[I + 1] = nums[I + 1] Sometimes it is necessary to change the following smaller number in relation to the size of the preceding number to make the sequence as large as possible: 4,2,3 -1, 4, 2, 2,3,4,2,4
4(i)
/\ 3
/ \ /
/ \/
/ 2(i+1)
-1(i+1)
4 (i) 4
/\ /
/ \ /
/ \ /
3 \ /
(i-1) \/
2(i+1)
Copy the codeAccording to the figure above,
- When nums[I +1] >= nums[i-1], shrink nums[I] because increasing nums[I +1] will destroy the increment sequence
- When nums[I +1] < nums[I +1], zoom in on nums[I +1]
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int s = nums.size(a);if(s <= 2) return true;
bool flag = nums[0] > nums[1]?false:true;
for (int i = 1; i < s - 1; i++) {
if (nums[i] > nums[i + 1]) {
if(flag){
if(nums[i- 1] <= nums[i+1])
nums[i] = nums[i+1];
else
nums[i+1] = nums[i];
flag = false;
} else
return false; }}return true; }};Copy the code