时间轴
贪心
题目：
非贪心算法：基于这样一个事实，如果从 i 到某一点 j 之后发现油不够了，那么 i~j 之间的所有点（比如假设 i~j 某一点 k，从 k 出发，少了 i~k 的油量）(从 i 出发能到 k 说明到 k 时油量>=0)更不可能到达 j+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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <vector>
using std::vector;
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int n = gas.size();
int start = 0;
int curr_gas;
int i, idx;
while (start < n) {
curr_gas = 0;
i = 0;
for (i = 0; i < n; i++) {
idx = (start + i) % n;
curr_gas += gas[idx] - cost[idx];
if (curr_gas < 0) {
start = start + i + 1;
break;
}
}
if (i == n)
return start;
}
return -1;
}
};
|
标准的贪心解法：我们是要找一个起点 start，使得从 start 出发沿环路绕一圈，油量永远 ≥ 0。
首先，同样地如果从 i 到某一点 j 之后发现油不够了，那么 i~j 之间的所有点，因为假设 i~j 某一点 k，从 k 出发，少了 i~k 的油量更不可能到达 j+1；
其次对于全部环路总油量 total_gas：如果 total_gas - total_cost < 0，说明整个环路油量不够，无论起点哪儿都不可能成功 → 返回 -1,如果 total_gas - total_cost >= 0，一定存在唯一一个可以成功的起点，这就是贪心方法最后返回的 start。
再者，我们从 0 遍历到 n-1 时，已经筛掉了所有不可能的起点。并且题目保证“如果存在解，则保证它是 唯一 的”。若最终 total >= 0，说明从最后一个 start 出发是可行的。这就说明了只需要遍历一遍是可行的。
那为什么只需遍历 0~n-1 就结束了呢？
形象一点来讲：当 curr_gas < 0 时我们总是把起点重置到“油量曲线最低谷”的下一个位置，所以最终的 start 是全局最低点之后的第一个站；而 total >= 0 说明从最低点之后开始，油量永远不会再跌破 0，因此能绕一整圈。
用反证法：假设最终该解法返回 start,在 start~n-1 之间有一点 k，因为结果是唯一的，如果 start 绕不了一圈，而是 k 能绕一圈，但是由于 start 能够到达 k，所以 start 应该也能绕一圈，与前提存在解则唯一矛盾，因此只需遍历只需要在 total>=0 的情况下，存在 start 可以到达 n-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
28
29
30
| #include <vector>
using std::vector;
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int total_diff = 0;
int curr_gas = 0;
int start = 0;
int diff;
for (int i = 0; i < n; i++) {
diff = gas[i] - cost[i];
total_diff += diff;
curr_gas += diff;
if (curr_gas < 0) {
start = i + 1;
curr_gas = 0;
}
}
return (total_diff >= 0) ? start : -1;
}
};
|
