LeetCode134☞加油站
关联LeetCode题号134
本题特点
- 贪心
- 局部最优解-部分差值 如果小于0(消耗大于油站油量) 就从下一个加油站开始,因为如果中间有小于0的情况 当前站就不可能是始发站,
- 整体最优解-整体差值 如果小于0 ,那么就是不能有始发站
本题思路
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
curSum = 0
totalSum = 0
start = 0
for i in range(len(gas)):
curSum += gas[i] - cost[i]
totalSum += gas[i] - cost[i]
if curSum < 0:
start = i + 1
curSum = 0
if totalSum < 0:
return -1
return start
java写法
package leetcode;
import org.junit.jupiter.api.Test;
/**
* File Description: gasStation_134
* Author: Your Name
* Date: 2024/12/24
*/
public class gasStation_134 {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.length; i++){
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if(curSum < 0){
start = i + 1;
curSum = 0;
}
}
if (totalSum < 0){
return -1;
}
return start;
}
@Test
public void TestCanCompleteCircuit() {
int[] gas = {2,3,4};
int[] cost = {3,4,3};
int start = canCompleteCircuit(gas, cost);
System.out.println(start);
}
}