python算法技巧——堆栈练习及掌握

r囧r小猫 2023-09-29 12:48 68阅读 0赞

**目录**

1. 给予一个字符串内含( )、\[ \]、\{ \}，判断是否合法：

2. 设计一个Minstack类，完成下列工作：

3. 使用队列(queue)完成下列堆栈的操作：

4. 按下列要求比较两段内容是否相同 ：

5. 删除相邻且相同的字符：

--------------------

#### **1. 给予一个字符串内含( )、\[ \]、\{ \}，判断是否合法：** ####

def isvalid(s):
        stack = []
        for i in range(len(s)):
            if s[i] in '([{':
                stack.append(s[i])
            if s[i] == ')':
                if s[i] == [] or stack.pop() != '(':
                    return False
            if s[i] == ']':
                if s[i] == [] or stack.pop() != '[':
                    return False        
            if s[i] == '}':
                if s[i] == [] or stack.pop() != '{':
                    return False
    
        if stack:
            return False
        else:
            return True
    
    print(isvalid('{12[4(123)]}'))
    print(isvalid('({)}'))

> 上述设计概念是使用堆栈的概念，如果符号是(、\[、\{，就存入堆栈，如果是)、\]、\}符号，就检查堆栈顶端是否有匹配的符号，如果没有表示匹配不合法。最后遍历字符串结束，如果堆栈内有数据表示匹配不合法，否则合法；

--------------------

#### **2. 设计一个Minstack类，完成下列工作：** ####

>  *  push(x)：将x推入堆栈；
>  *  pop()：将元素从堆栈顶端删除；
>  *  top()：取得堆栈顶端元素；
>  *  getmin()：获得堆栈最小值；

class Minstack():
        def __init__(self):
            self.stack = []
        
        def push(self, x):
            if self.stack == []:
                self.stack.append((x, x))
            else:
                self.stack.append((x, min(x, self.stack[-1][1])))
        
        def pop(self):
            self.stack.pop()
    
        def top(self):
            return self.stack[-1][0]  
        
        def getmin(self):
            return self.stack[-1][1]
    
    minstack = Minstack()
    minstack.push(-1)
    minstack.push(0)
    minstack.push(-5)
    print(minstack.getmin())
    minstack.pop()
    print(minstack.top())
    print(minstack.getmin())

> 上述程序的设计概念是，将元素值推入堆栈时使用元组，元组的索引0是元素值，元祖的索引1是当下最小值。

--------------------

#### **3. 使用队列(queue)完成下列堆栈的操作：**  ####

>  *  push()：将元素推入堆栈；
>  *  pop()：移除和回传堆栈顶端数据；
>  *  top()：取得堆栈顶端值；
>  *  empty()：回传堆栈是否为空；
> 
> 使用队列仿真表示，数据必须插入末端，取值要从前端，同时要可以操作empty()，判断堆栈是否为空；

class mystack():
        def __init__(self):
            self.queue = []
    
        def push(self, x):
            self.queue.append(x)
            tmp = []
            tmp.append(self.queue[-1])
            self.queue = tmp + self.queue[:-1]
    
        def pop(self):
            if self.empty():
                return None
            return self.queue.pop(0)
        
        def top(self):
            if self.empty():
                return None
            return self.queue[0]
        
        def empty(self):
            return self.queue == []
    
    stack = mystack()
    stack.push(1)
    stack.push(3)
    print(stack.pop())
    print(stack.top())
    print(stack.empty())

> 队列的特色是数据从一端插入(enqueue)，从另一端取值(dequeue),所以在stack的push设计中，在append(x)数据后，数据是在末端，而后的append是将数据移至队列的前端。所以pop()时可以从队列前端取值同时删除此元素，top()可以从前端回传元素；

--------------------

#### **4. 按下列要求比较两段内容是否相同 ：** ####

> 函数包含两个字符串，如果字符串有\#字符，可以让字符退后一格，相当于删除一个字符，最后比较两个字符串是否相同；

def backspacecompare(s, t):
        stacks = []
        stackt = []
        for i in s:
            if i != '#':
                stacks.append(i)
            else:
                stacks.pop()
    
        for i in t:
            if i != '#':
                stackt.append(i)
            else:
                stackt.pop()
        
        return stacks == stackt
    
    print(backspacecompare('ab#c', 'ad#c'))
    print(backspacecompare('a#k', 'a'))

> 上述设计主要是一个个读取字符串的字符，如果字符不是\#则将此字符推入堆栈，如果字符是\#则将堆栈的字符pop出来，最后比较堆栈的结果就可以得到两个字符串是否相同。

--------------------

#### **5. 删除相邻且相同的字符：** ####

def removeduplicates(s):
        stack = []
        for i in s:
            if stack and i == stack[-1]:
                stack.pop()
            else:
                stack.append(i)
        return ''.join(stack)
    
    print(removeduplicates('abbada'))
    print(removeduplicates('abdbada'))

> 设计程序时，每次比较字符是否与堆栈顶端的字符相同，如果相同则pop堆栈顶端字符，如果不想则将字符推入堆栈。

--------------------

## **算法技巧专栏**  ##

[https://blog.csdn.net/weixin\_53919192/category\_11761989.html![icon-default.png_t_M3K6][]https://blog.csdn.net/weixin\_53919192/category\_11761989.html][https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]

[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]: https://blog.csdn.net/weixin_53919192/category_11761989.html