赞
踩
def smallest_k(nums, k): front = nums[:k] after = nums[k:] # 对前k个数建立最大堆 for i in range(k // 2, -1, -1): heapify(front, i, k) # 从after中依次取出数据和堆顶比 for i in after: if i < front[0]: front[0] = i heapify(front, 0, k) return front def heapify(nums, i, size): """调整大顶堆""" left, right = 2*i+1, 2*i+2 # 第i号结点的左子树和右子树 largest = i if left < size and nums[left] > nums[largest]: largest = left if right < size and nums[right] > nums[largest]: largest = right if largest != i: # 若发现左右子树比父结点大, 则互换位置, 再继续向下调整堆 swap(nums, i, largest) heapify(nums, largest, size)
class DLinkNode(): def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None class LRUCache(): def __init__(self, capacity): self.head = DLinkNode() self.tail = DLinkNode() self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.items = {} def remove_node(self, node): node.prev.next = node.next node.next.prev = node.prev def add_node_to_head(self, node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def move_node_to_head(self, node): self.remove_node(node) self.add_node_to_head(node) def put(self, key, val): node = self.items.get(key) if node: # 存在, 更新值 node.val = val self.move_node_to_head(node) else: # 不存在, 插入值 if len(self.items) == self.capacity: # 若容量已满, 先移除最后一个node last_node = self.tail.prev self.items.pop(last_node.key) self.remove_node(last_node) new_node = DLinkNode(key, val) self.items[key] = new_node self.add_node_to_head(new_node) def get(self, key): node = self.items.get(key) if node: self.move_node_to_head(node) return node.val return -1
def catch_rain(height): left, right = 0, len(height)-1 left_max, right_max = 0,0 count = 0 while left <= right: if left_max < right_max: # 左边墙低, 接到的雨水数以左边为准 if height[left] > left_max: left_max = height[left] else: count += left_max - height[left] left += 1 else: # 右边墙低 if height[right] > right_max: right_max = height[right] else: count += right_max - height[right] right -= 1 return count
def fab(n):
a, b = 0, 1
ret = []
for i in range(n):
ret.append(b)
a, b = b, a+b
return ret
class Stack(): def __init__(self): self.items = [] def push(self, x): self.items.append(x) def pop(self): return self.items.pop() def top(self): return self.items[-1] def empty(self): return self.items == [] class MyQueue(): def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, x: int) -> None: self.s1.push(x) def pop(self) -> int: if not self.s2.empty(): return self.s2.pop() while not self.s1.empty(): val = self.s1.pop() self.s2.push(val) return self.s2.pop() def peek(self) -> int: if not self.s2.empty(): return self.s2.top() while not self.s1.empty(): val = self.s1.pop() self.s2.push(val) return self.s2.top() def empty(self) -> bool: return self.s1.empty() and self.s2.empty()
class ListNode():
def __init__(self, val=0):
self.val = val
self.next = None
def reverse_list(head):
cur = head
pre = None
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def has_cycle(head):
p1 = p2 = head
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
if p1 is p2:
return True
return False
def merge_two_lists(l1, l2):
head = ListNode()
cur = head
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return head.next
def merge_k_lists(lists):
all_val = []
for l in lists:
while l:
all_val.append(l.val)
l = l.next
head = ListNode()
cur = head
import heapq
heapq.heapify(all_val)
while all_val:
val = heapq.heappop(all_val)
cur.next = ListNode(val)
cur = cur.next
return head.next
class MyStack(): def __init__(self): self.items = [] def push(self, val): self.items.append(val) def pop(self): return self.items.pop() def top(self): return self.items[-1] def empty(self): return self.items == [] class MyQueue(): def __init__(self): self.s1 = MyStack() self.s2 = MyStack() def push(self, val): self.s1.push(val) def pop(self, val): if self.s2.empty(): while not self.s1.empty(): self.s2.push(self.s1.pop()) return self.s2.pop() def peek(self, val): if self.s2.empty(): while not self.s1.empty(): self.s2.push(self.s1.pop()) return self.s2.top()
class MyQueue(): def __init__(self): self.items = [] def push_back(self, x): self.items.append(x) def pop_front(self): return self.items.pop(0) def peek_front(self): return self.items[0] def size(self): return len(self.items) def empty(self): return len(self.items) == 0 class MyStack(): def __init__(self): self.q1 = MyQueue() self.q2 = MyQueue() def push(self, val): self.q1.push_back(val) def pop(self): while self.q1.size() > 1: self.q2.push_back(self.q1.pop_front()) ret = self.q1.pop_front() self.q1, self.q2 = self.q2, self.q1 return ret def top(self): while self.q1.size() > 1: self.q2.push_back(self.q1.pop_front()) ret = self.q1.peek_front() self.q2.push_back(self.q1.pop_front()) self.q1, self.q2 = self.q2, self.q1 return ret def empty(self): return self.q1.empty() and self.q2.empty()
class TreeNode():
def __init__(self, val=0):
self.val = left
self.left = None
self.right = None
def pre_order_trav(root):
"""根左右"""
stack = []
ret = []
cur = root
while stack or cur:
if cur:
ret.append(cur.val)
stack.append(cur.right)
cur = cur.left
else:
cur = stack.pop()
return ret
def in_order_trav(root):
"""左根右"""
stack = []
ret = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
ret.append(cur.val)
cur = cur.right
return ret
class post_order_trav(root):
"""根右左 -> 左右根"""
stack = []
ret = []
cur = root
while cur or stack:
if cur:
ret.append(cur.val)
stack.append(cur.left)
cur = cur.right
else:
cur = stack.pop()
return ret[::-1]
def level_order_trav(root):
queue = [root]
ret = []
while queue:
parent = queue.pop(0)
ret.append(parent.val)
if parent.left:
queue.append(parent.left)
if parent.right:
queue.append(parent.right)
return ret
def invert_tree(root):
if root is None:
return
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return root
def binary_search(nums, target):
beg = 0
end = len(nums) - 1
while beg <= end:
mid = (beg + end) // 2
if target == nums[mid]:
return mid
elif target > nums[mid]:
beg = mid + 1
else:
end = mid - 1
def bubble_sort(nums):
for i in range(len(nums) - 1):
flag = False
for j in range(len(nums) - 1 - i):
if nums[j] > nums[j + 1]:
flag = True
swap(nums, j, j + 1)
if not flag:
break
return nums
def quick_sort(nums, left, right): pivot = partition(nums, left, right) quick_sort(nums, left, pivot - 1) quick_sort(nums, pivot + 1, right) return nums def partition(nums, left, right): pivot = left i = j = pivot + 1 while j <= right: if nums[j] < nums[pivot]: swap(nums, i, j) i += 1 j += 1 swap(nums, i-1, pivot) return i-1
def select_sort(nums):
for i in range(len(nums)-1):
min_idx = i
for j in range(i+1, len(nums)):
if nums[j] < nums[min_idx]:
min_idx = j
swap(nums, i, min_idx)
return nums
def heapify(nums, i, size): left = 2*i + 1 right = 2*i + 2 largest = i if left < size and nums[left] > nums[largest]: largest = left if right < size and nums[right] > nums[largest]: largest = right if largest != i: swap(nums, i, largest) heapify(nums, largest, size) def heap_sort(nums): # 建立最大堆 size = len(nums) for i in range(size // 2, -1, -1): heapify(nums, i, size) # 每一轮把堆顶放到后面 for i in range(len(nums)-1, 0, -1): swap(nums, 0, i) size -= 1 heapify(nums, 0, size) return nums
def insert_sort(nums):
for i in range(1, len(nums)):
val = nums[i]
j = i - 1
while j >= 0 and nums[j] > val:
nums[j+1] = nums[j]
j -= 1
nums[j+1] = val
return nums
def shell_sort(nums):
n = len(nums)
gap = n // 2
while gap >= 2:
for i in range(gap):
j = i
while j+gap < n:
if nums[j] > nums[j+gap]:
swap(nums, j, j+gap)
j += gap
gap //= 2
return nums
def merge(left, right): ret = [] while left and right: if left[0] < right[0]: ret.append(left.pop(0)) else: ret.append(right.pop(0)) ret.extend(left or right) return ret def merge_sort(nums): if len(nums) < 2: return nums mid = len(nums) // 2 left = nums[:mid] right = nums[mid:] return merge(merge_sort(left), merge_sort(right))
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。