@@ -0,0 +1,2166 @@
+package cc150;%0A%0A/*%0A * There are N gas stations along a circular route, where the amount of gas at station i is gas%5Bi%5D.%0A%0AYou have a car with an unlimited gas tank and it costs cost%5Bi%5D 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.%0A%0AReturn the starting gas station's index if you can travel around the circuit once, otherwise return -1.%0A%0ANote:%0AThe solution is guaranteed to be unique.%0A %0A * %0A */%0Apublic class GasStation_greedy %7B%0A    public int canCompleteCircuit(int%5B%5D gas, int%5B%5D cost) %7B%0A        if (gas == null %7C%7C cost == null %7C%7C gas.length == 0 %7C%7C cost.length == 0 %7C%7C gas.length != cost.length)%0A            return -1;%0A%0A        int len = gas.length;%0A        int delta = 0;%0A        int total = 0;%0A        int start_station = -1;%0A        %0A        for (int i=0; i%3Clen; i++) %7B%0A        %09delta += gas%5Bi%5D - cost%5Bi%5D;%0A        %09total += gas%5Bi%5D - cost%5Bi%5D;%0A        %09if (delta %3C 0) %7B%09%09// if not enough for next station, reset the starting point%0A        %09%09start_station = i;  // last station failed%0A        %09%09delta = 0;%0A        %09%7D%0A        %7D%0A        %0A        if (total %3C 0) return -1;%09// no way to circle%0A        else return start_station + 1;%09// because the logic above, %0A        %09%09%09%09%09%09%09// after start_station, all has surplus and enough total to circle%0A    %7D%0A%09%0A%09%0A%09// Brute-force, TLE%0A    public int canCompleteCircuitSlow(int%5B%5D gas, int%5B%5D cost) %7B%0A        if (gas == null %7C%7C cost == null %7C%7C gas.length == 0 %7C%7C cost.length == 0 %7C%7C gas.length != cost.length)%0A            return -1;%0A            %0A        int len = gas.length;%0A        int curgas = 0, index;%0A        %0A        for (int i=0; i%3Clen; i++) %7B%0A            curgas = gas%5Bi%5D;%0A            index = i;%0A            %0A            while (curgas %3E= cost%5Bindex%5D) %7B%0A                // reach next station%0A                curgas -= cost%5Bindex%5D;%0A %0A                index++;%0A                index = index %25 len;%0A                curgas += gas%5Bindex%5D;%0A          %0A                if (index == i) %7B   // if we can reach starting point, return success%0A                    return i;%0A                %7D%0A            %7D%0A        %7D%0A        %0A        return -1;%0A        %0A    %7D%0A%7D%0A

Add new version