[leetcode greedy]134. Gas Station
2024-10-07 15:47:09
There are N gas stations along a circular route, where the amount of gas at station i is gas[i]
.
You have a car with an unlimited gas tank and it costs cost[i]
of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1
题意:一个环路中有N个加油站,每个加油站有gap[i]的汽油,从加油站i到i+1耗油为cost[i],问一个油箱为无限大的汽车,能不能走完全程,能的话起点在哪
思路:如果环路中gas的总量比cost的总量多,那么肯定有一种方法可以让汽车跑完全程,首先什么情况下汽车不能跑完全程?比如从i出发到i+n时候,邮箱变为负值了,那么就可以把从i到i+n的节点全部滤掉
做法和求最大子列和一样
class Solution(object):
def canCompleteCircuit(self, gas, cost):
if not len(gas) or not len(cost) or sum(gas)<sum(cost):
return -1
balance,p= 0,0
for i in range(len(gas)):
balance += gas[i]-cost[i]
if balance < 0:
balance = 0
p = i+1
return p
最新文章
- Pro HTML5 Programming(Second Edition)2.Canvas API(2)
- PAT/进制转换习题集
- 解析json格式数据
- BZOJ4385 : [POI2015]Wilcze doły
- Java虚拟机学习记录
- HDFS介绍
- 1. while循环(当循环) 2. do{}while()循环 3. switch cose(多选一) 例子:当选循环下求百鸡百钱 用 switch cose人机剪刀石头布
- emacs org mode 中的标签全参考
- 转载robots.txt的学习
- 前台利用jcrop做头像选择预览,后台通过django利用Uploadify组件上传图最终使用PIL做图像裁切
- UITabBarController 笔记(三) UITabBarController 配合 UINavigationController 的使用
- hdu4745
- 更改Oracle实例的字符集
- Linux入门(六)ubuntu下vim编辑器安装与使用
- AWS ec2 vpn 搭建(20161014更新http://dl.fedoraproject.org/pub/epel/7/x86_64/e/epel-release-7-8.noarch.rpm)
- Python3基础 filter与lambda表达式配合 筛选出1-100之间的奇数
- hadoop-hdfs体系结构
- 使用Windows Server 2012+ 搭建VPN 简单 高效 稳定
- MySQL存储写入性能严重抖动分析
- Protobuf使用(一)