• 代码随想录笔记--栈与队列篇

    目录

    1--用栈实现队列

    2--用队列实现栈

    3--有效的括号

    4--删除字符串中的所有相邻重复项

    5--逆波兰表达式求值

    6--滑动窗口的最大值

    7--前k个高频元素

    1--用栈实现队列

    利用两个栈，一个是输入栈，另一个是输出栈；

    1. #include 
    2. #include 
    3.  
    4. class MyQueue {
    5. public:
    6.     MyQueue() {}
    7.     
    8.     void push(int x) {
    9.         in_stk.push(x);
    10.     }
    11.     
    12.     int pop() {
    13.         if(out_stk.empty()){
    14.             while(!in_stk.empty()){
    15.                 out_stk.push(in_stk.top());
    16.                 in_stk.pop();
    17.             }
    18.         }
    19.         int tmp = out_stk.top();
    20.         out_stk.pop();
    21.         return tmp;
    22.     }
    23.     
    24.     int peek() {
    25.         if(out_stk.empty()){
    26.             while(!in_stk.empty()){
    27.                 out_stk.push(in_stk.top());
    28.                 in_stk.pop();
    29.             }
    30.         }
    31.         return out_stk.top();
    32.     }
    33.     
    34.     bool empty() {
    35.         if(out_stk.empty() && in_stk.empty()) return true;
    36.         else return false;
    37.     }
    38. private:
    39.     std::stack<int> in_stk, out_stk;
    40. };
    41.  
    42. int main(int argc, char* argv[]){
    43.     MyQueue Queue;
    44.     Queue.push(1);
    45.     Queue.push(2);
    46.     Queue.push(3);
    47.     std::cout << Queue.pop() << std::endl;
    48.     std::cout << Queue.peek() << std::endl;
    49.  
    50.     return 0;
    51. }

    2--用队列实现栈

    主要思路：

            弹出栈顶元素时，需要将队列前 size - 1 个元素先弹出再重新加入到队列中；

    1. #include 
    2. #include 
    3.  
    4. class MyStack {
    5. public:
    6.     MyStack() {}
    7.     
    8.     void push(int x) {
    9.         q.push(x);
    10.     }
    11.     
    12.     int pop() {
    13.         int size = q.size();
    14.         for(int i = 1; i <= size - 1; i++){
    15.             q.push(q.front());
    16.             q.pop();
    17.         }
    18.         int tmp = q.front();
    19.         q.pop();
    20.         return tmp;
    21.     }
    22.     
    23.     int top() {
    24.         int size = q.size();
    25.         for(int i = 1; i <= size - 1; i++){
    26.             q.push(q.front());
    27.             q.pop();
    28.         }
    29.         int tmp = q.front();
    30.         q.pop();
    31.         q.push(tmp);
    32.         return tmp;
    33.     }
    34.     
    35.     bool empty() {
    36.         return q.empty();
    37.     }
    38. private:
    39.     std::queue<int> q;
    40. };
    41.  
    42. int main(int argc, char* argv[]){
    43.     MyStack stk;
    44.     stk.push(1);
    45.     stk.push(2);
    46.     stk.push(3);
    47.     std::cout << stk.pop() << std::endl;
    48.     std::cout << stk.top() << std::endl;
    49.     return 0;
    50. }

    3--有效的括号

    主要思路：

            基于栈，遇到左括号，入栈对应的右括号。遇到右括号，判断当前栈顶元素是否与右括号相等，相等则表示之前曾遇到对应的左括号，表明匹配成功并弹出栈顶元素，否则返回 false；

            最后判断栈是否为空，即是否有未匹配的左括号；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     bool isValid(std::string s) {
    8.         std::stack<char> stk;
    9.         for(int i = 0; i < s.length(); i++){
    10.             if(s[i] == '(') stk.push(')');
    11.             else if(s[i] == '[') stk.push(']');
    12.             else if(s[i] == '{') stk.push('}');
    13.             else{
    14.                 if(stk.empty()) return false;
    15.                 else if(stk.top() != s[i]) return false;
    16.                 else stk.pop(); // 匹配
    17.             }
    18.         }
    19.         return stk.empty();
    20.     }
    21. };
    22.  
    23. int main(int argc, char* argv[]){
    24.     std::string test = "()[]{}";
    25.     Solution S1;
    26.     bool res = S1.isValid(test);
    27.     if(res) std::cout << "true" << std::endl;
    28.     else std::cout << "false" << std::endl;
    29.     return 0;
    30. }

    4--删除字符串中的所有相邻重复项

    主要思路：

            基于栈，遍历字符串，判断当前字符与栈顶元素是否相同，相同则弹出栈顶元素，否则入栈；

            最后遍历栈，将栈内的元素重构为字符串，需注意顺序；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::string removeDuplicates(std::string s) {
    8.         std::stack<char> stk;
    9.         for(int i = 0; i < s.length(); i++){
    10.             if(stk.empty() || stk.top() != s[i]){
    11.                 stk.push(s[i]);
    12.             }
    13.             else{ // s[i] == stk.top()
    14.                 stk.pop();
    15.             }
    16.         }
    17.         std::string res;
    18.         while(!stk.empty()){
    19.             res = stk.top() + res;
    20.             stk.pop();
    21.         }
    22.         return res;
    23.     }
    24. };
    25.  
    26. int main(int argc, char* argv[]){
    27.     std::string test = "abbaca";
    28.     Solution S1;
    29.     std::string res = S1.removeDuplicates(test);
    30.     std::cout << res << std::endl;
    31.     return 0;
    32. }

    5--逆波兰表达式求值

    主要思路：

            基于栈，遍历字符串数组，当遇到数字时将数字压入栈中，当遇到运算符时，将栈顶的两个元素取出来进行运算，并将运算结果重新压入栈中；

            需注意运算顺序，即第二个出栈的 num2 作为运算符的左侧元素；

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. class Solution {
    7. public:
    8.     int evalRPN(std::vector& tokens) {
    9.         std::stack<int> stk;
    10.         for(int i = 0; i < tokens.size(); i++){
    11.             if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){
    12.                 stk.push(std::stoi(tokens[i]));
    13.                 continue;
    14.             }
    15.             int num1 = stk.top();
    16.             stk.pop();
    17.             int num2 = stk.top();
    18.             stk.pop();
    19.             if(tokens[i] == "+"){  
    20.                 int num3 = num2 + num1;
    21.                 stk.push(num3);
    22.                 continue;
    23.             }
    24.             else if(tokens[i] == "-"){
    25.                 int num3 = num2 - num1;
    26.                 stk.push(num3);
    27.                 continue;
    28.             }
    29.             else if(tokens[i] == "*"){
    30.                 int num3 = num2 * num1;
    31.                 stk.push(num3);
    32.                 continue;                
    33.             }
    34.             else{
    35.                 int num3 = num2 / num1;
    36.                 stk.push(num3);
    37.                 continue;
    38.             }
    39.         }
    40.         return stk.top();
    41.     }
    42. };
    43.  
    44. int main(int argc, char* argv[]){
    45.     // tokens = ["2","1","+","3","*"]
    46.     std::vector test = {"2", "1", "+", "3", "*"};
    47.     Solution S1;
    48.     int res = S1.evalRPN(test);
    49.     std::cout << res << std::endl;
    50.     return 0;
    51. }

    6--滑动窗口的最大值

    主要思路：

            维护一个双端队列，队列里的元素存储的是可能成为最大值的元素，对于当前滑动窗口，其最大值为队头元素；

            当移动滑动窗口时，需要判断当前移出窗口的元素是否是队头元素，如果是则需先将队头元素弹出（因为该元素已经离开了滑动窗口，相当于失效）；

            之前本题的解法是存储元素的索引（之前的解法），这样可以避免重复元素的出现；但现在本题的解法是存储元素，所以一个细节是需要避免错误移除重复元素的问题，具体可以推导例子：[-7,-8,7,5,7,1,6,0]；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    8.         std::deque<int> q; // 存储可能成为最大值的元素
    9.         std::vector<int> res;
    10.         // 初始化第一个滑动窗口
    11.         for(int i = 0; i < k; i++){
    12.             // 不能取等于号的原因是可能会出现相等的数，例如下例
    13.             // [-7,-8,7,5,7,1,6,0] 出现了两个7，取=号会误弹出第2个7
    14.             while(!q.empty() && q.back() < nums[i]){
    15.                 q.pop_back();
    16.             }
    17.             q.push_back(nums[i]);
    18.         }
    19.         res.push_back(q.front());
    20.         // 遍历更新
    21.         for(int i = k; i < nums.size(); i++){
    22.             // 移除滑动窗口左边界的元素
    23.             if(nums[i-k] == q.front()) q.pop_front();
    24.             // 把不可能成为最大值的元素从队列中移出
    25.             while(!q.empty() && q.back() < nums[i]){
    26.                 q.pop_back();
    27.             }
    28.             q.push_back(nums[i]);
    29.             res.push_back(q.front()); // 记录当前滑动窗口的最大值
    30.         }
    31.         return res;
    32.     }
    33. };
    34.  
    35. int main(int argc, char* argv[]){
    36.     std::vector<int> test = {1, 3, -1, -3, 5, 3, 6, 7};
    37.     int k = 3;
    38.     Solution S1;
    39.     std::vector<int> res = S1.maxSlidingWindow(test, k);
    40.     for(auto v : res) std::cout << v << " ";
    41.     std::cout << std::endl;
    42.     return 0;
    43. }

    7--前k个高频元素

    主要思路：

            维护一个优先队列（小顶堆），里面存储 k 个元素及其出现的次数；

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. class Solution {
    7. public:
    8.     std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
    9.         std::map<int, int> m;
    10.         for(int i = 0; i < nums.size(); i++){
    11.             m[nums[i]] += 1;
    12.         }
    13.  
    14.         // 小顶堆
    15.         std::priority_queueint, int>, std::vectorint, int>>, mycompare> pri_q;
    16.         for(auto it = m.begin(); it != m.end(); it++){
    17.             pri_q.emplace(*it);
    18.             if(pri_q.size() > k) pri_q.pop(); // 始终维护 k 个 pair 对
    19.         }
    20.  
    21.         // 倒叙输出k个高频元素
    22.         std::vector<int> res(pri_q.size(), 0);
    23.         for(int i = pri_q.size() - 1; i>=0; i--){
    24.             res[i] = pri_q.top().first;
    25.             pri_q.pop();
    26.         }
    27.         return res;
    28.     }
    29.  
    30.     class mycompare{
    31.     public:
    32.         bool operator()(std::pair<int, int>& item1, std::pair<int, int>& item2){
    33.             return item1.second > item2.second;
    34.         }
    35.     };
    36. };
    37.  
    38. int main(int argc, char* argv[]){
    39.     // nums = [1,1,1,2,2,3], k = 2
    40.     std::vector<int> test = {1, 1, 1, 2, 2, 3};
    41.     int k = 2;
    42.     Solution S1;
    43.     std::vector<int> res = S1.topKFrequent(test, k);
    44.     for(auto item : res) std::cout << item << " ";
    45.     std::cout << std::endl;
    46.     return 0;
    47. }

  • 相关阅读:
    Spring之BeanFactory
    自定义注解打印日志与耗时
    仓库管理系统到底是什么？有必要专门买一个吗？
    Linux无文件木马程序渗透测试复现
    Vue教学19：Element UI组件深入探索，构建精致的Vue应用界面
    STM32F103学习笔记（六） RTC实时时钟（应用篇）
    8-事件组或标志
    人工智能第2版学习——博弈中的搜索2
    机器学习数据挖掘十大经典算法 数学建模常用算法
    抖音seo源码--开源，支持二开不加密
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/132626708