V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
JasonLaw
V2EX  ›  程序员

怎么证明 LeetCode 134 Gas Station 这个算法的正确性?

  •  1
     
  •   JasonLaw · 2022-09-07 11:18:18 +08:00 · 1107 次点击
    这是一个创建于 812 天前的主题,其中的信息可能已经有所发展或是发生改变。

    对于Gas Station - LeetCode,我也想到了跟 NeetCode 同样的算法,但是我不知道怎么证明算法的正确性。

    我有以下疑问:

    1. 为什么 sum(gas) >= sum(cost)就表示一定存在那个 starting index ?
    2. 怎么证明要找的 starting index 就是 total 一直大于 0 的起点?
    第 1 条附言  ·  2022-09-07 12:00:21 +08:00

    对于疑问2,我现在已经理解了,有需要的人可以看一下Arpan Banejee的comment

    第 2 条附言  ·  2022-09-07 16:14:46 +08:00

    对于疑问1,我也理解了,以下视频或许对你有帮助。 https://youtu.be/rf66wlb9aNQ?t=482

    MoYi123
        1
    MoYi123  
       2022-09-07 11:55:58 +08:00
    简单说一下具体是怎么样的算法吧, 不然我还要去看个 15 分钟的视频.
    JasonLaw
        2
    JasonLaw  
    OP
       2022-09-07 12:02:01 +08:00
    @MoYi123 #1 我希望帮助的人去看一下视频的,这样子才能真正理解那个算法,所以没有贴出代码。

    不过还是谢谢啦。
    jdz
        3
    jdz  
       2022-09-07 15:14:03 +08:00
    考虑一个数组[a, b, c, d...] 有正有负, 加起来为正数, 与加油站油量 - 消耗量对应. 所以该数组正数对应 加油站油量大于消耗量.
    由于数组为正, 必然存在一个最大子数组和为正, 最大子数组左边(如果存在) 连续的数的和必然为小于等于 0, 同理右边 反证法很容易.
    以上想清楚了, 一切就很轻松理解了
    核心既是 `最大子数组的左边 连续子数组必然小于等于 0, 右边同理`
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1022 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 20:23 · PVG 04:23 · LAX 12:23 · JFK 15:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.