栈和队列

Friday, April 10, 2020

栈和队列

用栈实现队列

https://leetcode.com/problems/implement-queue-using-stacks/

这题用两个栈即可,push 的时候往 栈1 push,pop 的时候先判断栈2 有没有元素,有就先 pop 出来,然后将栈1的数据全部 pop 到栈2里面


    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.statck1 = []
        self.statck2 = []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.statck1.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.statck2:
            return self.statck2.pop()
        while self.statck1:
            n = self.statck1.pop()
            self.statck2.append(n)
        
        return self.statck2.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.statck2:
            return self.statck2[-1]
        while self.statck1:
            n = self.statck1.pop()
            self.statck2.append(n)

        return self.statck2[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        if self.statck1 or self.statck2:
            return False
        else:
            return True
        

最小值栈

https://leetcode.com/problems/min-stack/description/

单独使用一个栈来保存每次的最小值,然后与数据栈同步 append 或者 pop


    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min = sys.maxsize
        self.minStatck = []
        self.dataStatck = []

    def push(self, x: int) -> None:
        self.dataStatck.append(x)
        self.min = min(self.min, x)
        self.minStatck.append(self.min)

    def pop(self) -> None:
        self.dataStatck.pop()
        self.minStatck.pop()
        if self.minStatck:
            self.min = self.minStatck[-1]
        else:
            self.min = sys.maxsize

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

    def getMin(self) -> int:
        return self.min

用栈实现括号匹配

https://leetcode.com/problems/valid-parentheses/description/

使用字典保存括号对,key 为右括号,value 为左括号,然后遍历括号字符串,将不在 key 字典里的字符存入栈,也就是左括号。然后当前字符是右括号时,将 dic 的 value 拿出来跟栈的pop 的值对比即可。

记得最后返回的时候,还要判断下栈是否为空(即括号是不是一一匹配了)


    def isValid(self, s: str) -> bool:
        stack = []
        paren_map = {')': '(', ']': '[', '}': '{'}
        for c in s:
            if c not in paren_map:
                stack.append(c)
            else:
                if not stack or stack.pop() != paren_map[c]:
                    return False
        return not stack

数组中元素与下一个比它大的元素之间的距离(Medium)

https://leetcode.com/problems/daily-temperatures/

这题需要用两个栈,一个记录 index 的栈,一个初始化为数组长度的全为0的栈,index 栈在每次遍历的最后加上最新的 currentindex,然后 currentIndex + 1, 然后拿数组的 currentIndex 的值和上一个 index 的值对比,如果比上一个数字大,则将该距离记录到一开始全为0的那个栈的 preIndex 处(即 indexs 数组的最后一个值)。这里这个步骤使用 while,就是当前 T[currentIndex]的值对比每一个 记录在 indexs 里下标的值。

之所以 indexs 里面会有好几个值,也是因为遍历的数组,这几个值都没有比上一个值大,所以才都记录进去了。如果刚好下一个值比上一个值大,就需要把前面的几个值都对比算出距离记录进去,这样 indexs 里比 T[currentIndex]小的值就都清空了。

    def dailyTemperatures(self, T: List[int]) -> List[int]:
        indexs = []
        currentIndex = 0
        statck = [0] * len(T)
        while currentIndex < len(T):
            while len(indexs) > 0 and T[currentIndex] > T[indexs[-1]]:
                preIndex = indexs.pop()
                statck[preIndex] = currentIndex - preIndex
            indexs.append(currentIndex)
            currentIndex += 1
        return statck

循环数组中比当前元素大的下一个元素(Medium)

https://leetcode.com/problems/next-greater-element-ii/description/

这题思路与上题类似,也是用一个 indexs 数组记录上一个 index 的位置,然后一个全是-1的长度为 nums 的长度的栈,当当前数比上一个数大时,赋值到这个栈中。

不同的地方是,这个是循环数组,所以遍历的长度不能是数组的长度了,而是*2的长度。所以 indexs 记录的位置,也要处理一下,大于数组长度的就不需要记录了。当前num 的大小也需要 num = nums[i % length]来处理了

    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        statck = [-1] * len(nums)
        pre = []
        for i in range(len(nums) * 2):
            num = nums[i % len(nums)]
            while len(pre) > 0 and num > nums[pre[-1]]:
                preIndex = pre.pop()
                statck[preIndex] = num
            if i < len(nums):
                pre.append(i)
        return statck
数据结构-算法LeetCode

字符串习题

双指针