6

leetCode解题报告之Gas Station

 3 years ago
source link: https://blog.csdn.net/ljphhj/article/details/22150903
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
leetCode解题报告之Gas Station_快乐de胖虎-CSDN博客

题目：

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.

Note:
The solution is guaranteed to be unique.

分析：

题意大概是说，你有一辆车，这辆车有一个可以无限装油的油箱，然后有个圆环，圆环上有N个加油点，加油点 i 所能加油的量用gas[i] 来表示，而你从 加油点 i  开车到 加油点 i+1 中间这段路途，你要消耗的油量 用 cost[i] 来表示。

最后你要绕圆圈从起点开始，最后再转回到起点，让你求出起点的位置，并返回起点的下标，如果找不到这样的起点，那么返回-1

解题思路：

这种题目的话，我能想到的就是简单的解法，你for循环，每个加油点都做起点。

如： 加油点 i 作为起点

1、初始化：油箱 tank = 0;

2、从加油点 i  到 加油点 gas.length -1 ，判断其中是否有 tank < cost[i] 的情况，如果有的话，表示这车油已经不足以支撑你从 加油点 i  到 加油点 i+1 这段路途了

3、如果前面第2步 顺利走到了加油点 gas.length -1, 那么要走到起点（加油点 i），就和第2步一样了，从 加油点 0 到加油点 i，判断其中是否有 tank < cost[i] 的情况，如果有的话，表示这车油已经不足以支撑你从 加油点 i  到 加油点 i+1 这段路途了

4、如果最后 回到了起点 则这个 i 便是题目要求的 满足条件的起点，返回它， 否则继续找下一个 加油点 作为起点的情况

5、全部加油点找完还没有满足条件的加油点时，返回-1

图解：

AC代码：


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK