9.15 部分算法题总结

工作内容

1、总结有关栈和队列的相关题型
2、总结coodsheep发布的算法题大集锦
3、看RT Huang的GitHub

剑指上有关栈的题目总结：1、用队列实现栈，2、栈实现队列 ，3、包含min函数的栈，4、 合法的出战序列

1、用队列实现栈

无论是两个队列还是一个队列去实现栈的功能，思路都是一样的，在压入当前数值时，先把队列内之前的元素要么移动到辅助队列里，压入元素后再移动回来。要么就是直接在一个队列里进行操作，即只保留最后一个压入元素，在尾部压入头部元素，再删除头部元素。

1.1 两个队列实现栈

class MyStack {
public:
    queue<int> qi; //主队列
    queue<int> qt; //辅助队列
    MyStack() {
    }
    void push(int x) {
        while(qi.size()) { //将qi中的元素全部搬至qt
            qt.push(qi.front());
            qi.pop();
        }
        qi.push(x);  //插入新元素
        while(qt.size()) {  //将qt中的元素全部搬回qi
            qi.push(qt.front());
            qt.pop();
        }
    }
    int pop() {
        int temp = qi.front();
        qi.pop();
        return temp;
    }
    int top() {
        return qi.front();
    }
    bool empty() {
        return qi.empty();
    }
};

1.2 单队列实现栈

class MyStack {
public:
    queue<int> q; //单队列
    MyStack() {
    }
    void push(int x) {
        q.push(x);
        for(int i = 0; i < q.size() - 1; i ++) { //交换位置
            q.push(q.front());
            q.pop();
        }
    }
    int pop() {
        int temp = q.front();
        q.pop();
        return temp;
    }
    int top() {
        return q.front();
    }
    bool empty() {
        return q.empty();
    }
};

2、栈实现队列

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        int a;
        if(stack2.empty()){
            while(!stack1.empty()){
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top();
        stack2.pop();
        return a;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

3、包含min函数的栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

思路：1、设置一个压入栈，压入数值。设置一个辅助栈，保存最小值。2、弹出时，当压入栈和辅助栈的数相等时，同时弹出，否则压入栈弹出。因为相等时，即代表当前元素为最小值，如果弹出，则该最小值不再是当前值。

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    stack<int>s;
    stack<int>Min;
    void push(int x) {
        s.push(x);
        if(Min.empty()||x<=Min.top())Min.push(x);
    }

    void pop() {
        if(!s.empty()){
            if(s.top()==Min.top())Min.pop();
            s.pop();
        }
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return Min.top();
    }
};

4、 合法的出战序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

思路：定义一个栈，向栈里添加第一个序列元素，直到与第二序列元素相等时，栈弹出，二序列往后移动一位。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {       
        stack<int> p;
        int j = 0; //记录弹出序列的位置
        for(int i = 0; i< pushed.size();i++)
        {
            p.push(pushed[i]);
            while(!p.empty() &&p.top() == popped[j] )
            {
                p.pop();
                j++;
            }

        }

        if(p.empty())
            return true;
        return false;
    }
};