Floyd已经很优秀，但是给它优化一下更好
来提每日一题
2024-07-30 16:32:44
校招找工作实录 转码 每日一题 北美求职 LeetCode 每天59秒拿下每日一题 近期找工作现状
国际站每日一题今日思路：
优化Floyd。对于每个点求出距离表，判断在给定限制内到达点数，找到符合要求的答案。Floyd是对每个点跑三角形法则，影响三角形法则的是边，这里可能为稀疏图，不妨对边排序然后对每个点跑三角形法则(其实算法类似Prim)，若为稀疏图时间复杂度为n方，稠密图时间复杂度为n三次方。
国区每日一题今日思路：
贪心。若分区值最小，即使得两数组的最小值最大，最大值最小；等价于尝试从数组每个可以插隔板位置划分，这样二者差值最小。将数组排序(有很多排法)，模拟插隔板计算全局最优。看到这点个赞吧[喝奶茶R]
0
阅读：0
