需要着重理解为啥下一点可以从i+1开始
classSolution {
public:
intcanCompleteCircuit(vector &gas, vector &cost) {
vector diff;
for(inti=0;i<(int)gas.size();i++)
diff.push_back(gas[i]-cost[i]);
intsum=0;
intstart=0;//标记开始的位置
intend=0;
for(inti=0;i<2*diff.size();i++) //由于是环路,最后一个可以走至此位置
{
if(sum<0) //表示到达下一点(i+1)的剩余油量,如果大于等于0表示能够当前状态能够支撑到下一点
{
sum=diff[i%diff.size()];
start=i;
end=i;
}
else
{
sum+=diff[i%diff.size()];
end=i;
if(end-start>=diff.size())
returnstart;
}
}
return-1;
}
};
// 解有且只有一个,所以只有从起点start处出发 // 才可以走完全程。这也指出了一个事实:那就是 // 从另外的起点出发,走到start-1时无法走下一步 // 到start,所以当出现本次剩余汽油量<0时,下一步 // 就有可能是真正的起点,至于是不是,要看总得汽油 // 量是不是大于0 public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if (gas == null || cost == null || gas.length <= 0 || cost.length <= 0) return -1; int index = -1, remain = 0, total = 0; for(int i = 0; i < gas.length; i++){ total += gas[i] - cost[i]; remain += gas[i] - cost[i]; // 如果本次剩余<0,说明不能由i走到i+1 if(remain < 0){ remain = 0; index = i; } } return total >= 0 ? index + 1 : -1; } }
思路:
(1)枚举法:枚举从第一个位置开始,直到最后一个位置。
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int n = gas.size();
int j = 0;
int rest = 0;
for(int i = 0; i < n; i++){
j = i;
rest = gas[j] - cost[j];
while((j+1)%n != i && rest >= 0){
j = (j+1)%n;
rest += gas[j] - cost[j];
}
if((j+1)%n==i&&rest>=0) return i;
}
return -1;
}
评论中的其它思路:
思路1(牛客923):设置一个start,一个end
思路2(食肉大灰兔):
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
vector<int> sub(gas.size());
for (int i = 0; i < gas.size(); ++i) {
sub[i] = gas[i] - cost[i];
}
int leftOver = 0;
int sum = 0;
int start = 0;
for (int j = 0; j < gas.size(); ++j) {
leftOver += sub[j];
sum += sub[j];
if (sum < 0) {
start = j + 1;
sum = 0;
}
}
if (leftOver < 0) {
return -1;
}
return start;
}
};
class Solution { public: // 贪心算法 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int start = -1; int total = 0,sum = 0; for(int i=0;i<gas.size();i++) { sum += gas[i] - cost[i]; total += gas[i] - cost[i]; if(sum < 0) // 不能达到该点i,则start到i-1之间的点都不能作为有效起点,将i作为新的起始点 { sum = 0; start = i; } } return total >= 0 ? start+1 : -1; } };
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int left = 0;//邮箱中剩余的油量 for(int i = 0; i < gas.size(); ++i)//起点 { for(int j = 0; j < gas.size(); j++)//向前走加油站的个数 { //每经过一个加油站后,邮箱中的油=之前剩余的油量+加油站的油量-本次消耗的油量 left = left + gas[(i+j)%gas.size()] - cost[(i+j)%gas.size()]; if(left < 0)//如果剩余油量为负数,换下一期起点重新开始 { left = 0; break; } if(j == gas.size() - 1)//如果当前起点能走完所有加油站 return i;//返回当前起点 } } return -1;//所有起点都不满足,返回-1 } };
public int canCompleteCircuit(int[] gas, int[] cost) { /* 解法依据1:如果从 A 出发到 B 无法到达,那么从A到B间任意站出发都到不了B * 因为:1. 如果A下一站就是B,那么代表A站的油量无法到达B,下一次尝试从B站出发 * 2. 如果A下一站不是B, 那么A能够到A+1,不能到B,说明deltaA = gas[A]-cost[A] >0 * A到B最后剩余油量是 delta < 0, 从A+1出发最后油量 delta` = delta - deltaA < delta < 0 * 依次类推可以得到,A出发无法到B,那么A和B间任意站出发都无法到B * 所以每次判断无法到达后,下一次尝试从B站开始 * 解法依据2:如果一个数组的总和非负,那么一定可以找到一个起始位置,从他开始绕数组一圈,累加和一直都是非负的 * 证明 -> (待完成,还没证明成功,查下资料先) * 可以这样理解,从依据1,我们知道已经判断过的无法到达的点将数组分段,而且每一段最后的剩余油量 * 总是小于0的,那么最后一次出发的站点可以到达下标0的站点的话,那么不用再往后判断了, * 只要看此时剩余的油量是否大于从0到该站点的油量(之前每一段所欠的油量)即可 */ // 历史亏欠油量 int left = 0; // 当前剩余总油量 int tank = 0; // 当前出发站点 int start = 0; for(int i=0; i<gas.length; i++){ // 从i到i+1(或者从n到0)的净剩油量 int delta = gas[i] - cost[i]; // 油箱剩余油量(之前站点的剩油+当前一次净剩油) tank += delta; // 油量不足,无法到达i+1,下一次从i+1开始尝试 if(tank<0){ // 记录无法到达的亏欠油量 left += tank; // 重置记录,清零油箱剩油,起始站点为i+1 tank = 0; start = i+1; } } // 如果到达0时候剩余油量能满足从0到i的亏欠油量 //(之前能到达的剩油油更多还是能到达,之前不能到达的油也够了) // 就能到达 return left + tank < 0 ? -1 : start; }
idea:
code
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int ans = 0; int total = 0; int gas_now = 0; int n = gas.size(); for (int i = 0; i < n; i++){ gas_now += gas[i] - cost[i]; total += gas[i] - cost[i]; if (gas_now < 0){ gas_now = 0; ans = i+1; } } return total>=0?ans:-1; } };
```
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if(gas.length<1 || cost.length<1 || gas.length!=cost.length) return -1; int left=0; int index=0; for(int i=0;i<gas.length;i++){ left+=gas[i]-cost[i]; if(left<0) { left=0; i=index++; continue; } if(i==gas.length-1) i=-1; if(i==index-1) return index; if(index>=gas.length) break; } return -1; } }
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int start(0);int store(0);int tank(0); for(int i(0);i != gas.size();i++) { if((tank += gas[i] - cost[i]) < 0) { store += tank; start = i + 1; tank = 0; } } return (tank + store >= 0 ? start:-1); } };
import java.util.*; public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; //考虑从每一个点出发 for (int i = 0; i < n; i++) { int j = i; int remain = gas[i]; //当前剩余的油能否到达下一个点 while (remain - cost[j] >= 0) { //减去花费的加上新的点的补给 remain = remain - cost[j] + gas[(j + 1) % n]; j = (j + 1) % n; //j 回到了 i if (j == i) { return i; } } } //任何点都不可以 return -1; } }
/** * * @param gas int整型一维数组 * @param cost int整型一维数组 * @return int整型 */ public int canCompleteCircuit (int[] gas, int[] cost) { boolean flag = false; int result = 0; for (int i = 0 ; i < gas.length; i ++){ result = gas[i] - cost[i]; if (result >= 0) { flag = true; for (int j = (i + 1) % cost.length; j != i; j = (j + 1) % cost.length) { //余油量 + 当前加油量 - 要消耗的油量 result = result + gas[j] - cost[j]; if (result < 0) { // 这条路走不通, flag = false; } } if (flag) { return i; } } } return -1; }方法二: 上面可以知道,在整个二层循环中,result 的值一直是全部的 gas[i] - cost[i] 。所以可以优化上面的代码,使时间复杂度将至 O(n)
public int canCompleteCircuit (int[] gas, int[] cost) { // 表示循环后两个数组值的相减值,如果最终值 < 0 表示没有答案, 否则返回index + 1 的节点位置 int result = 0; // 表示当前节点是否 > 0 , 如果小于0, 表示已经选定的index + 1 不是起始点,重置sum 和 index 的值。 int sum = 0; // 表示目前的目标加油站下标的 前一个位置, 所以index 的初始值 = 0 - 1 = -1. // 如此定义是为了方便后面的 当前值 sum < 0 时, 直接领 index = i, 即index 为目标起点的前一个节点 int index = -1; for (int i = 0 ; i < gas.length; i ++){ result += gas[i] - cost[i]; sum += gas[i] - cost[i]; if (sum < 0) { sum = 0; index = i; } } return (result >= 0 ? index + 1 : -1); }
class Solution { public: /** * * @param gas int整型vector * @param cost int整型vector * @return int整型 */ int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { // write code here int total = 0, last_fail = -1; for(int i=0, cur=0; i<gas.size(); ++i){ cur += gas[i]-cost[i]; total += gas[i]-cost[i]; if(cur < 0) cur = 0, last_fail = i; } return total>=0 ? last_fail+1 : -1; } };
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int i = 0; i < gas.length; i++) {
//计算节点后面的累计汽油
int number = 0;
for (int j = i; j < gas.length; j++) {
number = number + gas[j] - cost[j];
if (number < 0) {
break;
}
}
if (i==0 && number>=0) {
return 0;
}
//计算节点前面的累计汽油
if (i>0 && number>=0) {
for(int j=0;j<i;j++) {
number=number+gas[j]-cost[j];
if(number<0) {
return -1;
}
}
if(number>=0) {
return i;
}
}
}
return -1;
}
//忍不住想来一发用链表模拟... //正好好像没看到用链表模拟的.... //写个链表给大家取笑一下......... class Solution { public: struct ListNode{ ListNode *next; int gas; int cost; }; int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { if(gas.size()==0) return -1; if(cost.size()==0) return -1; if(cost.size()!=gas.size()) return -1; int gasSum=0,costSum=0; for(int i=0;i<gas.size();i++) { gasSum+=gas[i]; costSum+=cost[i]; } if(gasSum<costSum) return -1; int N=gas.size(); ListNode * pHead=new ListNode(); ListNode *plast=pHead; pHead->gas=gas[0]; pHead->cost=cost[0]; for(int i=1;i<N;i++) { ListNode *pStation=new ListNode(); plast->next=pStation; pStation->gas=gas[i]; pStation->cost=cost[i]; plast=pStation; } plast->next=pHead; ListNode *pNode=pHead; for(int i=0;i<N;i++) { ListNode* pTemp=pNode; int leftGas=0; while(true) { leftGas+=pTemp->gas; //在开始的站先加油 leftGas-=pTemp->cost;//然后看下到下一个站是否够油 if(leftGas<0) break; //不够油,换个加油站 else //够油到下一个站 { if(pTemp->next==pHead) return i; else pTemp=pTemp->next; } } pNode=pNode->next; } return -1; } };
class Solution(object): def canCompleteCircuit(self, gas, cost): a = [] for i in range(len(gas)): a.append(gas[i] - cost[i]) if sum(a) < 0: return -1 res = -1 s = 0 for i in range(len(a)): if res == -1: if a[i] >= 0: res = i s = a[i] else: if s + a[i] >= 0: s += a[i] else: res = -1 return res
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int start = gas.size() - 1; int end = 0; int V = gas[start] - cost[start]; while(start > end) { if(V>=0) { V += gas[end] - cost[end]; end++; }else{ start--; V += gas[start] - cost[start]; } } return V>=0?start:-1; } };