preface

When I first know LeetCode and algorithm, I will record my algorithm learning experience in this series of articles. In the early stage, I mainly supervise my learning and clock in. In the later stage, I will slowly add my understanding of knowledge to the articles. I hope you can gain something from reading my articles. The order of this series of articles is Code Capriccio As a clue.

1, Implement queue with stack

Title:
Please use only two stacks to implement the first in first out queue. The queue should support all operations supported by the general queue (push, pop, peek, empty):

Implement MyQueue class:

void push(int x) Will element x Push to the end of the queue
int pop() Removes and returns an element from the beginning of the queue
int peek() Returns the element at the beginning of the queue
boolean empty() If the queue is empty, return true ；Otherwise, return false

explain:

You can only use standard stack operations - that is, only push to top, peek/pop from top, size, and is empty The operation is legal.
Your language may not support stacks. You can use list perhaps deque(To simulate a stack, as long as it is a standard stack operation.

Example 1:

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 1, 1, false]

Explanation:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Tips:

1 <= x <= 9
 Up to 100 calls push,pop,peek and empty
 Assume that all operations are valid (for example, an empty queue will not be called) pop perhaps peek Operation)

Advanced:

Can you achieve equal sharing of time for each operation, with a complexity of O(1) Queue? In other words, execution n The total time complexity of operations is O(n) ，Even if one of these operations may take a long time.

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. Use two stacks, one as input and one as output;
2. Learn code reuse;

code:

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        //Import data from stIn only when STUT is empty
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return stOut.empty() && stIn.empty();
    }
};

2, Implement stack with queue

Title:
Please use only two queues to implement a last in first out (LIFO) stack, and support all four operations of the ordinary stack (push, top, pop and empty).

Implement MyStack class:

void push(int x) Will element x Press into the top of the stack.
int pop() Remove and return the top of stack element.
int top() Returns the top of stack element.
boolean empty() If the stack is empty, return true ；Otherwise, return false . 

be careful:

You can only use the basic operations of the queue -- that is push to back,peek/pop from front,size and is empty These operations.
Your language may not support queues. You can use list (List) or deque(To simulate a queue , As long as it is a standard queue operation.

Example:

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 2, 2, false]

Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // Return 2
myStack.pop(); // Return 2
myStack.empty(); // Return False

Tips:

1 <= x <= 9
 Up to 100 calls push,pop,top and empty
 Every call pop and top Ensure that the stack is not empty

Advanced: can you implement the stack with only one queue.

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. Only one queue is needed, that is, before each pop-up of the last element, move the first few elements to the end of the queue;

code:

class MyStack {
public:
    queue<int> que;
    MyStack() {

    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size = que.size();
        size--;
        while(size--){
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

3, Valid parentheses

Title:
Given a string s that only includes' (',') ',' {','} ',' [','] ', judge whether the string is valid.

Valid strings must meet:

The left parenthesis must be closed with the same type of right parenthesis.
The left parentheses must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "() [] {}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Tips:

1 <= s.length <= 104
s Parentheses only '()[]{}' form

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. Use stack knowledge to solve the problem of symmetry

code:

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for(int i = 0; i < s.size(); i++){
            if (s[i] == '(') st.push(')');
            else if (s[i] == '[') st.push(']');
            else if (s[i] == '{') st.push('}');
            else if(st.empty() || st.top() != s[i]) return false;
            else st.pop();
        }
        return st.empty();
    }
};

4, Deletes all adjacent duplicates in the string

Title:
Given the string S composed of lowercase letters, the duplicate deletion operation will select two adjacent and identical letters and delete them.

Repeat the duplicate deletion operation on S until the deletion cannot continue.

Returns the final string after all deduplication operations are completed. The answer is guaranteed to be unique.

Example:

Enter: "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca", we can delete "bb". Because the two letters are adjacent and the same, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", in which only "aa" can perform duplicate deletion, so the final string is "ca".

Tips:

1 <= S.length <= 20000
S It consists of lowercase English letters only.

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. Use stack knowledge to solve

code:

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for(char s : S){
            if(st.empty() || s != st.top()){
                st.push(s);
            }else{
                st.pop();
            }
        }
        string result = "";
        while(!st.empty()){
            result += st.top();
            st.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

5, Evaluation of inverse Polish expression

Title:
Find the value of the expression according to the inverse Polish representation.

Valid operators include +, -, *, /. Each operand can be an integer or another inverse Polish expression.

Note that the division between two integers only retains the integer part.

It can be guaranteed that the given inverse Polish expression is always valid. In other words, an expression always yields a valid value and there is no case where the divisor is 0.

Example 1:

Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: this formula is transformed into a common infix arithmetic expression: ((2 + 1) * 3) = 9

Example 2:

"[" + "," token 4 ", [" + ",]
Output: 6
Explanation: this formula is transformed into a common infix arithmetic expression: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10", "6", "9", "3", "+", "- 11", "", "/", "" 17 "," + "," 5 "," + "]
Output: 22
Explanation: this expression is transformed into a common infix arithmetic expression:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Tips:

1 <= tokens.length <= 104
tokens[i] It's an operator("+","-","*" or "/")，Or in the range [-200, 200] An integer in

Inverse Polish expression:

Inverse Polish expression is a suffix expression. The so-called suffix means that the operator is written after it.

The commonly used formula is an infix expression, such as ( 1 + 2 ) * ( 3 + 4 ) . 
The inverse Polish expression of the formula is written as ( ( 1 2 + ) ( 3 4 + ) * ) . 

The inverse Polish expression has the following two advantages:

After removing the brackets, the expression is unambiguous, even if the above formula is written as 1 and 2 + 3 4 + * The correct results can also be calculated according to the order.
Suitable for stack operation: enter the stack when encountering numbers; In case of an operator, take out the two numbers at the top of the stack for calculation, and press the result into the stack

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. Use the knowledge of stack to solve it. When you encounter numbers, press the stack, and when you encounter operators, pop up two numbers from the stack for operation.

code:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (int i = 0; i < tokens.size(); i++) {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if(tokens[i] == "+") st.push(num2 + num1);
                if(tokens[i] == "-") st.push(num2 - num1);
                if(tokens[i] == "*") st.push(num2 * num1);
                if(tokens[i] == "/") st.push(num2 / num1);  
            }else {
                st.push(stoi(tokens[i]));
            }
        }
        int result = st.top();
        st.pop();
        return result;
    }
};

6, Sliding window Max

Title:
Give you an integer array nums, with a sliding window of size k moving from the leftmost side of the array to the rightmost side of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.

Example 1:

Input: num = [1,3, - 1, - 3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Maximum position of sliding window

[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: num = [1], k = 1
Output: [1]

Tips:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. About "how can the sorted queue pop up the elements to be removed from the window (this element may not be the maximum value)? Another expression is how the queue maintains all the elements in the window". Understand: in fact, the information of the maximum value can contain information smaller than the maximum value, because the topic is to find the maximum value. For example, 3 in 1, 2 and 3 can represent 1, 2 and 3, because 3 is the largest of the three numbers, 1 and 2 can be ignored.

code:

class Solution {
    class MyQueue{
        public:
            deque<int> que;
            void pop(int value){
                if(!que.empty() && value == que.front()){
                    que.pop_front();
                }
            }
            void push(int value){
                while(!que.empty() && value > que.back()){
                    que.pop_back();
                }
                que.push_back(value);
            }
            int front(){
                return que.front();
            }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for(int i = 0; i < k; i++){
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i = k; i < nums.size(); i++){
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

7, Top K high frequency elements

Title:
Give you an integer array nums and an integer k. please return the elements with the highest frequency of k. You can return answers in any order.

Example 1:

Input: num = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: num = [1], k = 1
Output: [1]

Tips:

1 <= nums.length <= 105
k The value range of is [1, Number of different elements in the array]
The question data ensures that the answer is unique, in other words, the first one in the array k The set of high frequency elements is unique

Advanced: the time complexity of the algorithm you design must be better than O(n log n), where n is the size of the array.

Source: LeetCode link: https://leetcode-cn.com/problems/binary-search

Idea:
1. Imitation function and imitation function rewriting can see this link
2. After the functor rewrites (), it pops up from the last element of the sequence.
3. Small top heap and large top heap are determined according to the sequence of elements after pop-up.

code:

class Solution {
public:
    class mycomparison {
    public:
        bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs){
            return lhs.second > rhs.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(int i = 0; i < nums.size(); i++){
            map[nums[i]]++;
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pri_que;
        for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
            pri_que.push(*it);
            if(pri_que.size() > k){
                pri_que.pop();
            }
        }
        vector<int> result(k);
        for(int i = k - 1; i >= 0; i--){
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};