首页 > 编程语言 >代码随想录算法训练营day10| 232.用栈实现队列 225. 用队列实现栈 20. 有效的括号 1047. 删除字符串中的所有相邻重复项

代码随想录算法训练营day10| 232.用栈实现队列 225. 用队列实现栈 20. 有效的括号 1047. 删除字符串中的所有相邻重复项

时间:2024-10-09 22:14:59浏览次数:7  
标签:20 队列 self 随想录 括号 obj return stack def

学习资料:https://programmercarl.com/栈与队列理论基础.html

栈与队列

学习记录:
232.用栈实现队列(两个栈(stack_in, stack_out)实现一个队列的行为)

点击查看代码
class MyQueue(object):

    def __init__(self):
        self.stack_in = []
        self.stack_out = []


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack_in.append(x)
        


    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        if self.stack_out:
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()



    def peek(self):
        """
        :rtype: int
        """
        ans = self.pop()
        self.stack_out.append(ans)
        return ans


    def empty(self):
        """
        :rtype: bool
        """
        return not (self.stack_in or self.stack_out)



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

225.用队列实现栈(一个两端队列deque实现栈的行为)

点击查看代码
class MyStack(object):

    def __init__(self):
        self.que = deque()


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.que.append(x)


    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        for i in range(len(self.que)-1):
            self.que.append(self.que.popleft())
        return self.que.popleft()


    def top(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        return self.que[-1]


    def empty(self):
        """
        :rtype: bool
        """
        return not self.que



# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

20.有效的括号(栈行为的应用:消消乐;左括号取反存入栈;右括号与栈中右括号消除;有三种错误括号形式(左括号多了;右括号多了;左右括号不匹配,如'{(})'))

点击查看代码
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for item in s:
            # 当出现左括号时,变成对应的右括号放到栈里
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            # 当还未遍历完栈就为空,或者当前括号与栈顶元素不同时,都是错的
            elif not stack or stack[-1] != item:   # 要先判断栈为空的情况
                return False
            # 排除2、3种错误情况后,当前括号与栈顶元素一致,消除此栈顶元素
            else:
                stack.pop()
        # 排除第1种错误,遍历完后如果栈中还有元素则错
        if not stack:
            return True
        else:
            return False
            

1047.删除字符串中的所有相邻重复项(消消乐,两两消除;逻辑:如果栈不为空且遍历值等于栈顶元素,则消除,其余情况都把遍历值添加到栈中)

点击查看代码
class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []      # 用list模拟栈的行为
        for item in s:
            # 如果栈有元素且栈顶元素等于该遍历值,则消除
            if stack and stack[-1]==item:
                stack.pop()
            # 如果栈之前没有元素或者元素不等于该遍历值,则添加
            else:
                stack.append(item)
        return ''.join(stack)

PS:前两道题栈与队列相互实现操作的类,还有点迷糊,多刷
今天吃了酸汤云吞全家福美味,特别是香菇马蹄和紫菜馅儿的~
面试不顺啊,国企又礼貌又犀利

标签:20,队列,self,随想录,括号,obj,return,stack,def
From: https://www.cnblogs.com/tristan241001/p/18455269

相关文章

  • 20222426 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    学号202224262024-2025-1《网络与系统攻防技术》实验一实验报告1.实验内容1.1NOP,JNE,JE,JMP,CMP汇编指令的机器码:1.1.1NOP(NoOperation)功能:NOP指令是一条空操作指令,它不做任何事情。执行NOP指令时,处理器的状态(如寄存器值、内存内容等)不会发生变化,只是简单地消耗了一......
  • 20222401 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    1.实验内容本次实验是关于缓冲区溢出攻击的,主要的学习内容如下:1.基本Linux命令objdump:将代码段反汇编,在这次实验中主要是用来找地址的。xxd:实现十六进制与二进制的转换,在这次实验的过程中,主要是有两个地方用到了这个命令。一是在打开文件后进行转换,而是以十六进制打开文件,保证......
  • codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报
    解题历程:看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后......
  • 【笔记】杂题选讲 2024.10.5(DNF)
    十一杂题选讲-VirtualJudge(vjudge.net)/mnt/e/codes/contests/20241008/sol.md目录[AGC004F]Namori[1406E]DeletingNumbers[1081G]MergesortStrikesBack[1033E]HiddenBipartiteGraph[1254E]SendTreetoCharlie[1012E]Cyclesort[1284F]NewYearandSocialN......
  • 2024.10.9 LGJ Round
    B对于所有\(x\in[0,n],y\in[0,m]\),求执行\(x\getsx+y,y\getsx+y\)若干次后满足\(x=k\)的双元组个数。这个题充分体现我的唐氏。具体地枚举\(x,y\)分别被算了多少次,系数是斐波那契数列,所以项数很少。然后转化为求\(k_1x+k_2y=k\)的方案数,这个我非常唐不会求。只需......
  • 2024自动化保研经验分享(西工成电北邮北航西交复旦计算所自所等等)
            具体的保研黑话、保研流程及注意事项就不说了哈,知乎上有很多大佬的分享非常细致,我就说说我参加的几个夏令营和预推免的具体情况及注意事项一、个人基本情况先上个人基本情况院校:某顶2专业:自动化rk:7%-10%(菜狗,很多院筛都过不了英语:刚过(悲伤竞赛:数模水赛省......
  • 2020年华为杯数学建模竞赛C题论文和代码
    面向康复工程的脑电信号分析和判别模型    摘          要:脑电信号的识别和分类是脑机接口技术中非常重要的一环,使用者无需通过复杂训练就可以获得较高的识别准确率,具有稳定的锁时性和高时间精度特性。本文使用基于监督学习的随机森林,SVM算法,半监督学习S3VM......
  • 2020年华为杯数学建模竞赛D题论文和代码
    无人机集群协同对抗摘          要:本文针对非线性约束条件下红蓝双方无人机集群协同对抗的最优规划问题,结合贪婪队形、非线性规划、内点法、蒙特卡洛方法和全联立正交配置有限元法,构建了无人机集群协同对抗推演模型。针对问题一,构建了基于蒙特卡洛法的蓝方突防......
  • 2024/9/30 日 日志
    今天下午进行了国庆假期前的小测。我们需要界面化生成30道四则运算题。在此次测试中,我原打算模仿迷宫游戏的格式将题目尽数输出。但在简化过程多层循环时遇到了问题ij的位置当然可变,但无法保证时在一行中输出不同的题目。加之频繁调整位置让过程变得复杂。以下是滑轮完成。C......
  • 2024/10/8日 日志
    在今天我对之前的小测内容进行了更新和对之前的想法进行了实现,改变了界面化的形式。Count.java点击查看代码importjava.util.ArrayList;importjava.util.Random;publicclassCount{ArrayList<Integer>number1=newArrayList<>();ArrayList<Integer>number2......