专栏首页蛮三刀的后端开发专栏[Leetcode][python]Gas Station/加油站

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

题目大意

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),则问题一定有解。

代码

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
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

总结

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II

    我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。

    后端技术漫谈
  • 面试常问的小算法总结

    需要说明的是,由于算法的代码实现主要注重思路的清晰,下方有代码实现的文章主要以Python为主,Java为辅,对于Python薄弱的同学敬请不用担心,几乎可以看...

    后端技术漫谈
  • [Leetcode][python]Sort List/排序链表

    https://leetcode-cn.com/problems/sort-list/description/

    后端技术漫谈
  • RxJS学习笔记之Subject

    总的来说,Subject 既是能够将值多播给多个观察者的特殊的可观察对象,因为可以添加观察者并使用 subscribe 方法来接收值;又是观察者,因为它有 ne...

    Theo Tsao
  • Kubernetes相关组件监控指标采集

    线上部署了kuberneter集群环境,需要在zabbix上对相关组件运行情况进行监控。kuberneter组件监控指标分为固定指标数据采集和动态指标数据采集。...

    洗尽了浮华
  • ABAP内表数据和JSON格式互转

    注:json字符串格式如:jsonstr = '[ {flag: "0",message: "abc"},{flag: "1",message: "abcddd...

    matinal
  • 探索VR设备衍化的终极意义,让交互设备回归为你的双手

    VRPinea
  • 将Spring Boot应用程序部署到Bluemix

    在之前的博客文章中,我介绍了如何通过Swagger在Spring Boot应用程序中记录REST API。下面我将介绍如何将这些应用程序作为Docker容器部署...

    FLYMOTH
  • 腾讯课堂 IMWeb 七天前端求职提升营 Day 7

    本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中,所推送的面试题目及编程练习的一次汇总,期间还包括三次直播课的分享,均由腾讯导师给大家讲解,该系列博...

    Nian糕
  • Oracle RMAN 清除归档日志

          在开发环境及UAT环境经常碰到需要清除归档日志的情形,对于这个问题方法有很多。可以直接使用rm方式清除归档日志,也可以使用find命令来查找符合条件...

    Leshami

扫码关注云+社区

领取腾讯云代金券