本文共 928 字,大约阅读时间需要 3 分钟。
这题不友好啊,,需要找规律。按照提示的部分来思考,假设当前我只有一个邮箱,那没增加一个房子的情况下,如当前有x,y,z三个房子,邮箱放在y位置,x的位置是start;每多一个新的房子w,则总的距离增加就是w到y的距离。因为此时要么中心换为z,要么还是y,但是总的增加量还是不变的。(比如x->y:l1,y->z:l2,z->w:l3, 当只有x,y,z三个 houses的时候,距离为l1+l2, 增加w点后,不换中心,增加的距离是l2+l3, 换中心,则y->z的距离l2需要加入,w->z的距离l3的距离也需要加入,增加的量还是l2+l3。所以,增加的距离为w的index与start相加/2,(index + start)/2之后得到的坐标到index的距离。)好了,由此开始推断,前面的start到index里只放一个,剩下的使用recursion迭代。并在此过程中寻找最小值。
class Solution: def minDistance(self, house: List[int], k: int) -> int: if len(house) == k:return 0 house.sort() @functools.lru_cache(None) def recursion(start, k): if k >= (len(house) - start): return 0 res = float('inf') addlength = 0 for i in range(start, len(house)): addlength += house[i] - house[(start+i)//2] res = min(res, addlength + recursion(i+1, k-1)) return res return recursion(0,k)
转载地址:http://eijii.baihongyu.com/