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_id
                    assigned_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_id
                    assigned_workers.add(worker_id)
                    assigned_bikes.add(bike_id)
        return ans