1. Biscuit distribution (NO.455)
Title Description: suppose you are a great parent and want to give your children some cookies. However, each child can only be given one cookie 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 for each biscuit j, there is a size sj. If sj > = gi, we can assign the cookie j to the child i, and the child will be satisfied. Your goal is to meet as many children as possible and output the maximum number. A child can only have one cookie at most.
Solution: biscuits for a child should be as small as possible and can satisfy the child, so that large biscuits can be used for children with greater satisfaction. Because the child with the least satisfaction is the easiest to be satisfied, the child with the least satisfaction should be satisfied first.
#include<algorithm> class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(),g.end());//sort sort(s.begin(),s.end()); int i = 0, j = 0;//Double pointer while(i < g.size() && j < s.size()){ if (g[i] <= s[j]){ i++; } j++; } return i; } };
2. No overlapping interval (NO.435)
Topic Description: given a set of intervals, find the minimum number of intervals to be removed so that the remaining intervals do not overlap each other. It can be considered that the end of the interval is always greater than its starting point. The boundaries of the intervals [1,2] and [2,3] are in "contact" with each other, but do not overlap with each other.
Solution idea: in each choice, the end of the interval is the most important. The smaller the end of the selected interval, the larger the space left for the later interval, and the larger the number of intervals that can be selected later.
Sort by the end of the interval. Select the interval with the smallest end each time and no overlap with the previous interval.
class Solution { public: static bool cmp(vector<int> &a, vector<int> &b){//Sort by tail element from small to large if (a[1] == b[1]) return a[0] < b[0]; else return a[1] < b[1]; } int eraseOverlapIntervals(vector<vector<int>>& intervals) { int n = intervals.size(); if (n == 0 || n == 1) return 0; sort(intervals.begin(),intervals.end(),cmp);//sort int count = 0; vector<int> pre = intervals[0]; for (int i = 1; i < n; i++){ if (intervals[i][0] < pre[1])//Overlap, pre unchanged, i to move backward count++; else pre = intervals[i];//No overlap, both pre and i move backward } return count; } };
3. Throwing darts to pierce the balloon (NO.452)
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's horizontal, the y coordinate doesn't matter, so just knowing the x coordinate at the beginning and end is enough. The start coordinate is always less than the end coordinate. There are up to 104 balloons in the plane.
A bow can shoot completely vertically from different points along the x-axis. If the starting and ending coordinates of the diameter of a balloon are xstart and xend, and xstart ≤ x ≤ xend is satisfied, the balloon will be detonated. There is no limit to the number of bows that can be fired. Once the bow and arrow are shot, they can move forward indefinitely. We want to find the minimum number of bows and arrows needed to make all balloons explode.
Solution idea: it also calculates the number of non overlapping intervals, but the difference between [1,2] and [2,3] is that [1,2] and [2,3] are overlapping intervals.
class Solution { public: static bool cmp(vector<int> &a, vector<int> &b){ if (a[1] == b[1]) return a[0] < b[0]; else return a[1] < b[1]; } int findMinArrowShots(vector<vector<int>>& points) { int n = points.size(); if (n == 0) return 0; sort(points.begin(),points.end(),cmp);//sort vector<int> pre = points[0]; int count = 1; for (int i = 1; i < n; i++){ if (points[i][0] <= pre[1])//The current interval overlaps the previous one continue; count++;//Do not overlap, add 1, and move pre pre = points[i]; } return count; } };
4. Reorganize the queue according to height and serial number (NO.406)
Topic Description: suppose there is a group of people in disorder standing in a queue. Each person is represented by an integer pair (h, k), where h is the height of the person, and k is the number of people in front of the person whose height is greater than or equal to H. Write an algorithm to rebuild the queue.
Input:
[[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]]
Solution idea: in order to make the insertion operation not affect the subsequent operation, the students with higher height should do the insertion operation first, otherwise the k-th position that the students with lower height inserted correctly may become the k+1 position.
The height h is in descending order, the number k is in ascending order, and then a student is inserted into the K position of the queue. For the front line, if we insert a new person with a lower height in the position of K, there will be no impact on the person before K, and no impact on the person who is higher than the new person after K.
class Solution { public: static bool cmp(vector<int> &a, vector<int> &b){ if (a[0] == b[0]) return a[1] < b[1]; else return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { int n = people.size(); sort(people.begin(),people.end(),cmp);//Rearrange the array in descending order of h and ascending order of k for (int i = 1; i < n; i++){ vector<int> temp = people[i]; for (int j = i - 1; j >= temp[1]; j--){ people[j+1] = people[j]; } people[temp[1]] = temp; } return people; } };
5. Maximum return on trading shares (NO.121)
Title Description: given an array, its ith element is the price of a given stock on the ith day. If you are only allowed to complete one transaction at most (that is, to buy and sell a stock once), design an algorithm to calculate the maximum profit you can obtain.
Solution idea: just record the minimum price in front of you, take the minimum price as the purchase price, and then take the current price as the sold price to see whether the current income is the maximum income.
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; int minPrice = prices[0]; int max = 0; for (int i = 1; i < n; i++){ if (prices[i] - minPrice > max) max = prices[i] - minPrice; if (prices[i] < minPrice) minPrice = prices[i]; } return max; } };
6. Maximum return on trading of shares II (NO.122)
Title Description: given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can get. You can do as many trades as you can (buy and sell a stock multiple times).
Solution: buy at a low price, sell at the local highest price, buy at a low price, sell at a high price. When a price [i] is accessed and the price [i] - prices[i-1] > 0, then the price [i] - prices[i-1] is added to the revenue.
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; int profit = 0; for (int i = 1; i < n; i++){ if (prices[i] - prices[i-1] > 0) profit = profit + prices[i] - prices[i-1]; } return profit; } };
7. Planting flowers (NO.605)
Title Description: suppose you have a very long flower bed. Some of the plots are planted with flowers, while others are not. However, flowers can't be planted on adjacent plots. They will fight for water, and both will die. Given a flower bed (represented as an array containing 0 and 1, where 0 represents no flowers planted, 1 represents flowers planted), and a number n. Can n flowers be planted without breaking the planting rules? Returns True if it can, or False if it cannot.
Solution idea: add 0 to the front and last faces of the array. If the element of a position is 0, and the elements of its front and back are also 0, then the position can be planted. Count and add 1, and change the value of the position to 1, indicating that there are flowers here.
class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { int length = flowerbed.size(); flowerbed.insert(flowerbed.begin(),0); flowerbed.push_back(0); int count = 0; for (int i = 1; i <= length; i++){ if (flowerbed[i-1] == 0 && flowerbed[i+1] == 0 && flowerbed[i] == 0){ count++; flowerbed[i] = 1; } } return count >= n; } };
8. Judge whether it is a subsequence (NO.392)
Topic Description: given the strings S and t, determine whether s is a subsequence of t. A subsequence of a string is a new string formed by deleting some (or not) characters from the original string without changing the relative positions of the remaining characters. (for example, "ace" is a subsequence of "abcde", while "aec" is not).
Solution idea: use double pointer, one pointer points to the element in s, the other pointer points to the element in T, judge whether it is the same, if it is the same, move backward at the same time, otherwise, the pointer to the element in t moves backward, and finally judge whether it has traversed the element in S.
class Solution { public: bool isSubsequence(string s, string t) { int length1 = s.size(); int length2 = t.size(); int i = 0, j = 0;//Double pointer while(i < length1 && j < length2){ if (s[i] == t[j]) i++; j++; } return i == length1; } };
9. Modify a number to a non recursive subtraction group (NO.665)
Title Description: give you an integer array of length N, please judge whether the array can become a non recursive subtraction column when changing at most one element. We define a non recursive subtraction column as follows: for all I (0 < = I < = n-2) in the array, nums [i] < = nums [i + 1] is always satisfied.
Solution idea: if nums[i] < nums[i-1], there are two options. The first is to make nums[i-1] smaller, i.e. to make nums[i-1]=nums[i]; the second is to make nums[i] larger, i.e. to make nums[i]=nums[i-1], but this will affect the subsequent process. Only when nums[i] < nums[i-2], can we make such a choice.
class Solution { public: bool checkPossibility(vector<int>& nums) { int cnt = 0; for (int i = 1; i < nums.size() && cnt < 2; i++){ if (nums[i] >= nums[i-1]) continue; cnt++; if (i-2 >= 0 && nums[i] < nums[i-2]) nums[i] = nums[i-1];//Increase nums[i] else nums[i-1] = nums[i];//Reduce nums[i-1] } return cnt <= 1; } };
10. Sum of the largest subarray (NO.53)
Topic Description: given an integer array nums, find a continuous subarray with the maximum sum (subarray contains at least one element), and return its maximum sum. For example, for an array [- 2,1, - 3,4, - 1,2,1, - 5,4], the sum of its consecutive subarrays [4, - 1,2,1] is the maximum, which is 6.
Solution: dynamic planning. Use sum to record the maximum sum of successive subarrays ending with i-1 elements. If pre sum > 0, update pre sum to num[i] + pre sum. If pre sum < 0, directly update pre sum to num[i]. Use maxSum to record the maximum sum.
class Solution { public: int maxSubArray(vector<int>& nums) { int preSum = nums[0]; int maxSum = nums[0]; for (int i = 1; i < nums.size(); i++){ preSum = preSum > 0 ? nums[i] + preSum : nums[i]; maxSum = max(preSum,maxSum); } return maxSum; } };
11. Separate strings to make the same characters appear together (NO.763)
Title Description: the string S is composed of lowercase letters. We want to divide the string into as many segments as possible, and only one segment will have the same letter. Returns a list representing the length of each string fragment.
Input: S = "ababcbaca defegde hijhklij"; the division result is "ababcbaca", "defegde", "hijhklij".
Output: [9,7,8]
Solution idea: use an array lastIndexsOfchar [] to record the last position of each character in the string. First index points to the first position of a fragment, lastIndex points to the tail position of the fragment, traverses all elements between them, and updates the tail position until it traverses to the tail position.
class Solution { public: vector<int> partitionLabels(string S) { vector<int> lastIndexsOfchar(26,0); for (int i = 0; i < S.size(); i++){ lastIndexsOfchar[charToIndex(S[i])] = i; } int firstIndex = 0; vector<int> result; while (firstIndex < S.size()){ int lastIndex = firstIndex; for (int i = firstIndex; i < S.size() && i <= lastIndex; i++){ int index = lastIndexsOfchar[charToIndex(S[i])]; if (index > lastIndex) lastIndex = index; } result.push_back(lastIndex-firstIndex+1); firstIndex = lastIndex + 1; } return result; } int charToIndex(char c){ return c - 'a'; } };