Leetcode 1478. Allocate Mailboxes

题目解法：follow up

题目

解法：

首先一定要有这种思想就是他求的是mincost这个值，所以应该往动态规划上去想。而且这个问题的动态规划肯定是二维的，这张基本思想要有。 这里的动态规划也是从放置的最后一个mailbox出发来想，当最后一个mailbox放置的位置定了之后，那么最终的cost就是放置最后一个mailbox造成的cost和前面的相应的子问题造成的cost。也就是说我们要求解的是最后一个mailbox覆盖若干个house的cost以及他相应子问题cost的和的最小值。这样状态转移方程就比较清晰了 接下来需要考虑的问题就是，对于有若干个房子，一个mailbox的情况下，怎样放置这个mailbox比较好，这个比较容易想到，应该是所有房子位置的中位数，cost就是所有房子减去中位数的绝对值之和，我下面代码里面的写法本质也是一样的 这边要特别特别特别注意边界，一定要想的特别清楚，可以用特殊情况来考虑

class Solution: def minDistance(self, houses: List[int], k: int) -> int: def cal_cost(left,right): total_dis = 0 while left<right: total_dis += houses[right]-houses[left] left += 1 right -= 1 return total_dis houses.sort() cost = [[0]*len(houses) for _ in range(len(houses))] for i in range(len(houses)-1): for j in range(i,len(houses)): cost[i][j] = cal_cost(i,j) dp = [[float('inf')]*(len(houses)+1) for _ in range(k+1)] for i in range(k+1): dp[i][0] = 0 for i in range(1,k+1): for j in range(1,len(houses)+1): for m in range(j): #print('m,j,cost',m,j,cost(m,j-1)) dp[i][j] = min(dp[i][j],dp[i-1][m]+cost[m][j-1]) return dp[-1][-1]

follow up

一次面试面到的题目是，这个cost是距离的平方。当cost的距离的平方的时候，对于基础的情况，也就是一个mailbox，多个house的情况下，应该将mailbox放置在均值的情况下cost最小，这个推导可以通过将cost写出来然后求导为0实现。换句话说，对于一个mailbox的情况，最小的cost就是这些house位置的方差。其他的解法跟上面这道题目是一样的。 下面讲一下如何来O(1)时间计算一段stream of numbers。首先需要进行推导化简得到如下结论：

variance = 所有数的平方和-n*平均数的平方

完整代码如下：

class variance_calculator: def __init__(self): self._square_sum = 0 self._count = 0 self._sum = 0 def add(self, number): self._count += 1 self._sum += number self._square_sum += number * number def get_variance(self): curr_mean = self._sum / self._count curr_variance = self._square_sum - self._count * curr_mean * curr_mean return curr_variance vc = variance_calculator() nums = [1,2,3,4] for num in nums: vc.add(num) print(vc.get_variance())