【LeetCode刷题笔记-10 134：加油站】_leetcode 银行家算法

题目：


今天的题，上来我联想到的是操作系统中的银行家算法，因为真的很像。涉及到资源分配，并且要求出完成任务并且不造成死锁（油量足够）的最佳序列。不一样的是，这道题最佳序列是唯一的，在操作系统中，最佳序列其实会有多个。

那么这道题其实比银行家算法要简单一点的，上来我就是一个暴力搜索。针对每一个点，都循环计算。
然后发现时间效率惊人的低。
看了看题解下面大佬们的做法，有一个简化暴力搜索的算法我觉得很好，也比较容易理解。

思路大概是这样：

1.首先，先计算两个数组的总和，如果cost>gas的总量，那么无论如何都是无法完成的，所以这种情况直接返回-1；

2.然后，经过第一步的判定之后，由题目可以知道必定有一个点可以作为起点。所以从gas【0】开始循环，i标识：

（1）如果该点gas<cost，则直接跳过。这一条可以大大削减对每一个起点都去运算检测剩余油量够不够下一个点的计算量。

（2）开始使用j标识当前元素进行暴力搜索，用sum存储剩余油量，去和cost做判定。遇到sum<cost时，说明该起点不行，那么则令起点i = j，由于自增，那么相当于i = j+1

"（2）“重置起点的方式是大大缩短暴力搜索算法时间的关键所在，怎么理解呢？
我们假设gas序列为：3，4，1，5，2
假设cost序列为：3，4，5，2，1
那么很显然，从0开始遍历的话，会在gas【2】的位置汽油量不足，因为gas只补充一个，但是cost需要五个汽油单位。
那么，按照暴力搜索的想法，下一个起点应该是gas【1】，汽油量为4的位置。
但是，循环判定到gas【2】作为起点不行的话，gas【2】之前的所有点都不能当作起点。
因为剩余量肯定不足。

因为你是从gas【0】开始的，如果情况足够好，gas【0】到gas【1】是会有剩余的汽油量的。那么你从gas【1】到gas【2】的油箱里有的油量，是gas【1】+sum。而这个gas【1】+sum都不足以支撑你gas【2】的使用，那么如果你以gas【1】为起点，那么汽油量gas【1】是一定小于等于gas【1】+sum的，就必定不能支撑gas【2】的使用量。所以需要将起点重置到gas【3】的位置。（因为gas【2】加上前面的余油量也不够，说明以它本身作为起点也不够。）
所以就有了i = j；由于自增，相当于i = j+1；

算法（C++附带测试）代码如下：

#include<iostream>
#include<vector>
using namespace std; 

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int gassum = 0;//汽油总量
        int costsum = 0;//消耗总量
        for(int i = 0;i<gas.size();i++)
        {
            gassum += gas[i];
            costsum += cost[i];
        }
        if(costsum>gassum)//不足够完成判定
        {
            return -1;
        }

        for(int i=0;i<gas.size();i++){
            //初始油量小于消耗量，跳过
            if(gas[i] < cost[i])continue;
            int sum = gas[i] - cost[i];//油量剩余值 
            int j=i+1;
            for(;j < gas.size();j++){
                sum += gas[j];
                if(sum >= cost[j]){
                    sum -= cost[j];
                }else{
                    break;
                }
            }
            //能到达n(等价于能到达第0点)，那么就能遍历所有点
            if(j == gas.size())return i;
            //不能到达n的，直接让i=j，由于i自加，该句等价于从i=j+1点出发
            i = j;
        }
        return -1;
    }
};

int main()
{
	vector<int> gas = {1,2,3,4,5};
	vector<int> cost = {3,4,5,1,2};
	int sum;
	Solution s;
	sum  = s.canCompleteCircuit(gas,cost);
	cout<<sum;
}
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
45
46
47
48
49
50