算法练习15——加油站

LeetCode 134 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

蛮力法

双重循环，必超时，不过可以验证对题意的理解

Python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        length = len(gas)
        for i in range(length):
            j = (i + 1 + length) % length
            g = gas[i] - cost[i]
            if g < 0:
                continue
            while j != i:
                g += gas[j] - cost[j]
                j = (j + 1 + length) % length
                if g < 0:
                    break
            if g < 0:
                continue
            return i
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Go

func canCompleteCircuit(gas []int, cost []int) int {
	length := len(gas)

	for i := 0; i < length; i++ {
		g := gas[i] - cost[i]
		if g < 0 {
			continue
		}
		for j := (i + 1 + length) % length; (j+length)%length != i; j++ {
			g += gas[(j+length)%length] - cost[(j+length)%length]
			if g < 0 {
				break
			}
		}
		if g >= 0 {
			return i
		}
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

写完发现上面一些取余是多余的orz

根据数据特点优化

1. 假设一定有解，根据题意，一定存在一个加油站i能从i触发绕一圈回到i，且i有且仅有一个
2. 假定从xm到xn后无法再继续行驶，那么xm一定不是满足条件的加油站，且xm到xn之间包括xn均不为满足条件的加油站，因为只要能从符合条件的加油站出发一定能走完全程
3. 所以遍历一次即可获取符合条件的加油站或者确认没有符合题意的加油站，可以从第一个加油站向后走直到无法走到下一站，此时再从下一站从新开始，直到从某一站开始能回自身为正确答案，或者直到最后一站也无法出现满足题意的加油站

Python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        length = len(gas)
        i = 0
        while(i < length):
            j = i + 1
            g = gas[i] - cost[i]
            if g < 0:
                i += 1
                continue
            while j % length != i:
                g += gas[j % length] - cost[j % length]
                j += 1
                if g < 0:
                    i = j
                    break
            if g < 0:
                if j >= length:
                    return -1
                else:
                    continue
            return i
        return -1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Go

func canCompleteCircuit(gas []int, cost []int) int {
	length := len(gas)

	for i := 0; i < length; i++ {
		g := gas[i] - cost[i]
		if g < 0 {
			continue
		}
		for j := i + 1; j%length != i; j++ {
			g += gas[j%length] - cost[j%length]
			if g < 0 {
                i = j
				break
			}
		}
        if g < 0{
            if i > length{
                return -1
            }else{
                continue
            }
        }
        return i
	}
	return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

感觉官方题解和这个题解<-细节处理的很好