134.Gas Station

时间 2019-12-06 标签 134.gas 134 gas station

题目大意：一个circle圆环，第i个位置，有汽油gas[i]，而汽车从i到i+1，须要汽油cost[i]。求解，从哪一个位置开始，汽车能走完圆环。若是走不完则返回-1，能走完则返回index。例子以下：spa

法一：两个for循环。直接求解每一个可能的起始位置，而后计算可否在有汽油的状况下，走彻底环。o(n^2)。超时了。代码以下：code

 1     public int canComplete(int[] gas, int[] cost) {
 2         int len = gas.length;
 3         int cnt = 0;
 4         int flag = 0;
 5         //逐一遍历每一种可能
 6         for(int i = 0; i < len; i++) {
 7             flag = 0;
 8             //对于每个可能起始点，都计算一下circle可否完成汽车行驶任务
 9             for(int j = i; j < len; j++) {
10                 cnt += gas[j] - cost[j];
11                 if(cnt < 0 ) {
12                     cnt = 0;
13                     flag = -1;
14                     break;
15                 }
16             }
17             if(flag == -1) {
18                 continue;
19             }
20             for(int j = 0; j < i; j++) {
21                 cnt += gas[j] - cost[j];
22                 if(cnt < 0) {
23                     cnt = 0;
24                     flag = -1;
25                     break;
26                 }
27             }
28             if(flag == 0) {
29                 return i;
30             }
31         }
32         return -1;
33     }

View Code

法二（借鉴）：贪心。待证实。具体见代码（耗时1ms）：blog

 1     public int canComplete(int[] gas, int[] cost) {
 2         int gas_cnt = 0, cost_cnt = 0;
 3         int index = 0, cnt = 0;
 4         for(int i = 0; i < gas.length; i++) {
 5             //统计全部汽油数量
 6             gas_cnt += gas[i];
 7             //统计汽车行驶花费的全部汽油数量
 8             cost_cnt += cost[i];
 9             //统计到目前为止，汽油数量可否支撑汽车行驶
10             cnt += gas[i] - cost[i];
11             //若是一旦行驶不了，则从当前位置的下一个位置做为起始点
12             //缘由：因为到如今都行驶不了，若是选择这个位置以前的任何一个位置做为起始点，汽油数量只会更少
13             //因为若是汽油数量>=花费数量，则必定存在解，因此所找到的解必定符合要求。
14             if(cnt < 0) {
15                 cnt = 0;
16                 index = i + 1;
17             }
18         }
19         //若是汽油数量<花费数量，则必定不存在解。
20         if(gas_cnt < cost_cnt) {
21             return -1;
22         }
23         return index;
24     }

View Code