代码随想录算法训练营 Day 9

class MyQueue:

    def __init__(self):
        self.stack_in = []
        self.stack_out = []
        

    def push(self, x: int) -> None:
        self.stack_in.append(x)
        

    def pop(self) -> int:
        # 首先判断队列是否为空
        if self.empty():
            return None
        
        # 出栈中含有元素的话，直接取最后一个元素
        # 否则将入栈中每个元素从后往前依次压入出栈中，再取最后一个元素
        if self.stack_out:
            return self.stack_out.pop()
        else:
            for _ in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()
        

    def peek(self) -> int:
        res = self.pop()
        # peek不会影响数据，因此需要将其重新放入出栈最后
        self.stack_out.append(res)
        
        return res

    def empty(self) -> bool:
        if self.stack_in or self.stack_out:
            return False
        
        return True

from collections import deque

class MyStack:

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()
        

    def push(self, x: int) -> None:
        self.queue_in.append(x)


    def pop(self) -> int:
        if self.empty():
            return None
        
        for _ in range(len(self.queue_in)):
            self.queue_out.appendleft(self.queue_in.popleft())
        return self.queue_out.popleft()
        

    def top(self) -> int:
        res = self.pop()
        self.queue_out.appendleft(res)

        return res
        

    def empty(self) -> bool:
        if self.queue_in or self.queue_out:
            return False
        
        return True

from collections import deque

class MyStack:

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()
        

    def push(self, x: int) -> None:
        self.queue_in.append(x)


    def pop(self) -> int:
        if self.empty():
            return None
        
        for _ in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in
        return self.queue_out.popleft()
        

    def top(self) -> int:
        if self.empty():
            return None
        
        for _ in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in
        res = self.queue_out.popleft()
        self.queue_in.append(res)
        
        return res
        

    def empty(self) -> bool:
        if self.queue_in:
            return False
        
        return True

class Solution:
    def isValid(self, s: str) -> bool:
        match_stack = []

        for c in s:
            if c == '(':
                match_stack.append(')')
            elif c == '{':
                match_stack.append('}')
            elif c == '[':
                match_stack.append(']')
            else:
                if not match_stack or match_stack[-1] != c:
                    return False
                match_stack.pop()
        
        # 需要判断最后是否还有未匹配项
        if match_stack:
            return False
        
        return True

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        
        for c in s:
            if stack and stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)
        
        return ''.join(stack)

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list(s)
        slow = fast = 0
        length = len(res)

        while fast < length:
            # 如果一样直接换，不一样会把后面的填在slow的位置
            res[slow] = res[fast]
            
            # 如果发现和前一个一样，就退一格指针
            if slow > 0 and res[slow] == res[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
            
        return ''.join(res[0: slow])