150. Inverse Polish expressions
You are given an array of strings, tokens, representing an arithmetic expression according to the inverse Polish representation.
You are asked to compute the expression. Returns an integer representing the value of the expression.
Attention:
Valid operators are '+', '-', '*' and '/'.
Each operand (operation object) can be an integer or another expression.
Division between two integers always truncates to zero.
The expression does not contain a divide-by-zero operation.
The input is an arithmetic expression expressed according to the inverse Polish representation.
The answer and all intermediate calculations can be expressed as 32-bit integers.
Example 1:
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: This equation translates to the common medial arithmetic expression: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4", "13", "5","/", "+"]
Output: 6
Explanation: This equation translates to the common mid-range arithmetic expression: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10", "6", "9", "3", "+","-11", "*","/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: the equation translates to the common medial arithmetic expression as:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5)
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Tip:
1 <= <= 104
tokens[i] is an operator ("+", "-", "*" or "/") or an integer in the range [-200, 200].
Inverse Polish expressions:
An inverse Polish expression is a postfix expression, by which is meant that the operator is written after it.
The usual use of arithmetic is then a medial expression such as ( 1 + 2 ) * ( 3 + 4 ).
The inverse Polish expression of this equation is written as ( ( 1 2 + ) ( 3 4 + ) * ).
Inverse Polish expressions have two main advantages:
After removing the parentheses, there is no ambiguity in the expression, and even if the above equation is written as 1 2 + 3 4 + *, the correct result can be calculated according to the order.
Suitable for arithmetic with stack operations: when encountering a number, it goes onto the stack; when encountering an operator, it removes the top two numbers from the stack to perform the calculation and presses the result onto the stack
Positive solution (stack)
A very classic question on the stack
The title also gives a general idea of how the simulation will work:
When it encounters a number, it goes on the stack; when it encounters an arithmetic character, it takes out the top two numbers of the stack to compute and presses the result into the stack
As long as the simulation is done along these lines it will be fine;
Upcode (●'◡'●)
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// Power Buckle modified the background test data，requirelonglong
stack<long long> st;
for (int i = 0; i < (); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = ();
();
long long num2 = ();
();
if (tokens[i] == "+") (num2 + num1);
if (tokens[i] == "-") (num2 - num1);
if (tokens[i] == "*") (num2 * num1);
if (tokens[i] == "/") (num2 / num1);
} else {
(stoll(tokens[i]));
}
}
int result = ();
(); // Pop the last element of the stack.（Actually, it's fine if it doesn't pop up）
return result;
}
};
In fact the inverse Polish expression is equivalent to a backward traversal in a binary tree;
We can draw a binary tree by using the operators as intermediate nodes, following the rules of backward traversal;
239. Sliding window maximum
Given an array of integers, nums, there is a sliding window of size k that moves from the leftmost side of the array to the rightmost side of the array. You can only see the k numbers within the sliding window. The sliding window moves to the right one digit at a time.
Returns the maximum value in the sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output : [3,3,5,5,6,7]
Explanation:
Position of the sliding window Max.
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Tip:
1 <= <= 105
-104 <= nums[i] <= 104
1 <= k <=
discrimination
Violent methods:
The process of iterating through it again finds the largest value from the window each time again;
This is clearly\(O(nk)\)of the algorithm;
However, the topic requires linear time complexity;
Positive solution (monotonic queue)
This is a good question for a monotonic queue
We need a queue for that:
Put in the elements in the window, and then as the window moves, the queue goes in and out;
After each move, the queue tells us what the maximum value inside is.
Each time the window moves, call (value of the element removed from the sliding window), (value of the element added to the sliding window), and then () returns the maximum value we want.
To analyze it further, the elements in the queue must be sorted and the maximum value must be placed in the outgoing queue, otherwise how do you know the maximum value.
But if you put all the elements in the window into the queue, the queue needs to pop the elements when the window moves.
So the question is, how can a queue that has been sorted pop up the element (which is not necessarily the maximum value) that the window wants to remove.
In fact, it is not necessary to maintain all the elements in the window, only need to maintain the elements that have the potential to become the maximum value of the window can be, while ensuring that the value of the elements in the queue is from the largest to the smallest.
Then the queue that maintains monotonically decreasing elements is called a monotonic queue, i.e., a monotonically decreasing or monotonically increasing queue.There is no direct support for monotonic queues in C++, so we need to implement a monotonic queue ourselves.
Upcode (●'◡'●)
class Solution {
private.
class MyQueue { //monotonic queues (largest to smallest)
public.
deque<int> que; // Use deque to implement a monotonic queue.
// Each time it is popped, compare whether the current value to be popped is equal to the value of the queue's exit element, and pop if it is equal.
// Also pop before determining whether the queue is currently empty.
void pop(int value) {
if (! () && value == ()) {
que.pop_front();
}
}
// If the value of push is greater than the value of the entry element, then pop the value at the back end of the queue until the value of push is less than or equal to the value of the entry element of the queue.
// This keeps the values in the queue monotonically large to small.
void push(int value) {
while (! () && value > ()) {
que.pop_back();
}
que.push_back(value);
}
// Query the maximum value in the current queue. Just return the front of the queue.
int front() {
return ();
}
}; }
public.
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result.
for (int i = 0; i < k; i++) { // put the first k elements into the queue first
(nums[i]);
}
result.push_back(()); // result records the maximum value of the first k elements
for (int i = k; i < (); i++) {
(nums[i - k]); // slide the window to remove the top element
(nums[i]); // add last element before sliding window
result.push_back(()); // record the corresponding maximum value
}
return result.
}
}; }
Looking at the time complexity again, the time complexity of using a monotonic queue is O(n).
347. First K high frequency elements
Given an array of integers, nums, and an integer, k, you are asked to return the elements of the array that occur in the top k frequencies. You can return the answers in any order.
Example 1.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2.
Input: nums = [1], k = 1
Output: [1]
Tip:
1 <= <= 105
The value of k is in the range [1, the number of elements in the array that are not identical]
The question data guarantees that the answer is unique; in other words, the set of the first k high-frequency elements of the array is unique
Advanced: The time complexity of your algorithm must be better than the time complexity of the\(O(n log n)\) where n is the size of the array.
Positive solution (priority queue)
This question involves the following three main pieces:
To count the frequency of occurrence of an element
Ordering of frequencies
Find the first K high-frequency elements
First count the frequency of occurrence of the element, this type of problem can be counted using map.
Then there's sorting the frequencies, and one container adapter we can use here is a priority queue.
What is a priority queue?
In fact, it is a heap in the guise of a queue, because the external interface of the priority queue is just to take elements from the head of the queue, add elements from the end of the queue, and then no other way to take elements, it looks like a queue.
And the elements inside the priority queue are automatically ordered according to the weights of the elements. So how is it ordered?
By default priority_queue sorts the elements using a max-heap, which is a complete binary tree in the form of a vector.
The process of finding the first k largest elements is shown in the figure: (there are only three frequencies in the figure, so they form exactly one small top heap of size 3, which is used for scanning if there are more frequencies)
Upcode (●'◡'●)
class Solution {
public.
// Small top heap
class mycomparison {
public.
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return > ;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// To count the frequency of occurrence of an element
unordered_map<int, int> map; // map<nums[i], corresponding to the number of occurrences >
for (int i = 0; i < (); i++) {
map[nums[i]]++;
}
// Sort the frequencies
// Define a small top heap of size k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// Sweep the values of all frequencies using a small top heap of fixed size k
for (unordered_map<int, int>::iterator it = (); it ! = (); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // If the size of the heap is greater than k, the queue is popped, ensuring that the size of the heap is always k
pri_que.pop();
}
}
// Find the first K high-frequency elements, and output them to the array in reverse order, since the smallest one is popped first on the small-topped heap
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
result; return result.
}
}; }
Time Complexity.\(O(nlogk)\)
Space complexity.\(O(n)\)
It's not easy to write a blog, so please give me some support 8~!