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

目录

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.htmlhttps://blog.csdn.net/weixin_53919192/category_11761989.html