【每日算法】宝，今天练算法了吗？｜Python 主题月

本文正在参加「Python主题月」，详情查看 活动链接

栈的应用

实现一个浏览器的前进后退

浏览器的前进、后退功能，我想你肯定很熟悉吧？

当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

假设你是 Chrome 浏览器的开发工程师，你会如何实现这个功能呢？

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

比如你顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：

当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：

这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中。此时两个栈的数据是这个样子：

栈的实现

class Stack(object):
    """栈"""
    def __init__(self):
         self.__items = []

    def push(self, item):
        """加入元素"""
        self.__items.append(item)

    def pop(self):
        """弹出元素"""
        return self.__items.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.__items:
            # 如果是空列表,不支持-1操作
            # return self.__items[-1]
            return self.__items[len(self.__items)-1]
        else:
            return None
    
    def is_empty(self):
        """判断是否为空"""
        if self.__items == []:
            return True
        else:
            return False
        # return self.__items == []
    
    def size(self):
        """返回栈的大小"""
        return len(self.__items)
复制代码

用栈实现浏览器的前进后退

class Browser():

    def __init__(self):
        self.x = Stack()
        self.y = Stack()

    def can_forward(self):
        if self.y.is_empty():
            return False

        return True

    def can_back(self):
        if self.x.is_empty():
            return False

        return True

    def open(self, url):
        print("Open new url %s" % url, end="\n")
        self.x.push(url)

    def back(self):
        if self.x.is_empty():
            return

        top = self.x.pop()
        self.y.push(top)
        print("back to %s" % self.x.peek(), end="\n")

    def forward(self):
        if self.y.is_empty():
            return

        top = self.y.pop()
        self.x.push(top)
        print("forward to %s" % top, end="\n")


if __name__ == '__main__':
    browser = Browser()
    browser.open('a')
    browser.open('b')
    browser.open('c')
    if browser.can_back():
        browser.back()

    if browser.can_forward():
        browser.forward()

    browser.back()
    browser.back()
    browser.back()
复制代码

判断字符串是否有效

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
复制代码

示例 2:

输入: "()[]{}"
输出: true
复制代码

示例 3:

输入: "(]"
输出: false
复制代码

解题思路

当开始接触题目时，我们会不禁想到如果计算出左括号的数量，和右括号的数量，如果每种括号左右数量相同，会不会就是有效的括号了呢？

事实上不是的，假如输入是 [{]}，每种括号的左右数量分别相等，但不是有效的括号。这是因为结果还与括号的位置有关。

def isValid(s):
    dic = {')': '(', ']': '[', '}': '{'}
    stack = []
    for i in s:
        if stack and i in dic:
            if stack[-1] == dic[i]:
                stack.pop()
            else:
                return False
        else:
            stack.append(i)

    return not stack


if __name__ == '__main__':
    print(isValid("()["))
复制代码

十进制转换为二进制

所谓的”进制”,就是用多少个字符来表示整数.

十进制是0-9这十个数字字符,二进制是0,1两个字符

我们经常需要将整数在二进制和十进制之间转换

除以2的过程,得到的余数是从低到高的次序,而输出则是从高到低,所以需要一个栈来反转次序

def divideBy2(num):
    remstack = Stack()

    while num > 0:
        # 求余数
        rem = num % 2
        remstack.push(rem)
        # 整数除
        num = num // 2

    bstr = ""
    while not remstack.is_empty():
        bstr = bstr + str(remstack.pop())

    return bstr

print(divideBy2(233))
复制代码

利用栈解决迷宫问题

给一个二维列表，表示迷宫(0表示通道，1表示围墙)。给出算法，求一条走出迷宫的路径

思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y - 1),
    lambda x, y: (x, y + 1)
]


def maze_path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    # print(stack)
    while (len(stack) > 0):
        curNode = stack[-1]  # 当前的节点
        if curNode[0] == x2 and curNode[1] == y2:
            # 走到终点了
            for p in stack:
                print(p)
            return True

        # x,y 四个方向 x-1,y; x+1,y; x,y-1; x,y+1
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2  # 2表示为已经走过
                break   # 找到可以走的方向,直接退出就可以了
        else:
            # 没有找到,回退
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print("没有路")
        return False


maze_path(1, 1, 8, 8)
复制代码