首页 > 代码库 > Gas Station
Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station‘s index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
思路：通过不断合法合并相邻边来查找符合要求的起始点。一个合法合并应满足：合并之前和之后gas的剩余值都应大于等于零。
1 class Solution { 2 public: 3 int canCompleteCircuit( vector<int> &gas, vector<int> &cost ) { 4 vector<pair<int,int>> edges( gas.size() ); 5 for( size_t i = 0; i != gas.size(); ++i ) { 6 edges[i].first = i; 7 edges[i].second = gas[i] - cost[i]; 8 } 9 while( !edges.empty() ) {10 vector<pair<int,int>> new_edges;11 size_t i = 0;12 while( i != edges.size() ) {13 int delta = edges[i].second;14 size_t k = i;15 while( ++k != edges.size() && delta >= 0 ) {16 if( delta + edges[k].second < 0 ) { break; }17 delta += edges[k].second;18 }19 new_edges.push_back( pair<int,int>(edges[i].first,delta) );20 i = k;21 }22 if( new_edges.size() > 1 && new_edges.back().second >= 0 ) {23 pair<int,int> &front = new_edges.front(), &back = new_edges.back();24 if( back.second + front.second >= 0 ) {25 front.second = back.second + front.second;26 front.first = back.first;27 new_edges.pop_back();28 }29 }30 if( new_edges.size() == 1 && new_edges[0].second >= 0 ) { return new_edges[0].first; }31 if( edges.size() == new_edges.size() ) { return -1; }32 edges = new_edges;33 }34 return -1;35 }36 }
上述方法实现起来过于复杂。在网上看到一种非常简洁的方法：若总的剩余油量小于0，则不可能存在合法的起始点；否则，则必存在合法起始点。依次遍历每一个gas[i]-cost[i]，若当前剩余油量小于0，说明合法起始点必出现在当前位置之后。
1 class Solution { 2 public: 3 int canCompleteCircuit( vector<int> &gas, vector<int> &cost ) { 4 int total = 0, sum = 0, start = 0; 5 for( size_t i = 0; i != gas.size(); ++i ) { 6 total += gas[i] - cost[i]; 7 sum += gas[i] - cost[i]; 8 if( sum < 0 ) { start = (i+1)%gas.size(); sum = 0; } 9 }10 if( total < 0 ) { return -1; }11 return start;12 }13 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。