題目描述

?

?一.原本暴力算法

最初的想法是：先比較gas數組和cost數組的大小，找到可以作為起始點的站點(因為如果你起始點的油還不能到達下一個站點，就不能作為起始點)。當找到過后，再去依次順序跑一圈，如果剩余的油為負數，再去尋找下一個滿足條件的起始站點。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int index = -1; //定義初始起點int left = 0; //定義剩余油量bool flag = false;int n = gas.size();//尋找起始位置for(int i = 0;i<n;i++){if(gas[i] < cost[i]) {continue;}else{index = i; int j = index;int count = 0;cout<<"index="<<index<<endl;while(true){j = j%n;cout<<"j="<<j<<endl;if(left < 0) {left = 0;break;}if(count == n){flag = true;return index;}left = left + gas[j] - cost[j];cout<<"left="<<left<<endl;count++;j++;}   }}//判斷if(flag){return index;}else{return -1;}}
};

?

但是代碼最后超時了！！

時間復雜度是O(N^2)?因為循環遍歷尋找起始站點，找到過后再去循環遍歷走一圈是O(N^2）的時間復雜度！

巧妙思路算法二能通過的

轉子大佬的代碼。

• 情況一：如果gas的總和小于cost總和，那么無論從哪里出發，一定是跑不了一圈的

• 情況二：rest[i] = gas[i]-cost[i]為一天剩下的油，i從0開始計算累加到最后一站，如果累加沒有出現負數，說明從0出發，油就沒有斷過，那么0就是起點。

• 情況三：如果累加的最小值是負數，汽車就要從非0節點出發，從后向前，看哪個節點能把這個負數填平，能把這個負數填平的節點就是出發節點。

• class Solution {
  public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX; // 從起點出發，油箱里的油量最小值for (int i = 0; i < gas.size(); i++) {int rest = gas[i] - cost[i];curSum += rest;if (curSum < min) {min = curSum;}}if (curSum < 0) return -1;  // 情況1if (min >= 0) return 0;     // 情況2// 情況3for (int i = gas.size() - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
  };

  在這里時間復雜度O(N)

• 空間復雜度O(1)沒有開辟新的空間

二.貪心算法

每個加油站的剩余量rest[i]為gas[i] - cost[i]。

i從0開始累加rest[i]，和記為curSum，一旦curSum小于零，說明[0, i]區間都不能作為起始位置，因為這個區間選擇任何一個位置作為起點，到i這里都會斷油，那么起始位置從i+1算起，再從0計算curSum。

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一旦小于0start = i + 1;  // 起始位置更新為i+1curSum = 0;     // curSum從0開始}}if (totalSum < 0) return -1; // 說明怎么走都不可能跑一圈了return start;}
};

時間復雜度O(N)?

轉載于代碼隨想錄，大佬的算法