Problem Solving
1.1 Evaluate Reverse Polish Notation
- Original Link: Code Suizhanglu
- Problem Link: 150. Evaluate Reverse Polish Notation - LeetCode
Description
Given an array of strings tokens represanting a postfix expression, compute the result of this expression. Return an integer representing the value of the expression.
Notes:
- Valid operators are
'+','-','*', and'/'. - Each operand can be an integer or another expression.
- Division between two integers truncates towards zero.
- No division by zero in the input.
- The input is a valid postfix expression.
- Answers and all intermediate results can be represented as 32-bit integers.
Example 1:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
Constraints:
1 <= tokens.length <= 10^4tokens[i]is an operator ("+","-","*", or"/"), or an integer in the range[-200, 200]
Reverse Polish Notation: A postfix notation where operators appear after their operands. It eliminates the need for parentheses and is well-suited for stack-based computation.
Initial Thoughts
Follow the video instructions and proceed to solve the problem.
Solution
Use a stack to evaluate the postfix expression:
- Push numbers onto the stack.
- When encountering an operator, pop the top two elements, perform the operation, and push the result back onto the stack.
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (string token : tokens) {
if (token == "+" ||
token == "-" ||
token == "*" ||
token == "/") {
int val2 = st.top();
st.pop();
int val1 = st.top();
st.pop();
int res;
res = (token == "+" ? val1 + val2 : res);
res = (token == "-" ? val1 - val2 : res);
res = (token == "*" ? val1 * val2 : res);
res = (token == "/" ? val1 / val2 : res);
st.push(res);
} else {
st.push(stoi(token));
}
}
return st.top();
}
};
Challenges
None encountered during initial implementation.
Summary
This problem involves evaluating a postfix expression using a stack, which is a common data structure application.
1.2 Sliding Window Maximum
- Original Link: Code Suizhanglu
- Problem Link: 239. Sliding Window Maximum - LeetCode
Description
Given an array nums and a window size k, move the window from left to right and find the maximum value in each window position.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
Initial Thoughts
Watch the video explanation first.
Solution
Use a monotonic queue to efficiently track the maximum value within the sliding window.
class Solution {
private:
class MonotonicQueue {
private:
deque<int> dq;
public:
void pop(int x) {
if (!dq.empty() && dq.front() == x) {
dq.pop_front();
}
}
void push(int x) {
while (!dq.empty() && dq.back() < x) {
dq.pop_back();
}
dq.push_back(x);
}
int getMax() {
return dq.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue mq;
vector<int> res;
for (int i = 0; i < k; i++) {
mq.push(nums[i]);
}
res.push_back(mq.getMax());
for (int i = 0; (i + k) < nums.size(); i++) {
mq.pop(nums[i]);
mq.push(nums[i + k]);
res.push_back(mq.getMax());
}
return res;
}
};
Challenges
No significant challenges encountered.
Summary
The solution uses a monotonic queue to maintain the maximum value efficiently within a sliding window.
1.3 Top K Frequent Elements
- Original Link: Code Suizhanglu
- Problem Link: 347. Top K Frequent Elements - LeetCode
Description
Given an array nums and an integer k, return the top k frequent elements. You may return the enswer 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]
Constraints:
1 <= nums.length <= 10^5kis in the range[1, number of unique elements in the array]- The answer is guaranteed to be unique.
Advanced Requirement:
The algorithm must have a time complexity better than O(n log n).
Initial Thoughts
Use a hash map to count frequencies, but this approach has a time complexity of O(n log n).
Solution
Use a min-heap to maintain the top k frequent elements.
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freqMap;
for (int num : nums) {
freqMap[num]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
for (auto& entry : freqMap) {
pq.push(entry);
if (pq.size() > k) {
pq.pop();
}
}
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pq.top().first;
pq.pop();
}
return result;
}
};
Challenges
Understanding C++'s heap syntax took some time.
Summary
This problem introduces the use of a min-heap to efficiently retrieve the top k frequent elements.
Summary and Review
Spent considerable time on syntax-related issues, highlighting the need for further study. This chapter covered stacks and queues, including their use in simulating each other and solving classic problems like matching brackets and string deduplication. The three problems addressed today involved postfix evaluation with a stack, sliding window maximum with a monotonic queue, and top-k frequent elements with a min-heap.