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

2024-01-08 16:56:01

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 中的最小值。

题目说poptop?和?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

文章来源:https://blog.csdn.net/Jack199274/article/details/135448232
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。