Gas Station @LeetCode

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

	package leetcode;
	/**
	* Solution: i -> j if at somethere, like k, sum < 0, that means no point meet need from i to k.
	* Next start should be updated to k+1. Only one pass could find out result, O(n).
	* total >= 0 means there must a point could travel around the circuit once.
	* 只要k出现sum < 0 的情况，所有(i,k)的点都不可以作为起点. 把圈分成一段段的序列，正的，负的
	* 如果将全部油量累计起来，总是为正，那么一定能找到一个起点，使得可以走完一圈，也就是一定有解
	*
	* 一共维护 total总油量和 current的油量，sum, <0时候换点，置0
	*
	* There's also an O(n^2) brute force way. for every station i, if sum < 0, stops.
	*
	* See Reference for Mathematical Reasoning.
	*
	* Reference:
	* http://codeganker.blogspot.com/2014/03/gas-station-leetcode.html
	* http://leetcodenotes.wordpress.com/2013/11/21/leetcode-gas-station-
	* %E8%BD%AC%E5%9C%88%E7%9A%84%E5%8A%A0%E6%B2%B9%E7%AB%99%E7%9C%8B%E8%83%BD%E4%B8%8D%E8%83%BD%E8%B5%B0%E4%B8%80%E5%9C%88/
	*
	* @author jeffwan
	* @date Apr 4, 2014
	*/
	public class GasStation {
	public int canCompleteCircuit(int[] gas, int[] cost) {
	if (gas == null || cost == null || gas.length == 0
	|| cost.length == 0 || gas.length != cost.length) {
	return -1;
	}
	int sum = 0;
	int total = 0;
	int index = -1; // if sum > 0 always, 0 is the point, index should be -1 here.
	for (int i = 0; i < gas.length; i++) {
	int left = gas[i] - cost[i];
	sum += left;
	total += left;
	if (sum < 0) {
	sum = 0;
	index = i;
	}
	}
	return total >= 0 ? index + 1 : -1;
	}
	}

view raw GasStation.java hosted with ❤ by GitHub