⓺➂ Gas Station
Top Interview 150, leetcode medium, C++, Algorithm
Published in
4 min readJun 10, 2024
Today’s code
Idea1 Time Limit Exceeded
這就是模擬法的方式,去推演每一次出發的情形,但這樣就會很費時,與做許多次重複的事情。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int length = gas.size();
vector<int> tank(length);
int ans_index = 0;
bool is_arrived = true;
for(int i = 0; i < length; i++){
tank[i] = gas[i] - cost[i];
}
for(; ans_index < length; ans_index++){
is_arrived = true;
int tmp_gas = 0;
for(int j = ans_index; j < length; j++){
tmp_gas += tank[j];
if(tmp_gas < 0){
is_arrived = false;
break;
}
}
if(!is_arrived){
continue;
}
for(int i = 0; i < ans_index; i++){
tmp_gas += tank[i];
if(tmp_gas < 0){
is_arrived = false;
break;
}
}
if(is_arrived){
break;
}
}
if(is_arrived){
return ans_index;
}else{
return -1;
}
}
};
Idea2 by hi-malik
- 選定的起始位置必須是大於等於零的整數,表示可以順利到達下一個加油站。
- 除了起始位置之後都是累加的(tmp_tunk)方式去判斷,能否順利到達下一個加油站。
- 也是卡關最久的一個限制,就是全部的累計(total_tunk),注意這裡的全部累積跟第二點的起始位置之後的累計,是不一樣的。這裡的全部累計,是在判斷整個走完能不能完美的繞一圈。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int length = gas.size();
int total_tunk = 0;
int tmp_tunk = 0;
int start_index = 0;
for(int i = 0; i < length; i++){
tmp_tunk += gas[i] - cost[i];
total_tunk += gas[i] - cost[i];
if(tmp_tunk < 0){
start_index = i + 1;
tmp_tunk = 0;
}
}
if(total_tunk >= 0 && tmp_tunk >= 0){
return start_index;
}else{
return -1;
}
}
};