146.lru缓存机制
class DNode:
def __init__(self, key=0, value=0, prev=None, next=None):
self.key = key
self.value = value
self.prev = prev
self.next = next
class LRUCache:
def __init__(self, capacity: int):
self.head = DNode()
self.tail = DNode()
self.head.next = self.tail
self.tail.prev = self.head
self.cache = {}
self.capacity = capacity
self.size = 0
def insert_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def move_to_head(self, node):
self.remove(node)
self.insert_head(node)
def pop_tail(self):
node = self.tail.prev
self.remove(node)
return node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
else:
node = self.cache[key]
self.move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
node = DNode(key, value)
self.insert_head(node)
self.cache[key] = node
self.size += 1
if self.size > self.capacity:
t = self.pop_tail()
self.cache.pop(t.key)
self.size -= 1
else:
node = self.cache[key]
self.move_to_head(node)
node.value = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
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: ListNode) -> ListNode:
if not head or not head.next:
return head
mid=self.findmid(head)
left=head
right=mid.next
mid.next=None
l=self.sortList(left)
r=self.sortList(right)
return self.merge(l,r)
def findmid(self,head):
slow=head
fast=head
while fast.next and fast.next.next:
slow=slow.next
fast=fast.next.next
return slow
def merge(self,l,r):
dummy=ListNode(None)
cur=dummy
while l and r:
if l.val<=r.val:
cur.next=l
l=l.next
else:
cur.next=r
r=r.next
cur=cur.next
cur.next=l or r
return dummy.next
155.最小栈
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.data = []
self.minData = 0
def push(self, x: int) -> None:
if not self.data:
self.data.append(x)
self.minData = x
else:
delta = x - self.minData
if delta < 0:
self.minData = x
self.data.append(delta)
def pop(self) -> None:
if not self.data:
return
if len(self.data) == 1:
self.data.pop()
self.minData = 0
else:
delta = self.data.pop()
if delta < 0:
self.minData -= delta
def top(self) -> int:
if not self.data:
return -1
if len(self.data) == 1:
return self.data[0]
delta = self.data[-1]
if delta < 0:
return self.minData
else:
return self.minData + delta
def getMin(self) -> int:
return self.minData
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
