与Dijkstra大战两个回合

来提每日一题 2024-08-31 12:40:01
北美求职 转码 近期找工作现状 LeetCode 每天59秒拿下每日一题 创作灵感 国区每日一题今日思路: 数字频率。统计每一个数位对应数字的出现频率,每个数字对总和的贡献为除当前数字外,该数位上所有数字频率和。这里可以额外维护一个总和数组,用于计算剔除当前数字的总和。 国际站每日一题今日思路: 首先把所有-1的边变成1,如果最小的更改方式无法满足,直接返回空集。记路径s-x-y-d,s表示起点,x和y表示要修改的一条-1边的端点,d表示终点,有如下式子:target=d2(s,x) + w + d1(y,d) 第一项用第二次跑的路径,第二项为需更改的值,第三项可以直接使用第一次跑路径的结果(前提是y必须在最短路径路由中),借助第一次跑的路径,相当于知道路由,上式变为target=d(s,x) + w + d(s,d) – d(s, y) 转换一下 w=target-d1(s,d)+d1(s,y)-d2(s,x)。这样在修改路径时,可以省去再跑一次Dijkstra。如果第二次跑完仍然存在小于target的路径,也返回空集。最后处理未被访问的边,将其任意赋值即可。看到这点个赞吧[喝奶茶R]

0 阅读:0
来提每日一题

来提每日一题

感谢大家的关注