代码随想录刷题笔记(DAY 10)

今日总结:快要期末考试了,现在在疯狂速成,今天稍微缓和了一点,应该能保证继续每天刷题,欠下的那些寒假补上。

Day 10

01. 用栈实现队列(No. 232)

题目链接

代码随想录题解

1.1 题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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:

输入:
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]

解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示:

  • 1 <= x <= 9
  • 最多调用 100pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)
1.2 笔记

非常经典的题目,考察了对这两个数据结构的理解。栈实现了“先进后出”而队列则是“先进先出”,所以如果我们想要借助栈来实现队列的话,很容易就想到我们在输出的时候将栈中的数据反转即可,那反转如何实现呢?

这就需要用到两个栈:

在这里插入图片描述

即将 Stack1 视作一个 中转站,当我们需要输出的时候,就将 Stack1 中的元素 pop()Stack2 中,然后从 Stack2 中取元素。

注意 push() 的时候要判断 Stack2 是否为空,如果不为空就会出现顺序问题,因为此时的 Stack2 中即将弹出的第一个元素是我们构造的队列的第一个元素,如果我们在 Stack2 还未空的时候就 push() 新元素进来,就打破了确定的顺序。

1.3 代码
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;

    public MyQueue() {
        // 初始化
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        // 每次放入新元素的时候都暂存到 s1
        s1.push(x);
    }

    public int pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        // 判断 s2 是否为空
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

02. 用队列实现栈

题目链接

代码随想录题解

2.1 题目

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

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

注意:

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

示例:

输入:
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示:

  • 1 <= x <= 9
  • 最多调用100pushpoptopempty
  • 每次调用 poptop 都保证栈不为空
2.2 笔记

有了上面那道题的经验,很多朋友拿到这道题就想着想上面那道题一样倒过来就行了,那怎样倒过来呢?

简单,在创建一个队列然后从第一个队列推入就行了。

但是提交发现题目还是错了,这是为什么呢?

队列是先进先出的数据结构,我们把一个队列一个个取出放入另一个队列,顺序是不会改变的,就像正数乘以一个整数还是整数,栈能够倒置原因就是它是先进后出,负数乘以负数结果就是正数,这样类比起来就比较好理解。

这道题目可以使用一个队列来实现,队列的队尾元素是栈的栈顶元素:

那如果想要删除这个队尾的元素,我们可以从队头开始遍历,然后将队头的元素依次放到队尾,直到最开始的队尾元素(栈顶)是队列的队头的时候停止,也就是需要遍历 size - 1 次,这时候将队头元素弹出得到的就是需要的元素了。

那如何获取队尾元素呢?

我们可以按照上面的方法循环 size- 1 然后得到队头的元素但不删除。但其实我们可以设置一个变量 lastNum 当我们需要队尾元素的时候就直接将这个返回。

如果没有删除元素的话那这个 lastNum 的值就很好确定,我们每次 add() 添加新元素的时候就将 lastNum 重置为这个值即可,那如果执行了删除的话,这时候原本的倒数第二个元素就成了新的 lastNum 我们只需要在遍历到倒数第二个元素的时候将其赋值即可。

2.3 代码
class MyStack {
    Queue<Integer> q1;
    int lastNum; // 记录最后一个元素的值

    public MyStack() {
        q1 = new ArrayDeque<>();
    }

    public void push(int x) {
        q1.add(x);
        lastNum = x;
    }

    public int pop() {
        int size = q1.size();
        size = size - 1;
        while (size-- > 0) {
            int temp = q1.remove(); // 记录此时弹出的元素
            q1.add(temp);
            // 当循环结束的时候就将其赋值成倒数第二个元素了,其实等价于 if (size == 0) {lastNum = temp; }
            lastNum = temp; 
        }
        return q1.remove();
    }

    public int top() {
        return lastNum;
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/311802.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【JAVA基础】JVM之类加载--双亲委派机制

目录 1. 类加载的过程描述&#xff1a;看图&#xff1a;解释&#xff1a; 2. 那么类加载器都有哪些呢3. 双亲委派机制3.1 双亲委派机制的过程3.2 图看委派过程3.3 为什么要设计双亲委派机制 4. 自定义类加载器4.1 如何定义自己的类加载器&#xff1f; 1. 类加载的过程 描述&am…

YOLOv8 + openVINO 多线程数据读写顺序处理

多线程数据读写顺序处理 一个典型的生产者-消费者模型&#xff0c;在这个模型中&#xff0c;多个工作线程并行处理从共享队列中获取的数据&#xff0c;并将处理结果以保持原始顺序的方式放入另一个队列。 多线程处理模型&#xff0c;具体细节如下&#xff1a; 1.数据:数据里必…

Java学习,一文掌握Java之SpringBoot框架学习文集(4)

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…

GBASE南大通用SQL API 中的 SQL

ESQL 产品为GBASE南大通用数据库 GBase 8s SQL API&#xff08;应用程序编程接口&#xff09;。 GBase 为 C 编程语言产生 SQL API。 下图展示 SQL API 产品如何工作。您编写您在其中将 SQL 语句处理作为可执行代码的源 程序。嵌入式 SQL 预处理器处理您的源程序&#xff0c;它…

【QML COOK】- 008-自定义属性

前面介绍了用C定义QML类型&#xff0c;通常在使用Qt Quick开发项目时&#xff0c;C定义后端数据类型&#xff0c;前端则完全使用QML实现。而QML类型或Qt Quick中的类型时不免需要为对象增加一些属性&#xff0c;本篇就来介绍如何自定义属性。 1. 创建项目&#xff0c;并编辑Ma…

Qt 6之六:Qt Designer介绍

Qt 6之六&#xff1a;Qt Designer介绍 Qt Designer是一个可视化的用户界面设计工具&#xff0c;用于创建Qt应用程序的用户界面&#xff0c;允许开发人员通过拖放和布局来设计和创建GUI界面。 Qt 6之一&#xff1a;简介、安装与简单使用 https://blog.csdn.net/cnds123/articl…

作用域与作用域链

作用域与作用域链 一、什么是作用域 作用域就是一个独立的代码区域&#xff0c;域内的变量不会暴露到外部&#xff0c;外部无法访问&#xff0c;也就是说具有隔离性。 function outFun() {var inVariable "内层变量2"; } outFun(); // inVariable 的作用域仅在函…

matlab绘图修改坐标轴数字字体大小及坐标轴自定义间隔设置

一、背景 在matlab使用plot函数绘图后&#xff0c;生成的图片坐标轴数字字体大小及间隔可能并不符合我们的要求&#xff0c;因此需要自定义修改&#xff0c;具体方法如下 二、修改坐标轴数字字体大小 只需添加以下命令即可&#xff1a; set(gca,FontName,Times New Roman,F…

echarts -- 柱状图之柱状条如何显示白色侧阴影且鼠标移入时高亮

有个图表是要求柱状条的右下侧显示一个白色的侧阴影&#xff0c;一直没找到合适的方法&#xff0c; 加border或者shadowColor都达不到需求的效果。 因为柱状图 中series里可以包含多组数据&#xff0c;有几组就代表一个系列中有几个数据。这就代表series里要写七组数据。 对于上…

你了解计算机网络的发展历史吗?

1.什么是计算机网络 计算机网络是指将一群具有独立功能的计算机通过通信设备以及传输媒体被互联起来的&#xff0c;在通信软件的支持下&#xff0c;实现计算机间资源共享、信息交换或协同工作的系统。计算机网络是计算机技术与通信技术紧密结合的产物&#xff0c;两者的迅速发展…

电阻如何读取阻值

前言&#xff1a;大家经常见到的贴片电阻上的丝印有纯数字、数字与R组合、数字与除R之外的字母组合的&#xff0c;但大家知不知道这样的标注与贴片电阻的i精度相关&#xff1f;同一个阻值因为精度不同&#xff0c;标注也会不同。例如封装为0805的贴片电阻&#xff0c;丝印473和…

STL-list的使用简介

目录 ​编辑 一、list的底层实现是带头双向循环链表 二、list的使用 1、4种构造函数&#xff08;与vector类似&#xff09;​编辑 2、迭代器iterator 3、容量&#xff08;capicity&#xff09;操作 4、element access 元素获取 5、增删查改 list modifiers 6、list的迭…

【计算机组成原理】-指令系统

&#x1f3b5;1.指令的发展 &#x1f308;1.1基础概念 计算机的程序是由一系列的机器指令组成的。指令就是要计算机执行某种操作的命令。从计算机的层次结构来说&#xff0c;有微指令&#xff0c;机器指令和宏指令之分。微程序中用到微指令&#xff0c;属于硬件&#xff0c;而…

Fluids —— MicroSolvers DOP

目录 Gas SubStep —— 重复执行对应的子步 Switch Solver —— 切换解算器 Gas Attribute Swap —— 交换、复制或移动几何体属性 Gas Intermittent Solve —— 固定时间间隔计算子解算器 Gas External Forces —— 计算外部力并更新速度或速度场 Gas Particle Separate…

D3121是什么?主要有哪些特点呢?为什么可以应用在车载音响系统上

D3121 是一块对地能动冲放大器集成电路&#xff0c;该电路能有效消除由线 路电阻所引起的问题及噪声。所需外围电容小&#xff0c;便于设计时小型化的同 时可靠性不降低。广泛应用于车载音响系统内。 D3121 系列采用 DIP8 、 SOP8 、 SIP8 的封装形式封装。 主要特点&#…

面试算法115:重建序列

题目 长度为n的数组org是数字1&#xff5e;n的一个排列&#xff0c;seqs是若干序列&#xff0c;请判断数组org是否为可以由seqs重建的唯一序列。重建的序列是指seqs所有序列的最短公共超序列&#xff0c;即seqs中的任意序列都是该序列的子序列。 例如&#xff0c;如果数组org为…

python绘制热力图-数据处理-VOC数据类别标签分布及数量统计(附代码)

前言 当你需要统计训练数据中每个类别标签有多少&#xff0c;并且想知道坐标中心分布在图像的位置信息时&#xff0c;你可以利用一下脚本进行计算&#xff01; 步骤 要绘制热力图来分析VOC数据的分布统计&#xff0c;可以按照以下步骤进行&#xff1a; 数据处理&#xff1…

移动通信系统关键技术多址接入MIMO学习(8)

1.Multiple-antenna Techniques多天线技术MIMO&#xff0c;从SISO到SIMO到MISO到如今的MIMO&#xff1b; 2.SIMO单发多收&#xff0c;分为选择合并、增益合并&#xff1b;SIMO&#xff0c;基站通过两路路径将信号发送到终端&#xff0c;因为终端接收到的两路信号都是来自同一天…

计算机速成课Crash Course - 18. 操作系统

今天继续计算机速成课Crash Course的系列讲解。 更多技术文章&#xff0c;全网首发公众号 “摸鱼IT” 锁定 -上午11点 - &#xff0c;感谢大家关注、转发、点赞&#xff01; 计算机速成课Crash Course - 17. 集成电路&摩尔定律 18. 操作系统 1940,1950 年代的电脑&#…

rime中州韵小狼毫 词组注释 滤镜

在rime中州韵小狼毫 联想词组 滤镜一文中&#xff0c;我们通过Filter滤镜功能配置了联想词组的功能&#xff0c;这使得我们在输入一些关键词汇时&#xff0c;可以联想补充一些附加的词组&#xff0c;例如我输入“手机”&#xff0c;就可以联想补充对应的手机号&#xff0c;如下…