142. 环形链表 II
想了一个集合的方法，比较简单。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode):
if head is None:
return None
s = set()
cur = head
while cur.next:
if cur in s:
return cur
else:
s.add(cur)
cur = cur.next
return None
题目也用了哈希表的方法：
下面看到了K神的答案：
class Solution(object):
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
照着写了一下：
def detectCycle(self, head: ListNode):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
记得来2刷：
146. LRU 缓存
想到了双端队列，但是需要随机访问，所以不符合要求。下面是官方答案：
class LRUCache(collections.OrderedDict):
def __init__(self, capacity: int):
super().__init__()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self:
return -1
self.move_to_end(key)
return self[key]
def put(self, key: int, value: int) -> None:
if key in self:
self.move_to_end(key)
self[key] = value
if len(self) > self.capacity:
self.popitem(last=False)
代码看懂了，回头来2刷在写吧：
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = dict()
# 使用伪头部和伪尾部节点
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 如果 key 存在，先通过哈希表定位，再移到头部
node = self.cache[key]
self.moveToHead(node)
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
# 如果 key 不存在，创建一个新的节点
node = DLinkedNode(key, value)
# 添加进哈希表
self.cache[key] = node
# 添加至双向链表的头部
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
# 如果超出容量，删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中对应的项
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return node
148. 排序链表
先遍历，再排序，再构造链表，比较麻烦的方法：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head):
dummy = head
tmp = []
while True:
if not dummy: break
tmp.append(dummy.val)
dummy = dummy.next
tmp.sort()
dummy = cur = ListNode(0)
for t in tmp:
cur.next = ListNode(t)
cur = cur.next
return dummy.next
下面是K神的答案：
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head # termination.
# cut the LinkedList at the mid index.
slow, fast = head, head.next
while fast and fast.next:
fast, slow = fast.next.next, slow.next
mid, slow.next = slow.next, None # save and cut.
# recursive for cutting.
left, right = self.sortList(head), self.sortList(mid)
# merge `left` and `right` linked list and return it.
h = res = ListNode(0)
while left and right:
if left.val < right.val: h.next, left = left, left.next
else: h.next, right = right, right.next
h = h.next
h.next = left if left else right
return res.next
简直不是人。再来刷吧
152. 乘积最大子数组
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums: return
res = nums[0]
pre_max = nums[0]
pre_min = nums[0]
for num in nums[1:]:
cur_max = max(pre_max * num, pre_min * num, num)
cur_min = min(pre_max * num, pre_min * num, num)
res = max(res, cur_max)
pre_max = cur_max
pre_min = cur_min
return res
class Solution:
def maxProduct(self, nums: List[int]) -> int:
reverse_nums = nums[::-1]
for i in range(1, len(nums)):
nums[i] *= nums[i - 1] or 1
reverse_nums[i] *= reverse_nums[i - 1] or 1
return max(nums + reverse_nums)
跳过吧。回头再来看。
155. 最小栈
不会，下面是K神的方法：
跟着思路，自己写的：
class MinStack:
def __init__(self):
self.min_stack = []
self.stack = []
def push(self, val: int) -> None:
if self.min_stack:
if val <= self.min_stack[-1]:
self.min_stack.append(val)
else:
self.min_stack.append(val)
self.stack.append(val)
def pop(self) -> None:
if self.stack:
pop_val = self.stack.pop()
if pop_val <= self.min_stack[-1]:
self.min_stack.pop()
else:
return
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
下面是K神的代码：
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
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]
