zijing2333...大约 9 分钟

232. 用栈实现队列open in new window

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现MyQueue类：

  • void push(int x) 将元素 x 推到队列的末尾

  • int pop() 从队列的开头移除并返回元素

  • int peek() 返回队列开头的元素

  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有push to top, peek/pop from top, size, 和 is empty操作是合法的。 你所使用的语言也许不支持栈。你可以使用list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

提示：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

解题思路

两个栈实现队列，经典问题。元素入队全压入第一个栈，出队全从第二个栈中pop。如果第二个栈为空，就把第一个栈中所有元素全压入第二个栈。具体操作如下：

  1. 初始化： 定义两个栈 x1 和 x2，用 vector<int> 实现。

  2. push 操作： 当需要将元素 x 添加到队列尾部时，直接将元素 x 添加到栈 x1 的顶部。

  3. pop 操作：

    a. 如果栈 x2 为空，将栈 x1 的元素依次弹出并压入栈 x2。这样可以将队列的头部元素移到栈 x2 的顶部。

    b. 弹出栈 x2 的顶部元素并返回。该元素是队列的头部元素。

  4. peek 操作：

    a. 如果栈 x2 为空，将栈 x1 的元素依次弹出并压入栈 x2。这样可以将队列的头部元素移到栈 x2 的顶部。

    b. 返回栈 x2 的顶部元素。该元素是队列的头部元素。

  5. empty 操作： 如果栈 x1 和栈 x2 都为空，则队列为空。返回 true，否则返回 false。

class MyQueue {
public:
    /** Initialize your data structure here. */
        vector<int> x1;
        vector<int> x2;
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        x1.push_back(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(x2.size()==0){
            while(x1.size()!=0) 
            {
                x2.push_back(x1.back());
                x1.pop_back();
            }
        }
        int result=x2.back();
        x2.pop_back();
        return result;       
    }
    
    /** Get the front element. */
    int peek() {
        if(x2.size()==0){
            while(x1.size()!=0) 
            {
                x2.push_back(x1.back());
                x1.pop_back();
            }
        }
        return x2.back();  
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return (x1.size()==0 && x2.size()==0);
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

225. 用队列实现栈open in new window

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

解题思路

经典题目了，在 push 操作时，元素被添加到非空队列的尾部，并将另一个队列的元素依次移到非空队列中，以保持栈顶元素始终在非空队列的头部。在进行 pop、top 和 empty 操作时，只需检查和操作非空队列。具体操作如下：

  1. 初始化：定义两个队列 q1 和 q2。
  2. push 操作： a. 将元素 x 压入非空队列的尾部。 b. 将另一个队列的全部元素依次出队并压入非空队列的尾部。这样，非空队列的顶部就是栈顶元素。
  3. pop 操作： a. 弹出非空队列的头部元素。该元素是栈顶元素。
  4. top 操作： a. 返回非空队列的头部元素。该元素是栈顶元素。
  5. empty 操作： a. 如果两个队列都为空，则栈为空。返回 true，否则返回 false。
class MyStack {
public:
    deque<int> q1, q2;
    MyStack() {
    }
    
    void push(int x) {
        if (q1.empty()) {
            q1.push_back(x);
            while (!q2.empty()) {
                q1.push_back(q2.front());
                q2.pop_front();
            }
        } else {
            q2.push_back(x);
            while (!q1.empty()) {
                q2.push_back(q1.front());
                q1.pop_front();
            }
        }
    }
    
    int pop() {
        int top_element;
        if (!q1.empty()) {
            top_element = q1.front();
            q1.pop_front();
        } else {
            top_element = q2.front();
            q2.pop_front();
        }
        return top_element;
    }
    
    int top() {
        return q1.empty() ? q2.front() : q1.front();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();
    }
};

155. 最小栈open in new window

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

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

解题思路

用两个栈，一个栈保存当前push进去元素所对应的最小元素，另一个栈就是普通的push pop。

所以push就push两次，一次直接push当前元素，另一次push当前最小元素

pop也pop两次，获取最小元素就是访问保存最小元素栈的栈顶。具体操作如下：

  1. 初始化：定义两个栈st和st1。st 用作普通栈，st1 用于存储当前栈中的最小元素。

  2. push 操作：

    a. 将要插入的元素 val 添加到 st 向量的末尾。

    b. 如果 st1 非空，则将 val 与 st1 向量末尾的元素进行比较，将较小值添加到 st1 向量的末尾。

    c. 如果 st1 为空，则直接将 val 添加到 st1 向量的末尾。

  3. pop 操作： 分别从 st 和 st1 向量的末尾删除一个元素。

  4. top 操作： 返回 st 向量末尾的元素。

  5. getMin 操作： 返回 st1 向量末尾的元素，即当前栈中的最小值。

class MinStack {
public:
    vector<int> st;
    vector<int> st1;
    MinStack() {

    }
    
    void push(int val) {
        if(!st1.empty()) {
            st1.emplace_back(min(val, st1.back()));
        }else {
            st1.push_back(val);
        }
        st.emplace_back(val);
    }
    
    void pop() {
        st.pop_back();
        st1.pop_back();
    }
    
    int top() {
        return st.back();
    }
    
    int getMin() {
        return st1.back();
    }
};

20. 有效的括号open in new window

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。

解题思路

跟括号匹配其实一个思路，只不过这次变成了3种括号，碰到左括号就压栈，碰到右括号就看栈顶左括号匹不匹配，不匹配就g，匹配就把栈顶pop掉。具体操作如下：

  1. 初始化一个字符向量（vector）st，用作栈。

  2. 遍历字符串 s 中的所有字符：

    a. 如果字符为开括号 (、[ 或 {，将其添加到栈 st 的末尾。

    b. 如果字符为闭括号 )，检查栈 st 是否为空且栈顶元素为对应的开括号 (。如果是，则从栈中弹出栈顶元素；否则，返回 false。

    c. 如果字符为闭括号 ]，检查栈 st 是否为空且栈顶元素为对应的开括号 [。如果是，则从栈中弹出栈顶元素；否则，返回 false。

    d. 如果字符为闭括号 }，检查栈 st 是否为空且栈顶元素为对应的开括号 {。如果是，则从栈中弹出栈顶元素；否则，返回 false。

  3. 在遍历结束后，检查栈 st 是否为空。如果为空，说明所有括号都正确闭合，返回 true；否则，返回 false。

通过使用栈数据结构，我们可以在遍历过程中有效地跟踪和匹配开括号和闭括号。在遇到闭括号时，我们检查栈顶元素是否与之匹配，如果匹配则弹出栈顶元素，否则返回 false。在遍历结束后，如果栈为空，则说明所有括号都正确闭合。

class Solution {
public:
    bool isValid(string s) {
        vector<char> st;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
                st.emplace_back(s[i]);
            }else if(s[i] == ')'){
                if(!st.empty() && st.back() == '(') {
                    st.pop_back();
                }else {
                    return false;
                }
            }else if(s[i] == ']') {
                if(!st.empty() && st.back() == '[') {
                    st.pop_back();
                }else {
                    return false;
                }
            }else if(s[i] == '}') {
                if(!st.empty() && st.back() == '{') {
                    st.pop_back();
                }else {
                    return false;
                }
            }
        }
        return st.size() == 0;
    }
};
你认为这篇文章怎么样？
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.8