Gas Station [leetcode] 的两种解法

由于gas总量大于cost总量时，一定可以绕所有城市一圈。

第一种解法：

假设一开始有足够的油，从位置i出发，到位置k时剩余的油量为L(i,k)。

对任意的k，L(i,k)根据i的不同，只相差常数。

我们只需要找到最小的L(0, k)对应的k，k+1为所求。

代码如下：

    int canCompleteCircuit(vector
  
    &gas, vector
   
     &cost) { int start = 0; int curGas = 0, minGas = 0, totalGas = 0; for (int i = 0; i < gas.size(); i++) { int temp = gas[i] - cost[i]; curGas += temp; totalGas += temp; if (minGas > curGas) { start = i + 1; minGas = curGas; } } if (totalGas >= 0) return start % gas.size(); else return -1; }
   
  

如果L(i,k) < 0，则从i和k之间所有的位置都不能到k

所以从k+1的位置从0开始找

    int canCompleteCircuit(vector
  
    &gas, vector
   
     &cost) { int start = 0; int curGas = 0, totalGas = 0; for (int i = 0; i < gas.size(); i++) { int temp = gas[i] - cost[i]; curGas += temp; totalGas += temp; if (curGas < 0) { start = i + 1; curGas = 0; } } if (totalGas >= 0) return start % gas.size(); else return -1; }