Leetcode加油站

Question

我偶然发现了一个来自leetcode的加油站问题。它可以在O(n)中求解，如果从i站开始，到j站时，没有足够的气体进入j+1站，那么从i到j的任何一个站都不能作为起点。在另一个职位中提供了类似的方法。

我认为这个事实适用于这样的假设:储气罐有无限的储气量。如果储罐有一个最大的存储量(即，如果sum + gasi > MAXN，那么sum = MAXN，否则每个站的sum += gasi )？在这种情况下，从i到j的任何一个站点都不能作为起点，这并不一定是事实。那么这个问题还有一个O(n)的解吗？

Answer 1

在这种情况下，从i到j的任何一个站点都不能作为起点，这并不一定是事实。

那不是真的。更多的限制不会导致更多的可能的起点，它会导致更少的。最佳候选起点仍然是原算法返回的点。如果在任何一个站你有满的汽油，而且在你能完成一个完整的循环之前就用完了汽油，那就没有解决办法了。

假设你在加油站的最后一个站是i站，i+k站的汽油用完了。也就是说，在I站和i+k站之间，当你到达的时候，你总是有至少0的汽油。所以，如果你用0汽油开始的话，你无论如何在i+k站就会用完。如果你从i+k站开始，或者在那之后的任何一个站，你仍然会耗尽从I站到i+k站的汽油。

因此，要解决这个问题，首先使用原来的算法找到最佳候选站，然后从产生的站点再进行第二轮，检查是否能够返回到起点。如果你做不到，就没有解决办法。

原问题的最佳解决方案确保在每个站都有尽可能多的气体。因此，如果这个起点导致一个成功的循环，比所有其他起点返回的原始算法也将工作。

编辑：

若要找到其他解决方案，请在canCompleteCircuit (未经测试)之后执行此操作：

int findOtherSolutions(vector<int> &gas, vector<int> &cost, int bestStation, int totalGasLeft) {
  int sum = totalGasLeft;
  int min = totalGasLeft;
  vector<int> solutions;
  solutions.push_back(bestStation);
  for(int i = bestStation-1; i != bestStation ; --i){
    sum -= gas[i]-cost[i];
    if(sum <= min){
      min = sum;
      solutions.push_back(i); 
    }
    if(i==0){
       i = gas.size();
    }
  }
  return solutions;
}

请注意，您必须修改canCompleteCircuit以获得剩余气体的总数：

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

Answer 2

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int size = gas.length;
        for(int i=0;i<size;i++) {
            gas[i] = gas[i] - cost [i];
        }

        //try to find the start index which has the max addition value
        int index = -1;
        int maxLeft = -1;
        int left = 0;
        for(int i=size -1;i>=0;i--){
            left +=gas[i];
            if(left > maxLeft) {
                index = i;
                maxLeft = left;
            }
        }

        if(left < 0) index = -1;
        return index;
    }
}