Floyd已经很优秀,但是给它优化一下更好

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

0 阅读:0
来提每日一题

来提每日一题

感谢大家的关注