LeetCode 5

232. Implement Queue using Stacks

python中list是一个常用的栈，所以可以用list来模拟队列

注意pop方法可以用deque方法更加高效。

from collections import deque

def pop(self):
    res = self.queue.popleft()
    return res

GPT版本：

class MyQueue:
    def __init__(self):
        """初始化一个空队列"""
        self.queue = deque()

    def push(self, x: int) -> None:
        """入队，在队列尾部添加元素"""
        self.queue.append(x)

    def pop(self) -> int:
        """出队，从队列头部删除并返回元素"""
        return self.queue.popleft() if not self.empty() else None

    def peek(self) -> int:
        """查看队列头部的元素"""
        return self.queue[0] if not self.empty() else None

    def empty(self) -> bool:
        """检查队列是否为空"""
        return len(self.queue) == 0

225. Implement Stack using Queues

完全做出来了

class MyStack(object):

    def __init__(self):
        self.stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)


    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None 
        # self.stack.reverse()
        # res = self.stack.pop(0)
        # self.stack.reverse()
        res = self.stack[-1]
        return res

    def top(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        return self.stack[len(self.stack)-1]

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.stack) == 0

20. Valid Parentheses

这题很经典，使用栈匹配括号，但是没做出来

核心思路是左括号和右括号的顺序是一样的，只要有左括号就一定有右括号，并且先进后出，也就是匹配到的左括号所对应的右括号放入栈底，然后逐渐放入其他各种右括号，然后关键是如果不是左括号的话，那就判断当前元素是否等于栈顶的右括号，如果不等于那就是错的，因为如果是类似[()]的话一定是对应的。最后还是满足的话就将最顶上的元素出栈，如果正确匹配的话最后栈一定是空的。

1047. Remove All Adjacent Duplicates In String

这题也完全做出来了

class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        for ss in s:
            if len(stack) == 0 or stack[-1] != ss: # 这里写 not stack也可以
                stack.append(ss)
            else:
                stack.pop(-1)

        return "".join(stack)

1365. How Many Numbers Are Smaller Than the Current Number

k = 0
count = [0] * len(nums)
for i in range(len(nums)):
    k = 0
    for j in range(len(nums)):
        if nums[i] > nums[j]:
            k += 1
            count[i] = k

return count

         count = [0] * len(nums)
for i in range(len(nums)):
    for j in range(i+1, len(nums)):
        if nums[i] > nums[j]:
            count[i] += 1
        elif nums[i] < nums[j]: 
            count[j] += 1            

return count