Leetcode 134. Gas Station ½âÌⱨ¸æ

Leetcode 134. 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.

---

·ÖÎö

×î¼òµ¥µÄ×ö·¨¾ÍÊDZéÀúÒ»´Îÿ¸ö×÷ΪÆðµã,¸´ÔÓ¶ÈÊÇO(n^2).

ÏÖÔÚ¿¼ÂÇÖ»ÐèÒª±éÀúÒ»´ÎµÄ·½·¨
¾­¹ýÿ¸öÓÍÕ¾¶Ô³µÀ´½²¾ÍÊÇ2ÖÐÇé¿ö¼ÓÁËÓÍ»òÕߺÄÁËÓÍ,Õâ¿ÉÒÔÓÃgas[i]-cost[i]À´·´Ó³.ÓÚÊÇÎÒÃǹ¹ÔìÊý×édetaGas[i] = gas[i] - cost[i].±íʾ¾­¹ýÒ»¸öÓÍÕ¾¶ÔÓÍÁ¿µÄÓ°Ïì.
ÏÖÔÚ¿¼ÂÇ´ÓÓÍÕ¾i³ö·¢Ò»Ö±µ½ÓÍÕ¾p-1ÓÍÏäµÄÓÍÒ»Ö±ÊÇ>=0, µ½ÁËpÓÍÏäÓÍ<0,
¼´:sum £½¡¡detaGas[i]+detaGas[i+1]+detaGas[i+£²]¡­+detaGas[p-1]>=£°
sum £½¡¡detaGas[i]+detaGas[i+1]+detaGas[i+£²]¡­+detaGas[p]<£°

ÄÇô¿ÉÒÔÖªµÀdetaGas[i]>=0, Èç¹û´Ói+1µ½p-1Ö®¼ä³ö·¢¸ü²»¿ÉÄܵ½p,ÒòΪÉÙ¼ÓÁËiµÄÓÍ.ÄÇôÎÒÃÇÖ»ÐèÒª¿¼ÂÇ´Óp³ö·¢¾ÍºÃÁË,ÕâÑùÖ»ÐèÒª±éÀúÒ»´ÎÊý×é¾Í¿ÉÒԵõ½´ð°¸.

¼ÙÉèÊý×édaraGas±»·ÖΪ3¶Î
sum1 = detaGas[0]+detaGas[1]+¡­..+detaGas[i] <¡¡0;
sum2 = detaGas[i+1]+detaGas[i+2]+¡­..+detaGas[k] < 0;
sum3 = detaGas[k+1]+detaGas[1]+¡­..+detaGas[l-1] >= 0;
(Ò»¶¨×îºóÒ»¶ÎµÄÇ°ÃæµÄºÍ¶¼ÊÇСÓÚÁãµÄ)

´Ók+1ÄÜ»ØÀ´µÄÌõ¼þÊÇ ÒªÄÜ´Ó0×ßµ½k,´Ëʱ¿ÉÒÔ½èÖú´Ók+1µ½l-1ÔÜϵÄÓÍ,¼´Âú×ã sum3+sum1+sum2 >= 0¾Í¿ÉÒÔ»ØÀ´.

---

AC´úÂë

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int l = gas.size();
        if (l <= 0) return -1;

        int s = 0;
        int curSum = 0;
        int b = 0 ,total = 0;
        for (int i = 0; i < l; ++i) {
            curSum += (gas[i] - cost[i]);
            total += (gas[i] - cost[i]);

            if (curSum >= 0) {

            } else {
                b = i+1;
                curSum = 0;
            }
        }

        if (total >= 0) return b;
        else return -1;
    }
};