LeetCode--Gas Station（加油站）python

65 阅读 0 评论 43 点赞

我是靠谱客的博主冷酷宝马，最近开发中收集的这篇文章主要介绍LeetCode--Gas Station（加油站）python，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

给定一组站点，每个站点包含两个数据gas[i]和cost[i]，分别为该站点可加的油量和跑到下一站点的油量。这些站点组成一个环，求从哪个站点出发可以跑完整个环，若不能跑完整个环，则返回-1.

解题思路：

1.对站点进行遍历，从每个站点出发一次，看从该站点出发能不能跑完整个环。该思路会超时。

2.考虑该问题的规律和特征。有两个特征：a.若sum(gas)<sum(cost)，则返回值为-1. b.若从0-n的sum(gas)<sum(cost),则n以前的所有站点都不能作为起始站点。

代码（Python）：

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
else:
res = 0
station = 0
for i in range(len(gas)):
if res+gas[i]-cost[i]<0:
station = i+1
res = 0
else:
res = res+gas[i]-cost[i]
return station