leetcode_OJ WC93 解題心得
- Contest time: Jul 15, 2018
- 思路：直接解即可，用雙指標測量兩個鄰近的1的距離(不一定要相鄰，題目解說有點不清楚)，其中的to_binary是實用的數字轉二進位字串的方法。
- 分析 Time complexity = O(N), Space complexity (with auxilary string structure to store the binary number) = O(N)
#define FORI(n) for(int i = 0; i < n; ++ i)
class Solution
{
public:
int binaryGap(int num)
{
string binstr = to_binary(num);
int maxd = 0;
for(int i = 0; i < binstr.size() - 1; i++)
{
if(binstr[i] == '1')
{
for(int j = i + 1; j < binstr.size(); j++)
{
if(binstr[j] == '1')
{
maxd = max(maxd, j - i);
i = j;
break;
}
}
}
}
return maxd;
}
string to_binary(int num)
{
string res;
while(num)
{
if(num & 1)
{
res += "1";
}
else
{
res += "0";
}
num /= 2;
}
reverse(res.begin(), res.end());
return res;
}
};
- 題意：一個數字的各個位數，經過排列組合(包括不重排)後，其組合是否有可能成為二的次方，例如46重排變成64則符合，1232不管怎排都不行
- 思路：
- 先將已經是二的倍數，不需重排的直接回傳true。
- 接著進入while迴圈將每一位數push進入vector中，用algorithm std中的next_permutation排出所有可能，再把它串起來，以.c_str()，加上atoi的方式傳入is_pow2判斷，若有符合則直接回傳true，最後都沒有則回傳false。
- num & (num - 1) == 0 的話就是二的次方，挺實用的，大家可以透過二進位制想一下為什麼
- 分析 Time complexity = O(logN!??)(不確定，待確認，希望有先進能賜教，總覺得不太可能到fraction，不然沒有機會ac), Space complexity (with auxilary string structure to store the number) = O(N)
#define pb push_back
class Solution
{
public:
bool reorderedPowerOf2(int num)
{
if(num >= 1 && num <=10)
{
if(is_pow2(num))
{
return true;
}
return false;
}
else if(is_pow2(num)) //original order
{
return true;
}
vector<int> dgt;
while(num)
{
dgt.pb(num % 10);
num /= 10;
}
sort(dgt.begin(), dgt.end());
int sz = dgt.size(), judge = 0;
string str;
do {
str = "";
for(int i = 0; i < sz; i++)
{
str += (dgt[i] + '0');
}
cout << str <<endl;
judge = atoi(str.c_str());
if(is_pow2(judge))
{
return true;
}
}while(next_permutation(dgt.begin(), dgt.end()));
return false;
}
bool is_pow2(int num)
{
if((num & (num - 1)) == 0 )
{
return true;
}
return false;
}
};
- 題意: 給定目標距離與最初的汽油量，其中加油站會在某些距離，經過的時候可以將加油的汽油全部移轉過來，此時加油站的汽油將會用罄(全有全無)，並且一公里的行車會消耗汽油一公升(油耗真爛?)，問找出最少家由次數同時又能抵達目標，若無法則回傳-1
- WA思路: 這題當下沒有解出只有WA，看了提示解出，比較難。以下是原本錯誤的作法
- 首先每一次都盡量走到最遠的加油站。
- 再看當前可以找(也就是距離station position - my position <= current gas fuel)的加油站中，能補充最多的(包括往回走)
- 但貪心算法忽略了: 如果走來這裡前，事先補充過幾個加油站，雖會造成加油次數變多，但也可能更遠，例如 target = 200 startFuel = 100, stations = [[10, 60],[100, 80]]，錯誤算法會先走到 100 加油站 之後又逆回10加油站去加油 導致最後汽油量變成50(80-(100-10)+60) 哪都不能去
- 缺失分析: 實際上，上方的第三點想法是錯的，因為根本不是用回去加油的方法，而是走到此，再加上"當初如果經過該加油站所能延伸的距離"
/*
wrong answer testcase102 : 1000
299
[[13,21],[26,115],[100,47],[225,99],[299,141],[444,198],[608,190],[636,157],[647,255],[841,123]]
*/
class Solution
{
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations)
{
if(startFuel >= target)
{
return 0;
}
else if(stations.size() == 0)
{
return (startFuel >= target) ? 0 : -1;
}
int dp[500][500] = {0}, cur_fuel = startFuel, car_pos = 0, refuel = 0;
int best_choice = 0, max_refuel = 0, stations_pos = 0, can_reach_next = 1;
int closest_next_pos = 0, closest_next_dist = INT_MAX;
while (1)
{
printf("car_pos %d fuel_now %d \n",car_pos, cur_fuel);
if(car_pos + cur_fuel >= target || car_pos >= target) //should have the highest priority
{
printf("reach target!\n");
break;
}
can_reach_next = 0;//search the next, closest stations to go, reachable or not (check the requirement of break if unreachable)
closest_next_pos = 0;
closest_next_dist = INT_MAX;
for(int i = 0; i < stations.size(); i++)
{
if(abs(stations[i][0] - car_pos) < closest_next_dist && stations[i][1] > 0 /*still useable*/)
{
closest_next_dist = stations[i][0];
closest_next_pos = i;
}
}
if(stations[closest_next_pos][0] - car_pos > cur_fuel || closest_next_dist == INT_MAX)//unracehable with current fuel
{
printf("unreachable to all\n");
return -1;
}
max_refuel = stations_pos = 0;
for(int i = 0; i < stations.size(); i++) //find all reachable stations with max fuel to refill
{
if(/*stations[i][0] - car_pos >= 0*/cur_fuel >= abs(stations[i][0] - car_pos)/*reachable with current fuel*/&& stations[i][1] > max_refuel /*bigger fuel slot*/)
{
printf("i %d i0 %d i1 %d ok \n", i, stations[i][0], stations[i][1]);
max_refuel = stations[i][1];
stations_pos = i;
}
}
cur_fuel -= abs(stations[stations_pos][0] - car_pos); //drive
car_pos = stations[stations_pos][0]; //reach
cur_fuel += stations[stations_pos][1]; //refill
// stations[stations_pos][0] = INT_MAX; //marked such station as used to prevent duplicate using
stations[stations_pos][1] = 0; //used out such fuel
refuel++;
printf("select stations_pos %d, car_pos is now %d, car_fuel is now %d \n",stations_pos, car_pos, cur_fuel);
}
return refuel;
}
};
- 改正後 AC思路: 採用 priority_queue優先隊列回溯
- 首先一直走
- 直到在某個加油站停下時，燃料已經呈現負債，這時候回溯之前走過的加油站，依據優先隊列先找出最多油量的加油站。
- 途中若 當前的位置加上汽油量足以走到終點 則直接跳出回傳結果(另外，若回溯也無法補足負債的燃料，代表無論如何都找不到，因為即便加了油也無法前進，代表到不了target)，
- 走完所有加油站後若還沒有到終點，則繼續回溯之前走過的加油站，最後在一樣看 當前的位置加上汽油量足以走到終點 決定是否回傳-1。
- 自己跑過一便會想得比較清楚，例如方才的target = 200 startFuel = 100, stations = [[10, 60],[100, 80]] 首先一路走到尾端 此時油量剩下0 位置在100，開始回溯 首先將[100, 80]pop 出來，代表我如果在100加油可以再從100走80，得到180，此時加油次數1；再來將[10, 60]pop 出來，代表我 當初如果 有在10加油，我可以更再延伸60KM，於是能走到240
- 改進概念: 走到後發現沒油，回溯不是直接走去該加油站，而是加上該加油站我當初如果走過，會再延伸多少。
- 分析: Time complexity O(N log N) (log N for priority_queue structure maintenance, heap), Space complexity O(N), (the priority_queue)
- 心得: 這題讓我學會客製化優先隊列的寫法，因為要自訂上面是最大的所以寫了compare 裡面要放operator多載才可以用，不然會有priority_queue argument的compile error (詳情可以自行google，我也是查過才發現這個新寫法)
/*
AC version, try using the priority queue. we keep traversing through the stations without refuling, that means try our best with current fuel.
Once we traverse to a gas station with the negative fuel,
we refill the tank with the gas station we have visited before(pushed in to the traversed_stations priority queue)
to check if we can reach even further if we refueled before using the retroactive method.
----------------------------------------------------------------------------------------------------------------
Please try the following testcases for understanding how the code runs
1000
299
[[13,21],[26,115],[100,47],[225,99],[299,141],[444,198],[608,190],[636,157],[647,255],[841,123]]
*/
class Solution
{
public:
struct mycompare
{
bool operator()(pair<int ,int>&p1, pair<int ,int>&p2) //pair first for station position and second for how much gas does a staion hace
{
return p1.second < p2.second; //sort descending to get the largest element first
}
};
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations)
{
if(stations.size() == 0)
{
return (startFuel >= target) ? 0 : -1;
}
priority_queue<pair<int ,int>, vector<pair<int ,int>>, mycompare> traversed_stations; //logN query
int cur_fuel = startFuel, car_pos = 0, has_chance_to_refuel = 1, refuel = 0;
for(int i = 0; i < stations.size(); i++)
{
cur_fuel -= (stations[i][0] - car_pos);
if(car_pos + cur_fuel >= target)
{
break;
}
while(!traversed_stations.empty() && cur_fuel < 0) //traverse to certain gas station but we ran out of fuel, that we have to trace back to see if we can refuel before
{
cur_fuel += traversed_stations.top().second;
refuel++;
traversed_stations.pop();
}
if(cur_fuel < 0)
{
return -1;
}
car_pos = stations[i][0];
traversed_stations.push(make_pair(stations[i][0], stations[i][1]));;
has_chance_to_refuel = 0;
}
//if hasn't reach the target yet
while(!traversed_stations.empty() && car_pos + cur_fuel < target) //traverse to certain gas station but we ran out of fuel, that we have to trace back to see if we can refuel before
{
cur_fuel += traversed_stations.top().second;
// car_pos = traversed_stations.top().first;
refuel++;
traversed_stations.pop();
}
return (car_pos + cur_fuel >= target) ? refuel : -1; //able to reach the target destination or not
}
};