-
In the explanation [Greedy Algorithm: Rebuilding the Queue Based on Height, we mentioned that using vector (dynamic array in C++) to perform insert operations is time-consuming. Intuitively, the insert operation of the array is O(n), and the time complexity of the overall code is O(n^2).
-
For ordinary arrays, once the size is defined, it cannot be changed. For example, int a[10];, this array a can only hold 10 elements at most, and cannot be changed. For dynamic arrays, you don’t have to worry about the initial size and you can put data into it at will. The reason for the time-consuming process lies in the underlying implementation of the dynamic array. First of all, the underlying implementation of vector is also an ordinary array. The size of a vector has two dimensions, one is size and the other is capacity. Size is what we usually use when traversing the vector. Capicity is the size of the underlying array of the vector (that is, an ordinary array). Capicity is not necessarily size. When inserting data, if it is already larger than the capacity, the capacity will be expanded exponentially, but the size exposed to the outside world is actually only + 1.
-
That is to re-apply for an array twice the size of the original array, then copy all the data there, and release the original array memory. (Yes, it’s such a primitive and crude method!)
-
Then the bottom layer actually needs to apply for a normal array of size 6, copy the original elements there, and release the original array memory. Note that the memory starting address of the bottom array in the picture has changed. Use vector to perform the insert operation. At this time, you will find thatAlthough the apparent complexity is
O
(
n
2
)
O(n^2)
O(n2), but the bottom layer does not know how many additional full copies have been made, so including the bottom copy of vector, the overall time complexity can be considered
O
(
n
2
+
t
×
n
)
O(n^2 + t×n)
O(n2 + t×n) level, t is the number of underlying copies.
Topic: Detonate the balloon with the minimum number of arrows
-
There are some spherical balloons attached to a wall represented by an XY plane. The balloons on the wall are recorded in the integer array
points, wherepoints[i] = [xstart, xend]means that the horizontal diameter is betweenxstartandxend. You don’t know the exact y-coordinate of the balloon. -
A bow and arrow can be shotcompletely vertically from different points along the x-axis. Shoot an arrow at the coordinate
x. If there is a balloon with a diameter whose start and end coordinates arex``startandx``end, and ifxstart ≤ x ≤ x``endis satisfied, the balloon will be detonated. There is no limit to the number of arrows that can be fired. Once a bow and arrow is fired, it can move forward indefinitely. -
class Solution {<!-- --> public: static bool cmp(const vector<int> & amp;a,const vector<int> & amp;b){<!-- --> return a[0]<b[0]; } int findMinArrowShots(vector<vector<int>> & amp; points) {<!-- --> if(points.size()==0) return 0; sort(points.begin(),points.end(),cmp); int res=1; for(int i=1;i<points.size();i + + ){<!-- --> if(points[i][0]>points[i-1][1]){<!-- -->// Balloon i and balloon i-1 are not next to each other. Note that this is not >= res++; }else{<!-- --> points[i][1]=min(points[i-1][1],points[i][1]); } } return res; } }; -
Time complexity: O(nlog n), because there is a quick sort; Space complexity: O(n), there is a quick sort, and in the worst case (reverse order), n recursive calls are required. Therefore, it does require O(n) stack space.
-
In order to make the balloons overlap as much as possible, the array needs to be sorted. Sort according to the starting position, then traverse the balloon array from front to back, repeating the balloons as much as possible to the left.
Title: No overlapping intervals
-
Given a set of intervals
intervals, whereintervals[i] = [starti, endi]. Returns the minimum number of intervals that need to be removed so that the remaining intervals do not overlap each other. -
class Solution {<!-- --> public: static bool cmp(const vector<int> & amp;a,const vector<int> & amp;b){<!-- --> return a[0]<b[0]; } int eraseOverlapIntervals(vector<vector<int>> & amp; intervals) {<!-- --> if(intervals.size()==0){<!-- --> return 0; } sort(intervals.begin(),intervals.end(),cmp); int count=0; int end=intervals[0][1]; for(int i=1;i<intervals.size();i + + ){<!-- --> if(intervals[i][0]>=end){<!-- --> end=intervals[i][1]; }else{<!-- --> end=min(end,intervals[i][1]); count + + ; } } return count; } };
Title: Dividing letter intervals
-
You are given a string
s. We need to divide this string into as many segments as possible, and the same letter appears in at most one segment. Note that the division results need to meet the following requirements: concatenate all division results in order, and the resulting string is stills. Returns a list representing the length of each string fragment. -
In the process of traversing, it is equivalent to finding the boundary of each letter. If you find the farthest boundary of all the letters that have been traversed before, it means that this boundary is the dividing point. At this time, all the letters have appeared in front, and the furthest is this boundary. It can be divided into the following two steps:
- Count the last position of each character
- Traverse the characters from the beginning and update the farthest subscript of the character. If the subscript of the farthest position of the character is equal to the current subscript, the split point is found.
-
class Solution {<!-- --> public: vector<int> partitionLabels(string s) {<!-- --> int hash[27]={<!-- -->0}; for(int i=0;i<s.size();i + + ){<!-- -->//Count the last position of each character hash[s[i]-'a']=i; } vector<int> res; int left=0,right=0; for(int i=0;i<s.size();i + + ){<!-- --> right=max(right,hash[s[i]-'a']); if(i==right){<!-- --> res.push_back(right-left + 1); left=i + 1; } } return res; } }; -
Time complexity: O(n); Space complexity: O(1), the hash array used is fixed size
Title: Merging Intervals
-
The array
intervalsrepresents a set of several intervals, where a single interval isintervals[i] = [starti, endi]. Please merge all overlapping intervals and return a non-overlapping interval array that exactly covers all intervals in the input. -
Sort first so that all adjacent intervals overlap as much as possible. You can sort by the left boundary or the right boundary. The processing logic is slightly different. After sorting the left boundary from small to large, if
intervals[i][0] <= intervals[i - 1][1]that is, the left boundary of intervals[i] <= intervals[i - 1 ], there must be overlap. (The adjacent intervals in this question are also considered reposted, so they are <=). -
In fact, just use the left and right boundaries after merging the intervals as a new interval and add it to the result array. If there is no merge, the original range is added to the result array.
-
class Solution {<!-- --> public: vector<vector<int>> merge(vector<vector<int>> & amp; intervals) {<!-- --> vector<vector<int>> res; if(intervals.size()==0){<!-- --> return res; } sort(intervals.begin(),intervals.end(),[](const vector<int> & amp;a,const vector<int> & amp;b){<!-- -->return a[0] <b[0];}); res.push_back(intervals[0]); for(int i=1;i<intervals.size();i + + ){<!-- --> if(res.back()[1]>=intervals[i][0]){<!-- -->//Overlapping intervals res.back()[1]=max(res.back()[1],intervals[i][1]); }else{<!-- --> res.push_back(intervals[i]); } } return res; } };
Topic: Monotonically increasing numbers
-
If and only if the numbers
xandyon each adjacent digit satisfyx <= y, we say that the integer is < strong>Monotonically increasing. Given an integern, return the largest number less than or equal tonthat is monotonically increasing. -
class Solution {<!-- --> public: int monotoneIncreasingDigits(int n) {<!-- --> string strnum=to_string(n); int len_str=strnum.size(); for(int i=strnum.size()-1;i>0;i--){<!-- --> if(strnum[i-1]>strnum[i]){<!-- --> len_str=i; strnum[i-1]--; } } for(int i=len_str;i<strnum.size();i + + ){<!-- --> strnum[i]='9'; } return stoi(strnum); } }; -
Use brute force to solve, submission timeout
-
class Solution {<!-- --> public: bool check(int num){<!-- --> int max_one=10; while(num){<!-- --> int t=num; if(max_one>=t){<!-- --> max_one=t; }else{<!-- --> return false; } num=num/10; } return true; } int monotoneIncreasingDigits(int n) {<!-- --> for(int i=n;i>0;i--){<!-- --> if(check(i)) return i; } return 0; } };
-
Title: Monitoring Binary Tree
-
Given a binary tree, we install cameras on the nodes of the tree. Each camera on a node can monitor its parent, itself, and its immediate children. **Calculate the minimum number of cameras required to monitor all nodes of the tree.
-
The camera can cover the upper, middle and lower layers. If the camera is placed on the leaf node, it will waste one layer of coverage. Therefore, placing the camera at the parent node of the leaf node can make full use of the camera's coverage area. **So we have to look from the bottom up, local optimal: let the parent node of the leaf node install a camera, use the least number of cameras, the overall optimal: use the least number of all cameras! **At this time, the general idea is to go from bottom to top, first put a camera on the parent node of the leaf node, and then put a camera every two nodes until it reaches the head node of the binary tree. You can use postorder traversal, that is, the order in the left and right, so that you can deduce from bottom to top during the backtracking process.
-
At this time, a state transfer formula is needed. Don’t confuse it with the dynamic state transfer formula. There is no merit-based state transfer process in this question, it is a pure state transfer! Let’s see how this state should be transferred. First, let’s see how each node may have several states: This node has no coverage; This node has a camera; This node has coverage.
-
There are three numbers to represent them: 0: This node has no coverage; 1: This node has a camera; 2: This node has coverage
-
class Solution {<!-- --> public: int res; int travesal(TreeNode* cur){<!-- --> if(cur==nullptr){<!-- --> return 2; } int left=travesal(cur->left); int right=travesal(cur->right); if(left==2 & amp; & amp;right==2){<!-- -->// Both left and right nodes are covered return 0; } if(left==0||right==0){<!-- -->//There is no coverage, then the parent node needs to install a camera to cover it res++; return 1; } if(left==1||right==1){<!-- -->//If the child node has a camera, then the parent node is considered to be covered return 2; } // This return -1 logic doesn't go here. return -1; } int minCameraCover(TreeNode* root) {<!-- --> res=0; if(travesal(root)==0){<!-- -->//Post-order traversal res++; } return res; } }; //Logic doesn't go here. return -1; } int minCameraCover(TreeNode* root) {<!-- --> res=0; if(travesal(root)==0){<!-- -->//Post-order traversal res++; } return res; } }; -
Time complexity: O(n), each node on the binary tree needs to be traversed; Space complexity: O(n)