环形路上有n个加油站，第i个加油站的汽油量是gas[i].
你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。
求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-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;
}
}
发表于 2021-03-30 10:14:28
回复(0)
方法一：直接枚举。但是时间复杂度为 O(n2) .
/**
*
* @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);
}
编辑于 2020-09-20 00:16:06
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i=0;i<gas.length;i++){
int gasSum=0;
int costSum=0;
for(int j=i;j<gas.length;j++){
gasSum+=gas[j];
costSum+=cost[j];
if(costSum>gasSum)
break;
}
if(costSum<=gasSum){
for(int j=0;j<i;j++){
gasSum+=gas[j];
costSum+=cost[j];
if(costSum>gasSum)
break;
}
}
if(costSum<=gasSum)
return i;
}
return -1;
}
}
遍历每一个加油站出发的情况，针对出发的加油站i，从i开始，统计所需要的costSum,以及总共的gasSum，只有gas>cost的时候才能继续开下去，否则更换对出发点加1，变成i+1。需要注意i->end.。end->i。分两次进行
发表于 2020-04-13 18:05:12
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int i,j;
for(i=0;i<gas.length;i++){
int[] circle=new int[gas.length];
int temp=i;
int rest=0;
for(j=0;j<gas.length;j++){
if(temp>=gas.length)
temp=0;
circle[j]=temp;
temp++;
rest=rest+gas[circle[j]]-cost[circle[j]];
if(rest<0){
break;
}
}
if(j==gas.length){
return i;
}
}
return -1;
}
}
编辑于 2020-03-31 16:27:07
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas.length != cost.length)
return -1;
int total = 0; //记录走完一圈剩余的油量，若total>=0,则必存在满足题目条件的加油站点下标
int sum = 0; //记录从i到i+1是否可行，即需判断剩余油量sum>=0是否成立
int index = 0; //初始化出发站点为第一个站点下标
for(int i = 0 ; i < gas.length; i++){
total += gas[i] - cost[i]; //累加走完一个站点的剩余油量
sum += gas[i] - cost[i]; //累加走完一个站点的剩余油量
if(sum < 0){ //若剩余油量小于0，则表示i到i+1不可达，将i+1记为出发站点，同时sum重新初始化为0
sum = 0;
index = i + 1;
}
}
return total >= 0? index : -1; //若total>=0，则返回满足条件的站点下标，否则返回-1
}
}
编辑于 2020-02-27 11:37:25
回复(0)
首先计算每个加油站所加的油与到下一个加油站耗油的差值并保存在diff数组。
从第一个加油站开始出发，计算到达后面加油站所剩油量sum，即累加diff数组。
核心思想：
如果到达第i个加油站时sum小于零，说明从当前起点出发到达不了该加油站，同时可证明
从他们之间的任意一个加油站出发都到达不了第i个加油站，因此下一次选择把第i个加油站作为出发点。（相当于剪枝的思想）
算法步骤：
从某一个选择的加油站出发（i），从i开始循环，到 i+gas.length 结束循环 如果直到循环结束，sum始终大于等于零，则表示从该加油站出发能走完一圈，如果到达某一加油站时sum小于零则有三种情况：
1）如果i>gas.length,表示可选的起点已经越过初始0位置，即没有任何一个加油站可作为起点选择。
2）如果i==start_p,即从选择的起点到不了下一个加油站，则选择下一个加油站作为起点
3）否则选择该到达不了的加油站作为下一个起点。
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int[] diff = new int[gas.length];
for(int i = 0;i<gas.length;i++){
diff[i] = gas[i]-cost[i];
}
int start_p = 0;
int sum = 0;
while(start_p<gas.length){
for(int i =start_p;i<start_p+gas.length;i++){
sum+=diff[i%gas.length];
if(sum<0){
if(i>=gas.length)
return -1;
if(i==start_p)
start_p = start_p+1;
else
start_p = i%gas.length;
sum = 0;
break;
}
if(i==start_p+gas.length-1)
return start_p;
}
}
return -1;
}
}
发表于 2020-02-08 18:51:13
回复(0)
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0; //起点
int sum = 0; //当前站汽油加上消耗剩下的汽油
int total = 0; //总剩下的汽油
for(int i =0 ;i<gas.length;i++) {
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
//sum<0,表明从起点到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。
if(sum < 0) {
start = i + 1; //经过多少站加上1
sum = 0; //重新开始计数
}
}
return total >= 0 ? start : -1;
}
int start = 0; //起点
int sum = 0; //当前站汽油加上消耗剩下的汽油
int total = 0; //总剩下的汽油
for(int i =0 ;i<gas.length;i++) {
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
//sum<0,表明从起点到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。
if(sum < 0) {
start = i + 1; //经过多少站加上1
sum = 0; //重新开始计数
}
}
return total >= 0 ? start : -1;
}
发表于 2019-03-16 21:43:01
回复(0)
献丑了：
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0;
while (start <= gas.length - 1) {
if (start(gas, cost, start) != -1) {
return start;
}
start++;
}
return -1;
}
while (start <= gas.length - 1) {
if (start(gas, cost, start) != -1) {
return start;
}
start++;
}
return -1;
}
public int start(int[] gas, int[] cost, int start) {
int gastank = 0;
for (int i = start; i < gas.length; i++) {
gastank = gastank + gas[i] - cost[i];
if (gastank < 0) {
return -1;
}
}
for (int i = 0; i < start; i++) {
gastank = gastank + gas[i] - cost[i];
if (gastank < 0) {
return -1;
}
}
return start;
}
int gastank = 0;
for (int i = start; i < gas.length; i++) {
gastank = gastank + gas[i] - cost[i];
if (gastank < 0) {
return -1;
}
}
for (int i = 0; i < start; i++) {
gastank = gastank + gas[i] - cost[i];
if (gastank < 0) {
return -1;
}
}
return start;
}
发表于 2018-07-01 01:34:12
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int[]res = new int[gas.length];
for(int i=0;i<gas.length;i++){
res[i] = gas[i]-cost[i];
if(res[i]>=0){
for(int j=(i+1)%gas.length;j<gas.length;j++){
res[i] = res[i]+gas[j]-cost[j];
if(res[i]<0){
break;
}
if(j==i)
break;
}
}
}
for(int i=0;i<res.length;i++){
if(res[i]>=0)
return i;
}
return -1;
}
}
发表于 2018-05-08 15:40:42
回复(0)
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas==null||gas.length<=0||cost==null||cost.length<=0||gas.length!=cost.length){
return -1;
}
int i=0;
for(i=0;i<cost.length;i++){
if(cost[i]>gas[i]){
continue;
}
else{
int left=0;
int cur=i;
int j=0;
for(j=cur;j<cost.length;j++){
left=left+gas[j]-cost[j];
if(left<0){
break;
}
}
if(j==cost.length){
for(j=0;j<cur;j++){
left=left+gas[j]-cost[j];
if(left<0){
break;
}
}
if(j==cur){
return cur;
}
}
}
}
return -1;
}
暴力破解法！！！
发表于 2018-05-04 13:58:58
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int i = 0; i < gas.length; i++) {
if (gas[i] >= cost[i]) {
int sum = gas[i] - cost[i];
int j = (i + 1) % gas.length;
while (sum >= 0 && j != i) {
sum += gas[j] - cost[j];
j = (j + 1) % gas.length;
}
if (j == i && sum >= 0) {
return i;
}
}
}
return -1;
}
}
发表于 2018-04-29 14:53:44
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int len = gas.length;
for (int i = 0; i < len; i++) {
int total = 0;
int j = i;
while (total >= 0) {
total = total + gas[j] - cost[j];
j = (j + 1) % (len);
if (total < 0)
break;
if (j == i) return i;
}
}
return -1;
}
}
发表于 2018-04-01 18:13:29
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int currentGas = 0;
for (int i = 0; i < gas.length; i++) {
if (gas[i] >= cost[i]) {
int j = i + 1;
currentGas = gas[i] - cost[i];
boolean flag = true;
while (j % gas.length != i) {
if (gas[j%gas.length] + currentGas < cost[j%gas.length]) {
flag = false;
break;
}
currentGas = currentGas + gas[j%gas.length] - cost[j%gas.length];
j++;
}
if (flag)
return i;
currentGas = 0;
}
}
return - 1;
}
}
发表于 2018-03-29 17:11:37
回复(0)
import java.util.*;
/*
There are N gas stations along a circular route, where the amount of gas at station i isgas[i].
You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1).
You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
*/
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int left = 0;
int N = gas.length;
for(int start = 0; start<N; ++start){
for(int u = 0; u<N; ++u){
if(left + gas[(start+u)%N] >= cost[(start+u)%N]){
left += gas[(start+u)%N] - cost[(start+u)%N];
}else{
left = -1;
break;
}
}
if(left>=0){
return start;
}else{
left = 0;
}
}
return -1;
}
}
发表于 2018-01-21 14:55:17
回复(0)
//思路:
//设两个游标start,end= gas[n-1] ,;
//end是从n-1,n,n+1,n+2...走(求余后为n-1,0,1,2,3...),从左往右逼近
//如果amount为负,start就从n-2,n-3,n-4....走,从右往左逼近
//当start=-1时无解,当start = i-length时,两个游标碰面,满足情况
public static int canCompleteCircuit(int[] gas, int[] cost) {
if( cost == null ||gas == null || gas.length != cost.length)return -1;
int start = gas.length-1;//从最后一站开始走
int end = gas.length-1;
int amount = 0;
for (int i = end; i < 2*cost.length; i++) {
amount += gas[i%gas.length]-cost[i%gas.length];
while(amount <0){//如果油量不够的话
start = start-1;//start游标就往前移动一位
if(start <0)return -1;//移动到第0站时油箱还是负的,就返回-1
amount += gas[start]-cost[start];
}
if(start == i -gas.length)return start;
}
return -1;
}
发表于 2017-07-29 14:33:59
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int totalRest = 0;
int start = 0;
for (int i = 0; i < gas.length; ++i) {
sum += gas[i] - cost[i];
totalRest += gas[i] - cost[i];
if (sum < 0) {
start = i + 1;
sum = 0;
}
}
if (totalRest < 0)
return -1;
else {
return start;
}
}
}
发表于 2017-07-20 22:06:45
回复(0)
//穷举
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i=0;i<gas.length;i++){
if(f(gas,cost,i,0,i)) return i;
}
return -1;
}
public boolean f(int[] g,int []c,int i,int gas,int start){
if(gas+g[i]<c[i]) return false;
int a =(i+1)%g.length;
if(a==start) return true;
return f(g,c,a,gas+g[i]-c[i],start);
}
}
发表于 2017-07-20 10:22:54
回复(0)
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
//检查条件是否满足要求
if(gas == null || cost == null || gas.length == 0 || cost.length == 0 || gas.length != cost.length){
return -1;
}
//检查油量与消耗是否满足要求
int gassum = 0;
int costsum = 0;
for(int i = 0; i < gas.length; ++i){
gassum += gas[i];
costsum += cost[i];
}
//不满足要求就返回-1
if (gassum < costsum) {
return -1;
}
//根绝贪心选择策略，选择油量/消耗最大的站开始
double[] help = new double[gas.length];
for(int i = 0; i < gas.length; ++i) {
help[i] = (double)gas[i]/(double)cost[i];
}
double max = help[0];
int index = 0;
for(int j = 1; j < gas.length; ++j){
if (help[j] > max){
index = j;
max = help[j];
}
}
return index;
}
}
发表于 2017-07-12 09:26:44
回复(0)
问题信息
难度：
21条回答
211收藏
37434浏览
通过挑战的用户
查看代码-
2023-03-11 10:04:55 -
2022-09-12 16:07:30 -
2022-09-10 23:11:21 -
2022-09-08 20:39:04 -
2022-09-02 21:05:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int start = gas.size() - 1; int end = 0; int sum = gas[start] - cost[start]; while(start > end){ if(sum >= 0){ sum += gas[end] - cost[end]; ++end; }else{ --start; sum += gas[start] - cost[start]; } } return sum >=0 ? start : -1; } };