Grind75第3天 | 155.最小栈、224.基本计算器、21.合并两个有序链表

155.最小栈

题目链接：https://leetcode.com/problems/min-stack/

解法：

python中用list来表示栈，需要用到两个栈，其中借用一个辅助栈?min_stack，用于存取?stack?中最小值。

主要是push和pop的实现。

push() 方法： 每当push()新值进来时，如果小于等于 min_stack 栈顶值，则?push() 到 min_stack，即更新了栈顶最小值。
pop() 方法： 判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。

题目说pop、top?和?getMin?操作总是在?非空栈?上调用，所以不用判断是否为空了。

def push()中的x <=中的=如果掉了，这样会直接导致下标越界。有重复最小值时也要注入最小栈，这样测试样例才能通过。

参考题解：辅助栈

边界条件：无

时间复杂度：O(1)

空间复杂度：O(n)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        # 注意这里的判断是 <=，而不是 <，有重复最小元素也要加入辅助栈
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

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

    def getMin(self) -> int:
        return self.min_stack[-1]

224.基本计算器

题目链接：https://leetcode.com/problems/basic-calculator

解法：

这个题只要求实现【加、减】，但是考虑到可能有题目会要求把【加、减、乘、除】都实现，所以这里给出完整四则运算的代码。

过程比较长，直接看题解就行，参考题解：计算器

边界条件：无

时间复杂度：O(n)

空间复杂度：O(n)

class Solution:
    def calculate(self, s: str) -> int:
        # 使用deque效率高
        que = deque(s)
        return self.helper(que)

    def helper(self, que):
        stack = []
        num = 0
        sign = '+'

        while que:
            c = que.popleft()
            if c.isdigit():
                num = 10 * num + int(c)
            if c == '(':
                num = self.helper(que)

            # c = '(' 或 ')' 时，也会运行以下代码，会执行 sign = c, num = 0
            if (not c.isdigit() and c != ' ') or len(que) == 0:
                if sign == '+':
                    stack.append(num)
                if sign == '-':
                    stack.append(-num)
                if sign == '*':
                    pre = stack.pop()
                    stack.append(pre * num)
                if sign == '/':
                    pre = stack.pop()
                    # 除法向0取整
                    stack.append(int(pre / num))
                # 记得更新
                sign = c
                num = 0
            
            if c == ')': break
        return sum(stack)

21.合并两个有序链表

题目链接：https://leetcode.com/problems/merge-two-sorted-lists

解法：

双指针解法：

首先定一个dummy链表，用于合并两个链表。同时遍历两个链表（不断指向下一个node），如果 l1.val< l2.val，那么把l1添加为dummy链表中，否则添加l2。

最后如果两个链表长度不等，那么必有一个链表为空，一个不为空，那么把不为空的链表直接添加到dummy链表中。

最后返回dummy.next即可。

参考题解：双指针

递归解法：

终止条件：当一个链表为空时，合并完成，直接返回另外一个不为空的。
如何递归：我们判断 l1 和 l2 头结点哪个更小，如果l1小，那么l1的next指针和l2进行合并，然后作为l1的新的next指针。

参考题解：递归

边界条件：无

时间复杂度：O(m+n)，m和n分别是两个链表的长度

空间复杂度：双指针O(1)，递归O(m+n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 递归
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1: return list2
        if not list2: return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            # list2已经被合并了，所以返回list1
            return list1
        else:
            list2.next = self.mergeTwoLists(list2.next, list1)
            return list2