AlgoPressAppearance
0134-加油站
https://leetcode.cn/problems/gas-station
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
提示:
- gas.length == n
- cost.length == n
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
思路:暴力法
尽量选择加油多的站和耗油少的站作为出发点。 我们将加油和耗油组合，当时正数时检查是否完成循环。 时间复杂度 O(n^2) 会超时
参考代码
csharp
public class Solution {
private bool CheckCircuit(int[] gas, int[] cost, int index){
int sum = 0;
for(int i=index; i<gas.Length; i++){
sum += gas[i];
sum -= cost[i];
if(sum < 0){
return false;
}
}
for(int i=0;i<index; i++){
sum += gas[i];
sum -= cost[i];
if(sum < 0){
return false;
}
}
return true;
}
public int CanCompleteCircuit(int[] gas, int[] cost) {
int[] calc = new int[gas.Length];
//是负数的不可能是起点
for(int i=0; i<gas.Length; i++){
calc[i] = gas[i]-cost[i];
if(calc[i] >= 0){ //选择一个正数作为起点
if(CheckCircuit(gas,cost,i)){
return i;
}
}
}
return -1;
}
}
思路2：贪心
- 首先加油站和消耗的差值为负数的不能选择出发点，我们应该尽量选择剩余油量多的作为出发点。
- 当加油量是正数的时候，我们累计差值和，一旦小于0，说面前面选择的出发点一直到当前的点，都不能作为出发点，因为前面累加的都不够，那后续节点就更不够了。 要选择小于0的下一个节点做为开始节点。
- 中途我们记录邮箱为整数的计数器，当计数器>=n的时候，说明跑了一圈了，计数器在遇到邮箱小于0的时候重新计数。
- 同时还记录所有的跑动的次数，如果跑了两圈，说明前面邮箱会不停的置空，则不能跑完
csharp
public class Solution {
int total = 0; //一共跑的数量
int positive = 0; //油箱为非负数的数量
public int CanCompleteCircuit(int[] gas, int[] cost) {
int n = gas.Length;
int sum = 0;
int i = 0;
int startIndex = 0;
while(true){
sum = sum + gas[i] - cost[i];
//Console.WriteLine("sum = {0}, i={1}",sum,i);
if(sum >= 0){
positive++;
}
else{
positive=0;
sum=0;
startIndex = (i + 1) % n;
}
total++;
if(positive >= n){
return startIndex;
}
if(total / n >= 2){
return -1;
}
i=(i+1)%n;
}
}
}
另一种写法，从第一个加油站开始，如果发现有油箱不够用，则从不够用的油箱开始，循环下一个，直到末尾
csharp
public class Solution {
public int CanCompleteCircuit(int[] gas, int[] cost) {
int n = gas.Length;
int i=0;
while(i<n){
int count = 0;
int rest = 0;
while(count < n){
int j = (i + count) % n;
rest = rest + gas[j] - cost[j]; //循环计算油箱剩余数量
if(rest < 0){
break;
}
count++;
}
if(count == n){ //循环到结尾了
return i;
}
else{
i = i + count+1;
}
}
return -1;
}
}