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

这篇具有很好参考价值的文章主要介绍了代码随想录笔记--栈与队列篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1--用栈实现队列

2--用队列实现栈

3--有效的括号

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

5--逆波兰表达式求值

6--滑动窗口的最大值

7--前k个高频元素


1--用栈实现队列

代码随想录笔记--栈与队列篇,数据结构&LeetCode,数据结构

利用两个栈,一个是输入栈,另一个是输出栈

#include <iostream>
#include <stack>

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x) {
        in_stk.push(x);
    }
    
    int pop() {
        if(out_stk.empty()){
            while(!in_stk.empty()){
                out_stk.push(in_stk.top());
                in_stk.pop();
            }
        }
        int tmp = out_stk.top();
        out_stk.pop();
        return tmp;
    }
    
    int peek() {
        if(out_stk.empty()){
            while(!in_stk.empty()){
                out_stk.push(in_stk.top());
                in_stk.pop();
            }
        }
        return out_stk.top();
    }
    
    bool empty() {
        if(out_stk.empty() && in_stk.empty()) return true;
        else return false;
    }
private:
    std::stack<int> in_stk, out_stk;
};

int main(int argc, char* argv[]){
    MyQueue Queue;
    Queue.push(1);
    Queue.push(2);
    Queue.push(3);
    std::cout << Queue.pop() << std::endl;
    std::cout << Queue.peek() << std::endl;

    return 0;
}

2--用队列实现栈

代码随想录笔记--栈与队列篇,数据结构&amp;LeetCode,数据结构

主要思路:

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

#include <iostream>
#include <queue>

class MyStack {
public:
    MyStack() {}
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        for(int i = 1; i <= size - 1; i++){
            q.push(q.front());
            q.pop();
        }
        int tmp = q.front();
        q.pop();
        return tmp;
    }
    
    int top() {
        int size = q.size();
        for(int i = 1; i <= size - 1; i++){
            q.push(q.front());
            q.pop();
        }
        int tmp = q.front();
        q.pop();
        q.push(tmp);
        return tmp;
    }
    
    bool empty() {
        return q.empty();
    }
private:
    std::queue<int> q;
};

int main(int argc, char* argv[]){
    MyStack stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);
    std::cout << stk.pop() << std::endl;
    std::cout << stk.top() << std::endl;
    return 0;
}

3--有效的括号

代码随想录笔记--栈与队列篇,数据结构&amp;LeetCode,数据结构

主要思路:

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

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

#include <iostream>
#include <stack>
#include <string>

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> stk;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '(') stk.push(')');
            else if(s[i] == '[') stk.push(']');
            else if(s[i] == '{') stk.push('}');
            else{
                if(stk.empty()) return false;
                else if(stk.top() != s[i]) return false;
                else stk.pop(); // 匹配
            }
        }
        return stk.empty();
    }
};

int main(int argc, char* argv[]){
    std::string test = "()[]{}";
    Solution S1;
    bool res = S1.isValid(test);
    if(res) std::cout << "true" << std::endl;
    else std::cout << "false" << std::endl;
    return 0;
}

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

代码随想录笔记--栈与队列篇,数据结构&amp;LeetCode,数据结构

主要思路:

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

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

#include <iostream>
#include <stack>
#include <string>

class Solution {
public:
    std::string removeDuplicates(std::string s) {
        std::stack<char> stk;
        for(int i = 0; i < s.length(); i++){
            if(stk.empty() || stk.top() != s[i]){
                stk.push(s[i]);
            }
            else{ // s[i] == stk.top()
                stk.pop();
            }
        }
        std::string res;
        while(!stk.empty()){
            res = stk.top() + res;
            stk.pop();
        }
        return res;
    }
};

int main(int argc, char* argv[]){
    std::string test = "abbaca";
    Solution S1;
    std::string res = S1.removeDuplicates(test);
    std::cout << res << std::endl;
    return 0;
}

5--逆波兰表达式求值

代码随想录笔记--栈与队列篇,数据结构&amp;LeetCode,数据结构

主要思路:

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

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

#include <iostream>
#include <vector>
#include <stack>
#include <string>

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

int main(int argc, char* argv[]){
    // tokens = ["2","1","+","3","*"]
    std::vector<std::string> test = {"2", "1", "+", "3", "*"};
    Solution S1;
    int res = S1.evalRPN(test);
    std::cout << res << std::endl;
    return 0;
}

6--滑动窗口的最大值

代码随想录笔记--栈与队列篇,数据结构&amp;LeetCode,数据结构

主要思路:

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

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

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

#include <iostream>
#include <vector>
#include <queue>

class Solution {
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        std::deque<int> q; // 存储可能成为最大值的元素
        std::vector<int> res;
        // 初始化第一个滑动窗口
        for(int i = 0; i < k; i++){
            // 不能取等于号的原因是可能会出现相等的数,例如下例
            // [-7,-8,7,5,7,1,6,0] 出现了两个7,取=号会误弹出第2个7
            while(!q.empty() && q.back() < nums[i]){
                q.pop_back();
            }
            q.push_back(nums[i]);
        }
        res.push_back(q.front());
        // 遍历更新
        for(int i = k; i < nums.size(); i++){
            // 移除滑动窗口左边界的元素
            if(nums[i-k] == q.front()) q.pop_front();
            // 把不可能成为最大值的元素从队列中移出
            while(!q.empty() && q.back() < nums[i]){
                q.pop_back();
            }
            q.push_back(nums[i]);
            res.push_back(q.front()); // 记录当前滑动窗口的最大值
        }
        return res;
    }
};

int main(int argc, char* argv[]){
    std::vector<int> test = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    Solution S1;
    std::vector<int> res = S1.maxSlidingWindow(test, k);
    for(auto v : res) std::cout << v << " ";
    std::cout << std::endl;
    return 0;
}

7--前k个高频元素

代码随想录笔记--栈与队列篇,数据结构&amp;LeetCode,数据结构

主要思路:

        维护一个优先队列(小顶堆),里面存储 k 个元素及其出现的次数;文章来源地址https://www.toymoban.com/news/detail-690180.html

#include <iostream>
#include <vector>
#include <map>
#include <queue>

class Solution {
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::map<int, int> m;
        for(int i = 0; i < nums.size(); i++){
            m[nums[i]] += 1;
        }

        // 小顶堆
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, mycompare> pri_q;
        for(auto it = m.begin(); it != m.end(); it++){
            pri_q.emplace(*it);
            if(pri_q.size() > k) pri_q.pop(); // 始终维护 k 个 pair 对
        }

        // 倒叙输出k个高频元素
        std::vector<int> res(pri_q.size(), 0);
        for(int i = pri_q.size() - 1; i>=0; i--){
            res[i] = pri_q.top().first;
            pri_q.pop();
        }
        return res;
    }

    class mycompare{
    public:
        bool operator()(std::pair<int, int>& item1, std::pair<int, int>& item2){
            return item1.second > item2.second;
        }
    };
};

int main(int argc, char* argv[]){
    // nums = [1,1,1,2,2,3], k = 2
    std::vector<int> test = {1, 1, 1, 2, 2, 3};
    int k = 2;
    Solution S1;
    std::vector<int> res = S1.topKFrequent(test, k);
    for(auto item : res) std::cout << item << " ";
    std::cout << std::endl;
    return 0;
}

到了这里,关于代码随想录笔记--栈与队列篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第10天-代码随想录刷题训练-第五章 栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈

    栈和队列对应的三个不同的STL版本,底层实现方式不一样, 为我们所知道的是 SGI STL 栈 栈提供 pop和push等接口, 不提供走访功能 也不提供迭代器, 不像map和set可以使用迭代器遍历,往往不被归类为容器,而是容器适配器 栈的内部实现结构可以使用 verctor、list 和 deque(默认)

    2024年02月04日
    浏览(42)
  • 【代码随想录】刷题笔记Day43

    刚过完非常愉快的元旦假期,唔想反工啊啊啊,先刷刷题找回学习的状态吧 dp[target] == target为目标,weight和value相同的01背包问题,用一维遍历 dp[j]为容量为j的背包所能装的最大价值 dp[j] = max(dp[j], dp[j - num[i]] + nums[i]) 关键在于把两两相减问题转化为两堆近似相减,和上一题就

    2024年02月03日
    浏览(40)
  • 【代码随想录】刷题笔记Day49

    跑了个步吃了个饭洗了个澡以及和母上打了个电话,继续来刷题咯o(* ̄▽ ̄*)ブ 之前写过的,代码直接看【代码随想录】刷题笔记Day35-CSDN博客 一维和贪心的思路其实大差不差,本质还是上升就卖,不上升保留之前的利润 和上一题基本一样,唯一不同是可以买卖多次, dp[i]

    2024年01月21日
    浏览(56)
  • 【代码随想录】刷题笔记Day54

    差单调栈就结束代码随想录一刷啦,回家二刷打算改用python补充进博客,小涛加油!!! 中心点外扩,注意中心点可能有一个元素可能有两个元素 dp数组含义 dp[i][j]:表示区间范围[i,j] (左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false 递推公式 s[i]与s[j

    2024年01月23日
    浏览(53)
  • 代码随想录刷题笔记-Day21

    701. 二叉搜索树中的插入操作 https://leetcode.cn/problems/insert-into-a-binary-search-tree/ 给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。 注意,可能

    2024年02月22日
    浏览(51)
  • 代码随想录刷题笔记-Day20

    236. 二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深

    2024年02月21日
    浏览(51)
  • 代码随想录刷题笔记(DAY 10)

    今日总结:快要期末考试了,现在在疯狂速成,今天稍微缓和了一点,应该能保证继续每天刷题,欠下的那些寒假补上。 01. 用栈实现队列(No. 232) 题目链接 代码随想录题解 1.1 题目 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作( push 、 pop

    2024年01月23日
    浏览(50)
  • 动态规划01背包问题-代码随想录-刷题笔记

    有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品只能用一次 ,求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包 确定dp数组以及下标的含义 是使用二维数组,即 dp[i][j] 表示从下标为[0-i]的物品里任意取,

    2024年02月07日
    浏览(58)
  • 代码随想录阅读笔记-回溯【电话号码的字母组合】

    题目 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入:\\\"23\\\" 输出:[\\\"ad\\\", \\\"ae\\\", \\\"af\\\", \\\"bd\\\", \\\"be\\\", \\\"bf\\\", \\\"cd\\\", \\\"ce\\\", \\\"cf\\\"]. 说明:尽管上面的答案是按字典序排列的,但是你可以任意

    2024年04月13日
    浏览(58)
  • 【代码随想录python笔记整理】第十二课 · 位置互换

    前言: 本笔记仅仅只是对内容的整理和自行消化,并不是完整内容,如有侵权,联系立删。        这节我们讨论一个简单的问题——怎么交换两个变量的值。比如说,一个瓶子里是水,一个瓶子里是油,想要将两个瓶子中的东西互换,我们应该怎么做呢?要实现上述过程,

    2024年02月21日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包