Leetcode 1057. Campus Bikes (python)

题目

解法1：暴力排序

首先理解这道题目一定要到位。不是说从bike去找worker，也不是从worker去找bike。如果一开始陷入了这种错误思路，就会想到BFS，把题目搞得很复杂。
正确的理解是这样的，找到距离最近的pair，如果距离最近的pair有多个，那么先要选小的worker_id，比如worker1和worker2和bike1距离一样，那么要选worker1.然后如果worker1和bike1还有bike2距离都最小，那么要选bike1

那么可以都一个list，list里面的元素是一个3维tuple，第一维代表距离，第二维代表worker_id，第三维代表bike_id。然后对这个list按照距离，worker_id，bike_id这样的优先顺序进行排序即可

class Solution:def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:dis_pairs = collections.defaultdict(list)for i,worker in enumerate(workers):for j,bike in enumerate(bikes):d = abs(bike[0]-worker[0])+abs(bike[1]-worker[1])dis_pairs[d].append((i,j))#print(dis_pairs)dis_list = [key for key in dis_pairs.keys()]heapq.heapify(dis_list)ans = [0]*len(workers)assigned_workers = set()assigned_bikes = set()while len(assigned_workers)!=len(workers):d = heapq.heappop(dis_list)#print(d)for pair in dis_pairs[d]:worker_id = pair[0]bike_id = pair[1]if worker_id not in assigned_workers and bike_id not in assigned_bikes:ans[worker_id]=bike_idassigned_workers.add(worker_id)assigned_bikes.add(bike_id)return ans

解法2：heap代替暴力排序

将距离放入minheap中，然后构建一个map，map的key是距离，value是对应worker_id和bike_id构成的pair。这里要注意，需要先遍历worker_id，然后再遍历bike_id，这样就可以保证距离相同情况下，worker_id小的在前面。其次worker_id相同的情况下，bike_id小的在前面

class Solution:def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:dis_pairs = collections.defaultdict(list)for i,worker in enumerate(workers):for j,bike in enumerate(bikes):d = abs(bike[0]-worker[0])+abs(bike[1]-worker[1])dis_pairs[d].append((i,j))dis_list = [key for key in dis_pairs.keys()]heapq.heapify(dis_list)ans = [0]*len(workers)assigned_workers = set()assigned_bikes = set()while len(assigned_workers)!=len(workers):d = heapq.heappop(dis_list)for pair in dis_pairs[d]:worker_id = pair[0]bike_id = pair[1]if worker_id not in assigned_workers and bike_id not in assigned_bikes:ans[worker_id]=bike_idassigned_workers.add(worker_id)assigned_bikes.add(bike_id)return ans