西安疫情防控最新政策_设计方案评价_口碑营销的前提及好处有哪些_谷歌seo外链

 

1. 如果i可以往后走n步，那就可以绕一圈，返回start即可。
2. 如果i只能走cnt步（其中cnt<n）到某个点j，那么下一个起点只能从i+cnt+1开始尝试。从中间的某个点k开始也是不可能跨过j点的，因为从i可以到k点，说明i到k可以带大于等于0的油量过来。带了油过来都跨越不了j点，那以k为起点肯定更加跨越不了j点。

代码：

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) 
{int i = 0;while (i < gasSize) {int sumOfGas = 0, sumOfCost = 0;int cnt = 0;/*从当前加油站 i 开始，尝试走 cnt 个加油站。使用模运算来处理环形道路的情况。每经过一个加油站，就累加对应的汽油和费用。如果在某个时刻总的费用 sumOfCost 超过了总的汽油 sumOfGas，说明从当前起点 i 到达某个加油站 j 时，汽油不够，那么就中断这一轮尝试。*/while (cnt < gasSize) {int j = (i + cnt) % gasSize;sumOfGas += gas[j];sumOfCost += cost[j];if (sumOfCost > sumOfGas) {break;}cnt++;}/*如果 cnt 等于 gasSize，说明从起点 i 出发的所有加油站都能够成功到达，返回 i。如果不成功，则将 i 更新为 i + cnt + 1，跳过已经尝试过的加油站，继续尝试下一个可能的起点。*/if (cnt == gasSize) {return i;}else {i = i + cnt + 1;}}return -1;
}