栈和队列

232. 用栈实现队列

在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢?如果进栈和出栈都为空的话,说明模拟的队列为空了。

在代码实现的时候,会发现pop() 和 peek()两个函数功能类似,代码实现上也是类似的。

class MyQueue {
public:
    stack<int> stkIn;
    stack<int> stkOut;

    MyQueue() {

    }

    void push(int x) {
        stkIn.push(x);
    }

    int pop() {
        if(stkOut.empty()) {
            while(!stkIn.empty()) {
                stkOut.push(stkIn.top());
                stkIn.pop();
            }
        }
        int res = stkOut.top();
        stkOut.pop();
        return res;
    }

    int peek() {
        int res = this->pop();
        stkOut.push(res);
        return res;
    }

    bool empty() {
        return stkIn.empty() && stkOut.empty();
    }
};

225. 用队列实现栈

用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1

class MyStack {
public:

    queue<int> que1;
    queue<int> que2;  //备份用
    MyStack() {

    }

    void push(int x) {
        que1.push(x);
    }

    int pop() {
        int size = que1.size();
        while(!que1.empty()) {
            que2.push(que1.front());
            que1.pop();
        }
        while(size>1) {
            que1.push(que2.front());
            que2.pop();
            size--;
        }
        int res = que2.front();
        que2.pop();
        return res;
    }

    int top() {
        return que1.back();
    }

    bool empty() {
        return que1.empty();
    }
};

也可以一个队列就实现

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {

    }
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    /** Get the top element. */
    int top() {
        return que.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};

20. 有效的括号

遍历字符串,遇到[ 、{、 (则把对应的右括号入栈,否则就判断栈顶元素和当前遍历元素是否相等,相等弹出,不等返回错误。如果栈已经为空了,没有匹配的字符了,说明右括号没有找到对应的左括号 return false。

遍历结束后,栈不未空,就返回错误。

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> stk;
        for (char c : s)
        {
            if (c == '[')
            {
                stk.push(']');
            }
            else if (c == '(')
            {
                stk.push(')');
            }
            else if (c == '{')
            {
                stk.push('}');
            }
            else if (stk.empty() || stk.top() != c)
            {
                // 栈为空或者不匹配
                return false;
            }
            else
            {
                // st.top() 与 s[i]相等,栈弹出元素
                stk.pop();
            }
        }
        return stk.empty();
    }
};

1047. 删除字符串中的所有相邻重复项

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stk;
        string ans = "";
        for(char c: s) {
            if(stk.empty() || stk.top()!=c) {
                // 空或者不等
                stk.push(c);
            } else {
                stk.pop();
            }
        }
        // 得到结果
        while(!stk.empty()) {
            ans+=stk.top();
            stk.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

150. 逆波兰表达式求值

stringintstd::stoi()

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        for(string s: tokens) {
            if(s=="+" || s=="-" || s=="*" || s=="/") {
                int num1 = stk.top();
                stk.pop();
                int num2 = stk.top();
                stk.pop();
                if(s=="+") stk.push(num1+num2);
                if(s=="-") stk.push(num2-num1);
                if(s=="*") stk.push(num2*num1);
                if(s=="/") stk.push(num2/num1);
            } else {
                stk.push(stoi(s));
            }
        }
        int res = stk.top();
        return res;
    }
};

239. 滑动窗口最大值

参考:https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

  • 维护一个最大堆的方式,每次进行插入、删除、查找,就是O(log(k))+O(1),在外面是循环O(n),复杂度就是nlogk

  • 维护一个优先队列,保持最大值在队首

  • 维护一个单调队列,使用deque进行维护

    class Solution {
    public:
      vector maxSlidingWindow(vector& nums, int k) {
          deque que;
          vector ans;
          // 填充前k个
          for(int i=0; ique.back()) {
                  que.pop_back();
              }
              que.push_back(nums[i]);
          }
          ans.push_back(que.front());
          // 下面的
          for (int i=k;ique.back()) {
                  que.pop_back();
              }
              que.push_back(nums[i]);
    
              ans.push_back(que.front());
          }
          return ans;
      }
    };

347. 前 K 个高频元素

  • 基于堆

    class Solution {
    public:
      class comp{
          public:
              bool operator()(const pair & l,const pair & r) {
                  return l.second > r.second;
              }
      };
      vector topKFrequent(vector& nums, int k) {
          unordered_map map;
          for(int i:nums) map[i]++;
    
          // 定义小顶堆
          priority_queue, vector >, comp > que;
          for(auto it=map.begin(); it!=map.end(); it++) {
              que.push(*it);
              if (que.size()>k) que.pop();
          }
    
          // 找出前K个高频元素
          vector ans(k);
          while(k--) {
              ans[k] = que.top().first;
              que.pop();
          }
          return ans;
      }
    };
  • 快排

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇