leetcode 134 加油站 分手后的思念是犯贱 2022-08-28 09:47 119阅读 0赞 ## 前言 ## 题目:[134. 加油站][134.] 参考题解:[加油站-代码随想录][-] -------------------- ## 提交代码 ## 方法一:暴力法。均从0位置开始进行累计比较。比较简单,代码略。 方法二:从汽油量最大的点,进行累计比较。最大点失败,则从次大点开始。依次类推,直到确定当前条件无法绕圈。 方法三:这个方法不错,但不容易想到。 * 每个加油站的剩余量rest\[i\]为gas\[i\] - cost\[i\]。 * i从0开始累加rest\[i\],和记为curSum,一旦curSum小于零,说明\[0, i\]区间都不能作为起始位置,起始位置从i+1算起,再从0计算curSum。 我推荐方法一,虽然它是暴力法,但它足够简单,在数据量较少时,完全可以承受。 ### 方法二:从油量较大的站点出发 ### #include <vector> #include <algorithm> #include <map> #include <iostream> using namespace std; class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { multimap<int,int> gas_i; // <汽油量,下标> for(int i=0; i<gas.size(); i++){ gas_i.insert(make_pair(gas[i],i)); } multimap<int,int>::iterator it; for(it=gas_i.begin(); it!=gas_i.end(); it++){ // 从大于始发站需要汽油量,从大到小选择 int gas_count = 0; int cost_count = 0; int loc = it->second; int i; for(i=0; i<gas.size(); i++){ gas_count += gas[loc]; cost_count += cost[loc]; if(gas_count < cost_count) break; loc = (loc+1)%gas.size(); } if(i==gas.size()) break; } return it==gas_i.end() ? -1 : it->second; } }; int main(void){ vector<int> gas = {2,0,1,2,3,4,0}; vector<int> cost = {0,1,0,0,0,0,11}; Solution s; cout<<s.canCompleteCircuit(gas,cost); } ### 方法三:贪心 ### 思路和代码实现,来自参考题解。 class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum = 0; int totalSum = 0; int start = 0; for (int i = 0; i < gas.size(); i++) { curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0 start = i + 1; // 起始位置更新为i+1 curSum = 0; // curSum从0开始 } } if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了 return start; // 当可以走一圈时候,起点必然是圈中某一点。从[start,end]多出来的油量,可以填补[0.start-1]。很巧妙~ } }; [134.]: https://leetcode-cn.com/problems/gas-station/ [-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.md
还没有评论,来说两句吧...