Skip to content

leetcode_OJ WC93 解題心得

  • Contest time: Jul 15, 2018

PA. 868. Binary Gap 簡單雙指標

  • 思路:直接解即可,用雙指標測量兩個鄰近的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;
    }
};

PB. 869. Reordered Power of 2 STL活用

  • 題意:一個數字的各個位數,經過排列組合(包括不重排)後,其組合是否有可能成為二的次方,例如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;
        }
    };
    

PC.870. Advantage Shuffle 貪心算法

  • 題解請見此(雙語版本同步刊載於討論區)

PD. 871. Minimum Number of Refueling Stops priority_queue回溯法

  • 題意: 給定目標距離與最初的汽油量,其中加油站會在某些距離,經過的時候可以將加油的汽油全部移轉過來,此時加油站的汽油將會用罄(全有全無),並且一公里的行車會消耗汽油一公升(油耗真爛?),問找出最少家由次數同時又能抵達目標,若無法則回傳-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
    }

};