当前位置:   article > 正文

[LeetCode] Gas Station_leetcode gas station

leetcode gas station
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.


  1. public class Solution {
  2. public int canCompleteCircuit(int[] gas, int[] cost) {
  3. if (gas == null || gas.length < 1 || cost == null || cost.length != gas.length) {
  4. return -1;
  5. }
  6. int len = gas.length;
  7. int costTotal = 0;
  8. int gasTotal = 0;
  9. for (int i = 0; i < len; i++) {
  10. if (gas[i] >= cost[i]) {
  11. costTotal = 0;
  12. gasTotal = 0;
  13. for (int j = 0; j < len; j++) {
  14. int index = (j + i) % len;
  15. costTotal += cost[index];
  16. gasTotal += gas[index];
  17. if (gasTotal < costTotal) {
  18. break;
  19. }
  20. }
  21. if (costTotal <= gasTotal) {
  22. return i;
  23. }
  24. }
  25. }
  26. return -1;
  27. }
  28. }


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/493506
推荐阅读
相关标签
  

闽ICP备14008679号