1. 剑指 Offer 06. 从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # return self.reversePrint(head.next)+[head.val] if head else []
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-1]

2. 剑指 Offer 09. 用两个栈实现队列


1
2
3
4
5
6
7
8
9
10
11
12
13
14
class CQueue:

    def __init__(self):
        self.A,self.B = [],[]

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if self.B:return self.B.pop()
        if not self.A:return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()

3 剑指 Offer 30. 包含min函数的栈


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A,self.B = [],[]
        
    def push(self, x: int) -> None:
        self.A.append(x)
        if not self.B or self.B[-1] >= x:self.B.append(x)

    def pop(self) -> None:
        if self.A:
            if self.A[-1]==self.B[-1]:self.B = self.B[:-1]
            self.A = self.A[:-1]

    def top(self) -> int:
        return self.A[-1] if self.A else -1

    def min(self) -> int:
        print(self.B)
        return self.B[-1] if self.B else -111

4. 剑指 Offer 31. 栈的压入、弹出序列

1
2
3
4
5
6
7
8
9
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack,i = [],0
        for num in pushed:
            stack.append(num)
            while stack and stack[-1] == popped[i]:
                i+=1
                stack.pop()
        return not stack

5. 剑指 Offer 59 - I. 滑动窗口的最大值


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 先看剑指 Offer 59 - II. 队列的最大值
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res=[]
        A,B = [],[] # A用来存放队列中的数，B用来存放队列中最大的数的队列，每次push_back和pop_front都需要更新B
        for num in nums:
            #  push_back(num)
            A.append(num)
            while B and B[-1]<num:B.pop()
            B.append(num)
            #  队列长度达到最大长度时pop_front(num)
            if len(A)==k:
                res.append(B[0])
                if A[0]==B[0]:B=B[1:]
                A=A[1:]
        return res

6. 剑指 Offer 59 - II. 队列的最大值

class MaxQueue:
    def __init__(self):
        self.A,self.B=[],[]

    def max_value(self) -> int:
        return self.B[0] if self.B else -1

    def push_back(self, value: int) -> None:
        self.A.append(value)
        while self.B and self.B[-1]<value:self.B.pop()
        self.B.append(value)

    def pop_front(self) -> int:
        if self.A :
            res = self.A[0] 
            if res==self.B[0]:self.B = self.B[1:]
            self.A = self.A[1:]
        else: res=-1
        return res