题目描述
一.原本暴力算法
最初的想法是：先比较gas数组和cost数组的大小，找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点，就不能作为起始点)。当找到过后，再去依次顺序跑一圈，如果剩余的油为负数，再去寻找下一个满足条件的起始站点。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int index = -1; //定义初始起点
int left = 0; //定义剩余油量
bool flag = false;
int n = gas.size();
//寻找起始位置
for(int i = 0;i<n;i++)
{
if(gas[i] < cost[i])
{
continue;
}
else{
index = i;
int j = index;
int count = 0;
cout<<"index="<<index<<endl;
while(true)
{
j = j%n;
cout<<"j="<<j<<endl;
if(left < 0)
{
left = 0;
break;
}
if(count == n)
{
flag = true;
return index;
}
left = left + gas[j] - cost[j];
cout<<"left="<<left<<endl;
count++;
j++;
}
}
}
//判断
if(flag)
{
return index;
}else{
return -1;
}
}
};
但是代码最后超时了！！
时间复杂度是O(N^2) 因为循环遍历寻找起始站点，找到过后再去循环遍历走一圈是O(N^2）的时间复杂度！
巧妙思路算法二能通过的
转子大佬的代码。
情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum = 0; int min = INT_MAX; // 从起点出发，油箱里的油量最小值 for (int i = 0; i < gas.size(); i++) { int rest = gas[i] - cost[i]; curSum += rest; if (curSum < min) { min = curSum; } } if (curSum < 0) return -1; // 情况1 if (min >= 0) return 0; // 情况2 // 情况3 for (int i = gas.size() - 1; i >= 0; i--) { int rest = gas[i] - cost[i]; min += rest; if (min >= 0) { return i; } } return -1; } };在这里时间复杂度O(N)
空间复杂度O(1)没有开辟新的空间
二.贪心算法
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};时间复杂度O(N)
