Gas Station

7月 19 2014

这道题目，有点难。我没想出线性算法，写了一个朴素的n^2的，最后TLE了，感觉很像最大字段和，最后看了题解，也确实如此，但是可能还是理解不够透彻吧，想起那句名言：

What I can not create, I can not understand.

所以还是只停留在运用这些经典题目的算法上，而没有完全掌握这一类题。
题目是https://oj.leetcode.com/problems/gas-station/
思路比较朴素，转化为每一站gasi-costi的diff，那么照这样一个starti，使得sum(starti,j)>=0 for j=starti->(starti-1+n)%n, 这里可能有loop，要取模变回来，抽象成这样一个
等价问题是不难的，但是后面如何一次遍历，就确定这个starti是难的。

注意题目说了只有唯一解，这个很重要，后面强的性质是基于这个条件的。

性质1：如果sum(starti,i)加起来<0,且sum(starti,k)>=0 starti<=k<i, 则最后一个i之前一直到starti都不可能是解

证明: 因为sum(starti,i)<0, 若存在i<="k=0 (由已知得到，除掉加到i sum<0, 前面都="">=0,不然是加不到这里的)，则sum(k,i)=sum(starti,i)-sum(starti,k-1)<0, 因此
以k为起始的n个和里有一个必<0,所以k不可能是解。

性质2：如果sum(1,n)<0,则返回-1

哈哈，这个性质比较简单，我自己加的~~~

因此根据上述确立算法，如果起始开始，随意哪个作为起始都可以，加到第一次sum<0, 则前面的不可能是解，排除，记录解的变量j排除掉前面，j="i+1," sum="0，表示从新开始找一段和<0的index范围，排除掉之后" 最后退出loop时="" j记录的是前面几段负和的后一个index，同时看总和<0="" 的话返回-1，="" 总和都付不可能有节，因为任意一个必须n个sum="">0,且任意一个接都包含总和；否则，返回j,这是需要利用题目只有唯一解性质的，
因为后面可能还有节，但是题目说了唯一解，因此这个正确，但是可能最后一个元素 n 前面有段sum<0 那j岂不等于n+1越界了？这个不可能出现，因为如果出现，势必前面全是一段一段的sum<0, 总和<0 在另一个分支里面
O(∩_∩)O哈哈~

赋上代码，

int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        if(gas.size()==0) return -1;
        int n=gas.size();
        int sum=0,j=0,total=0;
        for(int i=0;i<n;i++)
        {
            sum+=gas[i]-cost[i];
            total+=gas[i]-cost[i];
            if(sum<0)
            {
                j=i+1;
                sum=0;
            }
        }
        if(total<0) return -1;
        else
            return j;
    }

另外赋上看的两个题解，
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/
http://blog.csdn.net/kenden23/article/details/14106137

Posted by richard爱闹 - 7月 19 2014
如需转载，请注明：本文来自 Richard

留言