Commit077ba38

applewjg

committed

GasStation.java

Change-Id: I1fb2e4f04a15450f891e015461fad1b24358ad17

1 parent8633ea6 commit077ba38Copy full SHA for 077ba38

File tree

+28

-0

lines changed

+28

-0

lines changed

Lines changed: 28 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,28 @@`
	`1`	`+/*`
	`2`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Jan 3, 2015`
	`4`	`+ Problem: Gas Station`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: http://oj.leetcode.com/problems/gas-station/`
	`7`	`+ Notes:`
	`8`	`+ There are N gas stations along a circular route, where the amount of gas at station i is gas[i].`
	`9`	`+ 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.`
	`10`	`+ Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.`
	`11`	`+ The solution is guaranteed to be unique.`
	`12`	`+`
	`13`	`+ Solution: ...`
	`14`	`+*/`
	`15`	`+publicclassSolution {`
	`16`	`+publicintcanCompleteCircuit(int[]gas,int[]cost) {`
	`17`	`+intN =gas.length;`
	`18`	`+intres =0,min =gas[0] -cost[0],sum =min;`
	`19`	`+for (inti =1;i <N; ++i) {`
	`20`	`+sum +=gas[i] -cost[i];`
	`21`	`+if (sum <min) {`
	`22`	`+min =sum;`
	`23`	`+res =i;`
	`24`	`+ }`
	`25`	`+ }`
	`26`	`+returnsum >=0 ? (res +1) %N : -1;`
	`27`	`+ }`
	`28`	`+}`

Comments

(0)