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原文地址：https://blog.csdn.net/Jack199274/article/details/135448232
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！