leetcode 134 加油站问题

leetcode 134 解析

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

自己的答案，基本算是暴力解法了，双重循环，不过考虑实际情况大多数都break掉了，测试时间也还好，C++代码如下：

C++解法一：

 class Solution {

 public:

     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

         int re=-,i=,j=;

         int l=gas.size();

         while(re==-&&i<l){

             gas.push_back(gas[i]);//下标每次后移前都把当前下标数目push_back

             cost.push_back(cost[i]);

             if(gas[i]>=cost[i]){//当前point满足出发条件进入子循环；

                 int oil=gas[i],m=;

                 while(m<l-){

                     if(oil-cost[i+m]>=){

                         oil=oil-cost[i+m]+gas[i+m+];

                         m++;

                     }else{

                         break;

                     }

                 }

                 if((m==l-)&&(oil-cost[i+m]>=)){

                     re=i;

                     break;

                 }

             }

             i++;

         }

         return re;

     }

 };

最优解：

只遍历一遍，有三个特征量，total，sum，start

start用来记录起点，也就是最终的返回值；

total用来记录整个环的gas和cost，即验证能否满足走完一圈的最低条件；

sum用来记录start到当前点是否满足向前行驶的条件；

时间复杂度只有O(n)；

但我总觉得这个程序实际上必须是满足total>0一定有解，这个解就是sum>0的第一个点的下标；至于为什么满足这个条件一定有解，等想明白了再更新；

C++解法二：

 class Solution {

 public:

     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

         int total=,sum=,start=;

         for(int i=;i<gas.size();i++){

             total+=gas[i]-cost[i];//走完整个环的前提

             sum+=gas[i]-cost[i];//走完起点到当前点的前提

             if(sum<){//当到达某一站点时油不够了，更换next为新起点

                 start=i+;

                 sum=;

             }

         }

         return (total<)? - : start;

     }

 };

巴特西

leetcode 134 加油站问题

最新文章

热门文章