堆就是用数组实现的二叉树，所有它没有使用父指针或者子指针。
堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
堆的常用方法：
1 构建优先队列
2 支持堆排序
3 快速找出一个集合中的最小值（或者最大值）
堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。
在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。
1103、分糖果
题目
class Solution:
def distributeCandies(self, candies: int, num_people: int) -> List[int]:
n = num_people
# how many people received complete gifts
p = int((2 * candies + 0.25)**0.5 - 0.5)
remaining = int(candies - (p + 1) * p * 0.5)
rows, cols = p // n, p % n
d = [0] * n
for i in range(n):
# complete rows
d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n
# cols in the last row
if i < cols:
d[i] += i + 1 + rows * n
# remaining candies
d[cols] += remaining
return d
23、合并K个排序链表
题目
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
self.node=[]
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next
215、数组中的第k个最大元素
题目
# 直接排序
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
a=sorted(nums)
lens=len(a)
return a[-k]
# 堆
# 维持最大堆，就是保持堆的长度为k，而堆顶总是当前堆里的最大值，如果后面值比堆顶大，
# 且堆长度大于k需要更新堆定值即可，遍历完最后的值为第k大元素
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import queue
dp = queue.PriorityQueue()
for v in nums:
dp.put(v)
if dp.qsize() > k:
dp.get()
return dp.get()
217、存在重复元素
题目
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
n=sorted(nums)
for i in range(1,len(n)):
if n[i]==n[i-1]:
return True
return False
218、天际线的问题
题目
#最大堆
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
#思路：最大堆，每次在判断关键点的时候，移除所有右端点≤当前点的堆顶。
if not buildings:return []
points = []
heap = [[0, float('inf')]]
res = [[0, 0]]
#1.将所有端点加入到点集中(每个建筑物的左右端点)
for l, r, h in buildings:
points.append((l, -h, r)) #这里负号将最小堆，变成了最大堆
points.append((r, h, 0)) #r的右端点为0
#2.将端点从小到大排序
points.sort() #如果当前点相等，则按照高度升序
#3.遍历每一个点，分别判断出堆、入堆、添加关键点操作。
for l, h, r in points:
while l >= heap[0][1]: #出堆：保证当前堆顶为去除之前建筑物右端点的最大值。
heapq.heappop(heap)
if h < 0: #入堆：所有左端点都要入堆
heapq.heappush(heap, [h, r])
if res[-1][1] != -heap[0][0]: #关键点：必然是左端点，堆顶，因此需要加负号
res.append([l, -heap[0][0]])
return res[1:]
239、 滑动窗口最大值
题目
# 暴力法
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if n * k == 0:
return []
return [max(nums[i:i + k]) for i in range(n - k + 1)]
#动态规划
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if n * k == 0:
return []
if k == 1:
return nums
left = [0] * n
left[0] = nums[0]
right = [0] * n
right[n - 1] = nums[n - 1]
for i in range(1, n):
# from left to right
if i % k == 0:
# block start
left[i] = nums[i]
else:
left[i] = max(left[i - 1], nums[i])
# from right to left
j = n - i - 1
if (j + 1) % k == 0:
# block end
right[j] = nums[j]
else:
right[j] = max(right[j + 1], nums[j])
output = []
for i in range(n - k + 1):
output.append(max(left[i + k - 1], right[i]))
return output
264、丑数II
题目
# 最小堆
class Solution:
def nthUglyNumber(self, n: int) -> int:
import heapq
heap = [1]
heapq.heapify(heap)
res = 0
for _ in range(n):
res = heapq.heappop(heap)
while heap and res == heap[0]:
res = heapq.heappop(heap)
a, b, c = res * 2, res * 3, res * 5
for t in [a, b, c]:
heapq.heappush(heap, t)
return res
295、数据流的中位数
题目
#
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.lst=[]
def addNum(self, num: int) -> None:
self.lst.append(num)
def findMedian(self) -> float:
self.lst.sort()
n=len(self.lst)
if n & 1 == 1: # n 是奇数
return self.lst[n // 2]
else:
return (self.lst[n // 2 - 1] + self.lst[n // 2]) / 2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
313、超级丑数
题目
# 堆
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
import heapq
heap = [1]
n -= 1
while n:
tmp = heapq.heappop(heap)
while heap and tmp == heap[0]:
tmp = heapq.heappop(heap)
for p in primes:
t = p * tmp
heapq.heappush(heap, t)
n -= 1
return heapq.heappop(heap)
347、前k个高频元素
题目
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = collections.Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
355、设计推特
题目
import heapq
class Twitter:
def __init__(self):
"""
Initialize your data structure here.
"""
self.user_info = {}
self.tweet_id = []
self.follow_info = {}
def postTweet(self, userId: int, tweetId: int) -> None:
"""
Compose a new tweet.
"""
self.user_info[userId] = self.user_info.get(userId, []) + [len(self.tweet_id)]
self.tweet_id.append(tweetId)
def getNewsFeed(self, userId: int) -> List[int]:
"""
Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
"""
followers = self.follow_info.get(userId, set())
heap = []
followers.add(userId)
for user in followers:
info = self.user_info.get(user, [])
for tweet in info:
heap.append(-tweet)
heapq.heapify(heap)
res = []
cnt = 1
while heap and cnt <= 10:
res.append(self.tweet_id[-heapq.heappop(heap)])
cnt += 1
return res
def follow(self, followerId: int, followeeId: int) -> None:
"""
Follower follows a followee. If the operation is invalid, it should be a no-op.
"""
self.follow_info[followerId] = self.follow_info.get(followerId, set())
if followeeId not in self.follow_info[followerId]:
self.follow_info[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
"""
Follower unfollows a followee. If the operation is invalid, it should be a no-op.
"""
self.follow_info[followerId] = self.follow_info.get(followerId, set())
if followeeId in self.follow_info[followerId]:
self.follow_info[followerId].remove(followeeId)
# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)1
373、查找和最小的k对数字
题目
class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
import heapq
res = []
queue = []
if not nums1 or not nums2:
return []
heapq.heappush(queue, (nums1[0] + nums2[0], (0, 0)))
# 防止重复加入
visited = {(0, 0)}
while queue and len(res) < k:
_, (i, j) = heapq.heappop(queue)
res.append((nums1[i], nums2[j]))
# 每次nums1 或者 nums2 移动
if i + 1 < len(nums1) and (i + 1, j) not in visited:
heapq.heappush(queue, (nums1[i + 1] + nums2[j], (i + 1, j)))
visited.add((i + 1, j))
if j + 1 < len(nums2) and (i, j + 1) not in visited:
heapq.heappush(queue, (nums1[i] + nums2[j + 1], (i, j + 1)))
visited.add((i, j + 1))
return res
378、有序数组中第k小元素
题目
# 二分
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
left = matrix[0][0]
right = matrix[-1][-1]
def search_less_equal(mid):
i = 0
j = n - 1
res = 0
while i < n and j >= 0:
if matrix[i][j] <= mid:
res += (j + 1)
i += 1
else:
j -= 1
return res
while left < right:
mid = (left + right) // 2
num = search_less_equal(mid)
if num < k:
left = mid + 1
else:
right = mid
return left
407、接雨水II
题目
题目
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
import heapq
if not heightMap: return 0
heap = []
cur_max = float("-inf")
visited = set()
row = len(heightMap)
col = len(heightMap[0])
res = 0
# 边界放进去
# 行
for j in range(col):
heapq.heappush(heap, [heightMap[0][j], 0, j])
heapq.heappush(heap, [heightMap[row - 1][j], row - 1, j])
visited.add((0, j))
visited.add((row - 1, j))
# 列
for i in range(row):
heapq.heappush(heap, [heightMap[i][0], i, 0])
heapq.heappush(heap, [heightMap[i][col - 1], i, col - 1])
visited.add((i, 0))
visited.add((i, col - 1))
while heap:
h, i, j = heapq.heappop(heap)
cur_max = max(h, cur_max)
for x, y in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
tmp_i = i + x
tmp_j = j + y
if tmp_i < 0 or tmp_i >= row or tmp_j < 0 or tmp_j >= col or (tmp_i, tmp_j) in visited:
continue
visited.add((tmp_i, tmp_j))
if heightMap[tmp_i][tmp_j] < cur_max:
res += cur_max - heightMap[tmp_i][tmp_j]
heapq.heappush(heap, [heightMap[tmp_i][tmp_j], tmp_i, tmp_j])
return res
451、根据字符出现频率排序
题目
题目
class Solution:
def frequencySort(self, s: str) -> str:
# 大顶堆
countFrequency = collections.defaultdict(int)
for i in s:
countFrequency[i] += 1
lst = []
heapq.heapify(lst)
for i in countFrequency:
for j in range(countFrequency[i]):
heapq.heappush(lst, (-countFrequency[i], i))
return ''.join([heapq.heappop(lst)[1] for _ in range(len(s))])
502、IPO
题目
from heapq import nlargest, heappop, heappush
class Solution:
def findMaximizedCapital(self, k: int, W: int, Profits: List[int], Capital: List[int]) -> int:
# to speed up: if all projects are available
if W >= max(Capital):
return W + sum(nlargest(k, Profits))
n = len(Profits)
projects = [(Capital[i], Profits[i]) for i in range(n)]
# sort the projects :
# the most available (= the smallest capital) is the last one
projects.sort(key = lambda x : -x[0])
available = []
while k > 0:
# update available projects
while projects and projects[-1][0] <= W:
heappush(available, -projects.pop()[1])
# if there are available projects,
# pick the most profitable one
if available:
W -= heappop(available)
# not enough capital to start any project
else:
break
k -= 1
return W
659、分割数组为连续子序列
题目
import heapq
from collections import defaultdict
class Solution:
def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
chains = defaultdict(list)
for i in nums:
if not chains[i-1]:
heapq.heappush(chains[i],1)
else:
min_len = heapq.heappop(chains[i-1])
heapq.heappush(chains[i],min_len+1)
#print(chains)
for _,chain in chains.items():
if chain and chain[0] < 3:
return False
return True
692、前k个高频单词
题目
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
count = collections.Counter(words)
heap = [(-freq, word) for word, freq in count.items()]
heapq.heapify(heap)
return [heapq.heappop(heap)[1] for _ in range(k)]
703、数据流中的第k大元素
题目
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.minheap = []
# 构建大小为 k 的小顶堆(O(k))
for i in range(min(k, len(nums))):
self.minheap.append(nums[i])
self.sift_up(i)
# 将多余的 nums 元素加入其中(O(nlog(t)))
for num in nums[k:]:
if num > self.minheap[0]:
self.minheap[0] = num
# 下沉新加入的节点以维护小顶堆
self.sift_down(0, k - 1)
def sift_up(self, new_idx: int):
new_val = self.minheap[new_idx]
# 循环比较新加入的节点以及其双亲节点以上浮新加入的节点
while new_idx > 0 and new_val < self.minheap[(new_idx - 1) // 2]:
self.minheap[new_idx] = self.minheap[(new_idx - 1) // 2]
new_idx = (new_idx - 1) // 2
self.minheap[new_idx] = new_val
def sift_down(self, start, end):
start_val = self.minheap[start]
# 循环比较新加入的节点以及其双子节点以下沉新加入的节点
while start * 2 + 1 <= end:
child = start * 2 + 1
# 找到双子节点中较小的一个节点
if child + 1 <= end and self.minheap[child] > self.minheap[child + 1]:
child += 1
if start_val > self.minheap[child]:
self.minheap[start] = self.minheap[child]
start = child
else: break
self.minheap[start] = start_val
def add(self, val: int) -> int:
if len(self.minheap) < self.k:
self.minheap.append(val)
self.sift_up(len(self.minheap) - 1)
elif self.minheap[0] < val:
self.minheap[0] = val
self.sift_down(0, self.k - 1)
return self.minheap[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
719、找出第k小的距离对
题目
#zijixiede
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
stack=[]
for i in range(len(nums)):
for j in range(i+1,len(nums)):
tmp=abs(nums[i]-nums[j])
stack.append(tmp)
stack=sorted(stack)
return stack[k-1]
# 二分
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
left, right = 0,nums[-1] - nums[0]
while left < right:
mid = (left + right) // 2
cnt, start = 0, 0
for i in range(len(nums)):
while nums[i] - nums[start] > mid:
start += 1
cnt += i - start
if cnt < k:
left = mid + 1
else:
right = mid
return left
743、网络延迟时间
题目
class Solution(object):
def networkDelayTime(self, times, N, K):
graph = collections.defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
pq = [(0, K)]
dist = {}
while pq:
d, node = heapq.heappop(pq)
if node in dist: continue
dist[node] = d
for nei, d2 in graph[node]:
if nei not in dist:
heapq.heappush(pq, (d+d2, nei))
return max(dist.values()) if len(dist) == N else -1
767、重构字符串
题目
#贪心算法
class Solution(object):
def reorganizeString(self, S):
pq = [(-S.count(x), x) for x in set(S)]
heapq.heapify(pq)
if any(-nc > (len(S) + 1) / 2 for nc, x in pq):
return ""
ans = []
while len(pq) >= 2:
nct1, ch1 = heapq.heappop(pq)
nct2, ch2 = heapq.heappop(pq)
ans.extend([ch1, ch2])
if nct1 + 1: heapq.heappush(pq, (nct1 + 1, ch1))
if nct2 + 1: heapq.heappush(pq, (nct2 + 1, ch2))
return "".join(ans) + (pq[0][1] if pq else '')
778、水位上升的泳池中游泳
题目
class Solution(object):
def swimInWater(self, grid):
N = len(grid)
seen = {(0, 0)}
pq = [(grid[0][0], 0, 0)]
ans = 0
while pq:
d, r, c = heapq.heappop(pq)
ans = max(ans, d)
if r == c == N-1: return ans
for cr, cc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= cr < N and 0 <= cc < N and (cr, cc) not in seen:
heapq.heappush(pq, (grid[cr][cc], cr, cc))
seen.add((cr, cc))
786、第k个最小的素数分数
题目
class Solution(object):
def kthSmallestPrimeFraction(self, primes, K):
from fractions import Fraction
def under(x):
# Return the number of fractions below x,
# and the largest such fraction
count = best = 0
i = -1
for j in range(1, len(primes)):
while primes[i+1] < primes[j] * x:
i += 1
count += i+1
if i >= 0:
best = max(best, Fraction(primes[i], primes[j]))
return count, best
# Binary search for x such that there are K fractions
# below x.
lo, hi = 0.0, 1.0
while hi - lo > 1e-9:
mi = (lo + hi) / 2.0
count, best = under(mi)
if count < K:
lo = mi
else:
ans = best
hi = mi
return ans.numerator, ans.denominator
787、k站中转内最便宜的航班
题目
题目
import collections
class Solution(object):
def findCheapestPrice(self, n, flights, src, dst, K):
graph = collections.defaultdict(dict)
for u, v, w in flights:
graph[u][v] = w
best = {}
pq = [(0, 0, src)]
while pq:
cost, k, place = heapq.heappop(pq)
if k > K+1 or cost > best.get((k, place), float('inf')): continue
if place == dst: return cost
for nei, wt in graph[place].items():
newcost = cost + wt
if newcost < best.get((k+1, nei), float('inf')):
heapq.heappush(pq, (newcost, k+1, nei))
best[k+1, nei] = newcost
return -1
818、赛车
题目
# 动态规划
class Solution(object):
def racecar(self, target):
dp = [0, 1, 4] + [float('inf')] * target
for t in range(3, target + 1):
#bit_length方法作用是得到指定数值的二进制的长度数、宽度数
k = t.bit_length()
if t == 2**k - 1:
dp[t] = k
continue
for j in range(k - 1):
dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)
if 2**k - 1 - t < t:
dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)
return dp[target]
857、雇佣k名工人的最低成本
题目
# 贪心算法
class Solution(object):
def mincostToHireWorkers(self, quality, wage, K):
from fractions import Fraction
ans = float('inf')
N = len(quality)
for captain in range(N):
# Must pay at least wage[captain] / quality[captain] per qual
factor = Fraction(wage[captain], quality[captain])
prices = []
for worker in range(N):
price = factor * quality[worker]
if price < wage[worker]: continue
prices.append(price)
if len(prices) < K: continue
prices.sort()
ans = min(ans, sum(prices[:K]))
return float(ans)
# 堆（优先队列）
class Solution(object):
def mincostToHireWorkers(self, quality, wage, K):
from fractions import Fraction
workers = sorted((Fraction(w, q), q, w)
for q, w in zip(quality, wage))
ans = float('inf')
pool = []
sumq = 0
for ratio, q, w in workers:
heapq.heappush(pool, -q)
sumq += q
if len(pool) > K:
sumq += heapq.heappop(pool)
if len(pool) == K:
ans = min(ans, ratio * sumq)
return float(ans)
864、获取所有钥匙的最短路径
题目
class Solution(object):
def shortestPathAllKeys(self, grid):
R, C = len(grid), len(grid[0])
# The points of interest
location = {v: (r, c)
for r, row in enumerate(grid)
for c, v in enumerate(row)
if v not in '.#'}
def neighbors(r, c):
for cr, cc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= cr < R and 0 <= cc < C:
yield cr, cc
# The distance from source to each point of interest
def bfs_from(source):
r, c = location[source]
seen = [[False] * C for _ in range(R)]
seen[r][c] = True
queue = collections.deque([(r, c, 0)])
dist = {}
while queue:
r, c, d = queue.popleft()
if source != grid[r][c] != '.':
dist[grid[r][c]] = d
continue # Stop walking from here if we reach a point of interest
for cr, cc in neighbors(r, c):
if grid[cr][cc] != '#' and not seen[cr][cc]:
seen[cr][cc] = True
queue.append((cr, cc, d+1))
return dist
dists = {place: bfs_from(place) for place in location}
target_state = 2 ** sum(p.islower() for p in location) - 1
#Dijkstra
pq = [(0, '@', 0)]
final_dist = collections.defaultdict(lambda: float('inf'))
final_dist['@', 0] = 0
while pq:
d, place, state = heapq.heappop(pq)
if final_dist[place, state] < d: continue
if state == target_state: return d
for destination, d2 in dists[place].items():
state2 = state
if destination.islower(): #key
state2 |= (1 << (ord(destination) - ord('a')))
elif destination.isupper(): #lock
if not(state & (1 << (ord(destination) - ord('A')))): #no key
continue
if d + d2 < final_dist[destination, state2]:
final_dist[destination, state2] = d + d2
heapq.heappush(pq, (d+d2, destination, state2))
return -1
871、最低加油次数
题目
题目
class Solution(object):
def minRefuelStops(self, target, startFuel, stations):
dp = [startFuel] + [0] * len(stations)
for i, (location, capacity) in enumerate(stations):
for t in range(i, -1, -1):
if dp[t] >= location:
dp[t+1] = max(dp[t+1], dp[t] + capacity)
for i, d in enumerate(dp):
if d >= target: return i
return -1
882、细分图中的可到达结点
题目
题目
class Solution(object):
def reachableNodes(self, edges, M, N):
graph = collections.defaultdict(dict)
for u, v, w in edges:
graph[u][v] = graph[v][u] = w
pq = [(0, 0)]
dist = {0: 0}
used = {}
ans = 0
while pq:
d, node = heapq.heappop(pq)
if d > dist[node]: continue
# Each node is only visited once. We've reached
# a node in our original graph.
ans += 1
for nei, weight in graph[node].items():
# M - d is how much further we can walk from this node;
# weight is how many new nodes there are on this edge.
# v is the maximum utilization of this edge.
v = min(weight, M - d)
used[node, nei] = v
# d2 is the total distance to reach 'nei' (nei***or) node
# in the original graph.
d2 = d + weight + 1
if d2 < dist.get(nei, M+1):
heapq.heappush(pq, (d2, nei))
dist[nei] = d2
# At the end, each edge (u, v, w) can be used with a maximum
# of w new nodes: a max of used[u, v] nodes from one side,
# and used[v, u] nodes from the other.
for u, v, w in edges:
ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))
return ans
973、最接近原点的k个点
题目
# 排序
class Solution(object):
def kClosest(self, points, K):
points.sort(key = lambda P: P[0]**2 + P[1]**2)
return points[:K]
# 分治法
class Solution(object):
def kClosest(self, points, K):
dist = lambda i: points[i][0]**2 + points[i][1]**2
def work(i, j, K):
if i >= j: return
oi, oj = i, j
pivot = dist(random.randint(i, j))
while i < j:
while i < j and dist(i) < pivot: i += 1
while i < j and dist(j) > pivot: j -= 1
points[i], points[j] = points[j], points[i]
if K <= i - oi + 1:
work(oi, i, K)
else:
work(i+1, oj, K - (i - oi + 1))
work(0, len(points) - 1, K)
return points[:K]
1046、最后一块石头的重量
题目
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
import heapq ## heapq库是专门处理最小堆的库
stones_heap = [-i for i in stones] ## 用取负数的办法弯道处理最大堆问题
heapq.heapify(stones_heap) ## 把list最小推结构化；时间复杂度是O(n)
while len(stones_heap) > 1: ## 当至少还有2块石头的时候
a = heapq.heappop(stones_heap) ## 取出质量最大的石头（因为是负数，所以值是最小）；时间复杂度是O(logn)，因为取出后还要用logn的时间保持堆结构
b = heapq.heappop(stones_heap) ## 在剩下的石头里取出质量最大的石头；时间复杂度是O(logn)
if a < b: ## 如果第一块石头比第二块重，那么把摩擦剩下的小石头放进堆里
heapq.heappush(stones_heap, a - b) ## 如果两块石头一样重，就都没有了
if stones_heap:
res = -stones_heap[0] ## 如果剩下石头，那么返回值是其质量
else:
res = 0 ## 如果不剩下石头，那么返回值是0
return res
1054、距离相等的条形码
题目
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
counter = collections.Counter(barcodes)
sorted_counter =sorted(counter.items(),key=lambda x : x[1], reverse=True)
n = len(sorted_counter)
res = [sorted_counter[0][0]] * sorted_counter[0][1]
i = 1
index = -1
for i in range(1,n):
for j in range(sorted_counter[i][1]):
if index == -1:
m = len(res)
index = m - 1
res.insert(index,sorted_counter[i][0])
index -= 1
return res
