题目
题目链接：
https://www.nowcoder.com/practice/a013a0691a0343aeb262ca1450d2fe4e
思路
贪心：
如果总的gas小于走完全程的cost，直接返回-1不需要再找了
如果确保了可以走完一圈之后，那么从index = 0开始找，
当gas_remain的油箱低于0了就代表从index出发不可以,index += 1
循环一遍即可,因为已经肯定了有答案，所有只要有一个i可以一直走到结束都可以保持油箱 > 0，
那么它肯定是答案。
参考答案C++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param gas int整型vector
* @param cost int整型vector
* @return int整型
*/
int gasStation(vector<int>& gas, vector<int>& cost) {
// 贪心
int sum = 0, allgas = 0, allcost = 0, start = 0;
for (int i = 0; i < gas.size(); i++) {
sum = sum + gas[i] - cost[i];
allgas += gas[i];
allcost += cost[i];
if (sum < 0) { //尝试从下一个位置出发
sum = 0;
start = i + 1;
}
}
return allgas >= allcost ? start : -1;
}
};
参考答案Java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param gas int整型一维数组
* @param cost int整型一维数组
* @return int整型
*/
public int gasStation (int[] gas, int[] cost) {
//贪心
int sum = 0, allgas = 0, allcost = 0, start = 0;
for (int i = 0; i < gas.length ; i++) {
sum = sum + gas[i] - cost[i];
allgas += gas[i];
allcost += cost[i];
if (sum < 0) { //尝试换下一个位置出发
sum = 0;
start = i + 1;
}
}
return allgas >= allcost ? start : -1;
/*
示例1
输入：
[1,2,3,4,5],[3,4,5,1,2]
返回值：
3
说明：
只能从下标为 3 的加油站开始完成 （即第四个加油站）：
1： index=3 start=4 cost=1 rest=3
2: index=4 start=8 cost=2 rest= 6
2: index=0 start=7 cost=3 rest=4
2: index=1 start=6 cost=2 rest=4
2: index=2 start=7 cost=5 rest=2
2: index=6 start=7 cost=5 rest=2
*/
}
}
参考答案Go
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param gas int整型一维数组
* @param cost int整型一维数组
* @return int整型
*/
func gasStation(gas []int, cost []int) int {
//贪心
sum := 0
allgas := 0
allcost := 0
start := 0
for i := 0; i < len(gas); i++ {
sum = sum + gas[i] - cost[i]
allgas += gas[i]
allcost += cost[i]
if sum < 0 { //尝试从下一个位置出发
sum = 0
start = i + 1
}
}
if allgas >= allcost {
return start
}
return -1
/*
示例1
输入：
[1,2,3,4,5],[3,4,5,1,2]
返回值：
3
说明：
只能从下标为 3 的加油站开始完成 （即第四个加油站）：
1： index=3 start=4 cost=1 rest=3
2: index=4 start=8 cost=2 rest= 6
2: index=0 start=7 cost=3 rest=4
2: index=1 start=6 cost=2 rest=4
2: index=2 start=7 cost=5 rest=2
2: index=6 start=7 cost=5 rest=2
*/
}
参考答案PHP
<?php
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param gas int整型一维数组
* @param cost int整型一维数组
* @return int整型
*/
function gasStation( $gas , $cost )
{
//贪心
$sum=0;
$allgas =0;
$allcost=0;
$start=0;
for($i=0;$i<count($gas);$i++){
$sum=$sum+$gas[$i]-$cost[$i];
$allgas+=$gas[$i];
$allcost+=$cost[$i];
if($sum<0){ //尝试换一个位置再出发
$sum=0;
$start =$i+1;
}
}
return $allgas>=$allcost? $start:-1;
/*
示例1
输入：
[1,2,3,4,5],[3,4,5,1,2]
返回值：
3
说明：
只能从下标为 3 的加油站开始完成 （即第四个加油站）：
1： index=3 start=4 cost=1 rest=3
2: index=4 start=8 cost=2 rest= 6
2: index=0 start=7 cost=3 rest=4
2: index=1 start=6 cost=2 rest=4
2: index=2 start=7 cost=5 rest=2
2: index=6 start=7 cost=5 rest=2
*/
}
