前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Gas Station/加油站

[Leetcode][python]Gas Station/加油站

作者头像
蛮三刀酱
发布2019-03-26 15:43:45
6290
发布2019-03-26 15:43:45
举报
文章被收录于专栏:蛮三刀的后端开发专栏

题目大意

Gas Station

解题思路

贪心法。但其实需要证明,证明详见: http://bookshadow.com/weblog/2015/08/06/leetcode-gas-station/ 看懂证明,才能看懂代码

结论1:若从加油站A出发,恰好无法到达加油站C(只能到达C的前一站)。则A与C之间的任何一个加油站B均无法到达C。

结论2:若储油量总和sum(gas) >= 耗油量总和sum(cost),则问题一定有解。

代码

代码语言:javascript
复制
class Solution:
    # @param {integer[]} gas
    # @param {integer[]} cost
    # @return {integer}
    def canCompleteCircuit(self, gas, cost):
        start = sums = 0
        for x in range(len(gas)):
            sums += gas[x] - cost[x]
            if sums < 0:
                start, sums = x + 1, 0
        return start if sum(gas) >= sum(cost) else -1
代码语言:javascript
复制
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        if sum(gas) < sum(cost):
            return -1
        min_sum, min_index, total = 0, 0, 0

        for i in range(len(gas)):
            print '----'
            total += gas[i] - cost[i]
            if min_sum > total:
                print 'gg'
                min_sum = total
                min_index = i + 1
            print i, 'total:', total, 'min_sum:', min_sum, 'min_index:', min_index

        if total < 0:
            return -1 
        else:
            return min_index

总结

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年11月17日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档