Leetcode刷题记录——栈

Leetcode刷题记录——栈,第1张

大家好!一个重要的决定,我,和我的美女室友小章,以及辣妹会加拿大分会的小阳准备一起刷leetcode,弥补在上海逛五角场荒废掉的日子。

好了,说够了,可以开始了。

知识点
  • 栈是一种逻辑结构,特点是只能在一端进行 *** 作,元素先进后出。
常用方法
  • C++
    • push() 元素入栈
    • pop() 元素出栈
    • top() 读取栈顶元素
    • empty() 判断栈是否为空
  • python
    • append() :元素入栈
    • pop():元素出栈并返回
    • stack[-1]:返回栈顶元素

题目来源:剑指Offer

学习计划:30 in 30

「剑指 Offer」 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台

一、剑指 Offer 09. 用两个栈实现队列

1. C++版本 核心点
  • 一个栈作为输入输出栈,一个栈作为辅助栈。
  • 简化代码的关键点:如何减少元素在两个栈之间的交换次数。
小技巧

使用一个整型变量size,记录栈内的元素个数。判断栈是否为空的时候,用size==0是否成立来进行 *** 作。比调用empty()函数效率更高。

具体C++代码如下:

//c++版本
class CQueue {
public:
    stack stack1;  //定义两个栈stack1,stack2
    stack stack2;
    int size=0;        //用来记录逻辑上的队列的长度,即两个栈中所有元素的个数总和
    CQueue() {}
    
    void appendTail(int value) {  //需要在逻辑队尾添加元素,直接添加到栈1中
        stack1.push(value);
        size++;
    }
    
    int deleteHead() {  
        if(size==0)    //逻辑队列此时为空
        {
            return -1;
        }
        else
        {
            if(stack2.empty())   //辅助栈中元素已经全部输出
            {
                while(!stack1.empty())   //如果栈1中仍然有元素
                {
                    int tmp=stack1.top(); //将栈1中元素逐个输入到栈2中
                    stack1.pop();
                    stack2.push(tmp);
                }
            }
            size--;
            int res=stack2.top();
            stack2.pop();
            return res;
        }


    }
};
2. python版本 重点
  1. 理解栈与队列的存储、读取逻辑差异所在:先入后出与先入先出;
  2. 理解两栈首尾相接等于队列的逻辑合理性。
难点
  1. 理清何时将输入栈的元素压入输出栈,并用代码实现;
  2. 梳理完全 输入栈与输出栈 各自是否为空的几种情况,不要遗漏可能性,以致报错。
函数知识点
  • 出入栈:

入栈:stack.append() ;

出栈:stack.pop()【注意:pop方法不只是输出栈顶元素,而且会将其删除】

  • 关于python中的self:

1.  python中的self - 不妨不妨,来日方长 - 博客园

2. 一篇文章让你彻底搞清楚Python中self的含义 - jessonsh - 博客园

#python3版本

class CQueue:
    ## 定义两个栈,通过命名可直观知道一个实现输入功能,一个实现输出功能
    def __init__(self):
        self.stack_in=[]
        self.stack_out=[]

    ## 输入功能的实现很符合直觉理解,记住append()方法。
    def appendTail(self, value: int) -> None:
        self.stack_in.append(value)
  
    ## 输出要分三种情况分析:
    ## 1。输出栈B中非空;2。输出栈B为空,输入栈A非空;3。输出栈B与输入栈A均为空。
    
    def deleteHead(self) -> int:
        if self.stack_out : 
            return self.stack_out.pop()
        ## 1。直接从B中输出栈顶元素并删除,即pop()方法;
        
        elif self.stack_in :
            while self.stack_in :
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()
         ## 2。将A中元素全部压入输出栈B中。注意,这是从逆序转为顺序的关键。
         
        else : 
            return -1
        ## 3。返回-1

二、  剑指 Offer 30. 包含min函数的栈

1. C++版本 第一次尝试的错误思路及代码: 

最初的思路:用变量x记录当前的最小元素的值,此外并未采用任何结构记录最小值。

Bug:如果d出的元素是当前的最小值,那么在元素d出后,剩余元素中的最小值无法在O(1)的时间复杂度内找到。

正确的思路:设计辅助栈

辅助栈:栈中元素个数与当前输入栈的元素个数相同(非边界情况下),区别在于,辅助栈的每一个元素,都对应于输入栈中同等高度的当前最小元素。当需要输出最小元素时,同时输出辅助栈和输入栈中的栈顶元素。

关键点

考虑边界情况,当第一次输入元素时,此时尚未存在最小元素,如何确定辅助栈中栈顶元素?在初始化的时候,将int类型的最大值,放入到辅助栈中,作为边界条件。在执行代码时,第一个输入的元素会被记为当前最小的元素。

动图源于Leetcode网站官方题解(力扣

//c++版本
class MinStack {
public:
    /** initialize your data structure here. */
    //
    stack instack;
    stack minstack;   //辅助栈

    MinStack() {
        minstack.push(INT_MAX);  //将int类型的最大值放在辅助栈的栈底,作为边界条件
    }
    void push(int x) {
        int tmp=minstack.top();
        if(x
2.python版本 重点和难点

如何在O(1)时间复杂度内实现min函数

#python版本
class MinStack:

    def __init__(self):
        self.A , self.B = [] , []

    def push(self, x: int) -> None:
        self.A.append(x)
        ## 若栈B中为空,或者x比栈顶元素更小,就把x压入栈。
        ## 即,保证栈B的顶上元素为最小值。
        if not self.B or self.B[-1] >= x :
            self.B.append(x)

    def pop(self) -> None:
        ## 输出并删除栈A的栈顶元素的同时,进行判断:
        ## 若此元素为当前最小值(即B的栈顶元素),那么这边也需要同步删除!
        if self.A.pop() == self.B[-1] : 
            self.B.pop()

    def top(self) -> int:
        return self.A[-1]

    def min(self) -> int:
        return self.B[-1]

三、 20. 有效的括号

1. C++版本 思路

 括号匹配问题是栈的应用的经典问题,主要思路在于使用栈保存左括号,当扫描到右括号的时候,可以分类讨论一下三种情况:

①栈内的栈顶元素正好是匹配的符号:d出栈顶元素,一对匹配完成

②栈内元素与当前扫描到的元素不匹配:匹配失败

③栈空:说明不存在左括号与当前元素匹配。匹配失败

当从前到后扫描完所有的元素后,如果栈仍然不为空,说明有部分左括号没有匹配完成。匹配失败

如果栈为空,那么匹配成功。

//c++版本
class Solution {
public:
    bool isValid(string s) {
        char ch;
        stack instack;
        for(int i=0;i
2. python版本 重点

利用栈顶元素为最近一个压入元素的特性,进行邻近括号的匹配

难点

空栈情况的考虑;字典的运用

小章's Code
class Solution:
    def isValid(self, s: str) -> bool:
        ## 首先定义栈A
        self.A = []

        for i in s :
            ## 如果遍历到左括号,将该元素压入栈A中
            if i in ('(' ,'[' ,'{') :
                self.A.append(i)
            ## 善用continue跳出此次判断,避免内存浪费
                continue
            
            ## 如果遍历到右括号,需要考虑其是否与栈顶元素配对成功。额外需要注意的是栈为空的情况,也是错误的!
            elif i == ')' :
                if not self.A or self.A.pop() != '(' :
                    return False
                else :
                    continue

            elif i == ']' :
                if not self.A or self.A.pop() != '[' :
                    return False
                else :
                    continue

            elif i == '}' :
                if not self.A or self.A.pop() != '{' :
                    return False
                else :
                    continue

        ## 最后,特别需要注意!单独余一个多的左括号,也是不合规的!所以最后要把这种情况排除掉!
        return (len(self.A) == 0)
官方题解:使用字典更清晰
class Solution:
    def isValid(self, s: str) -> bool:
        ## 首先定义栈A,并给它一个初始值,与题中元素不干扰,用于保证不出现空栈的异常情况。【一个小技巧】
        self.A = ['?']
        ## 然后定义字典。键为左括号,值为右括号。
        dic = {'?':'?', '(':')', '[':']', '{':'}'}
        
        ## 如果是字典中的键,就压入栈
        for i in s :
            if i in dic : 
                self.A.append(i)
        ## 如果是字典中的值,能和栈顶元素配对的,就pop出来,假装消消乐了;
        ## 如果对不上,就报错
            elif :
                dic[self.A.pop()] != i : 
                    return False 
                    
        ## 最后同样要避免剩下落单的左括号的情况,所以需要判定是否栈恢复如初。
        return (len(self.A) == 1)

四. 735. 行星碰撞

1.C++版本:先鸽了,我还没有彻底搞懂,搞懂了下一次补上。 2. python版本(小章写的!俺的室友老棒了!)
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        
        ## 首先定义一个栈A
        self.A = [] 

        for i in asteroids :
            ## 如果栈为空,需要先将第一个行星压入栈
            if not self.A :
                self.A.append(i)
                continue
            ## 如果下一颗行星和当前这颗行星互相靠近,即向左和向右的关系时,判断一下哪颗爆炸boom
            
            elif i < 0 and self.A[-1]> 0 :
                current = self.A[-1]
                ## 如果两颗一样大,就把现在的炸了,新的忽视(相当于也炸了)
                if abs(i) == current :
                    self.A.pop()
                ## 如果下一颗更小,就忽视
                elif abs(i) < current :
                    continue
                ## 如果下一颗更大,需要循环判断撞到啥时候结束
                else :
                    self.A.pop()
                    is_i_destroyed = 0
                    while self.A and self.A[-1] > 0 and is_i_destroyed == 0:
                        updated_current = self.A[-1]
                        
                        if updated_current < abs(i) : 
                            self.A.pop()
                            continue
                        if updated_current == abs(i) : 
                            self.A.pop()
                            is_i_destroyed = 1
                            continue
                        else :
                            is_i_destroyed = 1
                            continue
                    if is_i_destroyed == 0:
                        self.A.append(i)

            else :
                self.A.append(i)

        return self.A
三叶姐题解:

其实思路是一样的,但是这个解法抓住了更核心的问题,而且代码语言高度提炼

还有很巧妙的地方,我会分三种情况写,但三叶的这种写法就只需要两种情况,纯1、纯2、both 1和2 即为第三种情况。

妙啊~~~

class Solution:
    def asteroidCollision(self, ats: List[int]) -> List[int]:
        stk = []
        for t in ats:
            ok = True
            while ok and stk and stk[-1] > 0 and t < 0:
                a, b = stk[-1], -t
            ##1。
                if a <= b:
                    stk.pop(-1)
            ##2。
                if a >= b:
                    ok = False
            if ok:
                stk.append(t)
        return stk

p.s. 虽然我俩写的都是很简单的题目,但是还是选择发出来,不仅是为了以后可以时常复习,也算是彼此督促相互监督。学无止境,都给我学!

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/3002929.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-27
下一篇 2022-09-27

发表评论

登录后才能评论

评论列表(0条)