

leetcode_OJ WC95 解題心得

Contest time: Jul 29, 2018

876. Middle of the Linked List Linked list 中間點

題意：如題
思路：水題，計算長度找到中點，直接解即可

分析：Time complexity O(N), Space complexity O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode* middleNode(ListNode* head)
    {
        ListNode* h2 = head;
        int cnt = 0;
        while(head != NULL)
        {
            cnt++;
            head = head->next;
        }
        cnt /= 2;
        while(cnt--)
        {
            h2 = h2->next;
        }
        return h2;
    }

};

877. Stone Game簡單版Nim game + 一點數學

題意：有點類似簡單版的nim game，有偶數堆石頭(石頭數加總為奇數，因此沒有平手)，玩家雙方（一對一單挑）每次拿取頭或是尾端的堆，一次拿光，每個人都有最優思路，問先者是否可在當前盤面有必勝解。
思路：若我是先者，可以觀察奇數index 或是偶數index加總較大，因而有必勝法則（先者必勝)，因此恆常true)
- 舉例來說 [3,7,9,4] 先者可以觀察到3 + 9 > 7 + 4，因此先者將3取走(後者就只能取4 or 7) 最後先者取得9獲勝。
心得與注意事項：剛開始以為最優思路是greedy algorithm，但這樣只有當前最佳解，很可能因為拿了當前的最佳解，導致後面的人拿比我這個更好的，因而輸掉(例如上面的[3,9,7,4])。

分析：Time complexity O(1), Space complexity O(1)

class Solution
{
public:
    bool stoneGame(vector<int>& piles)
    {
        return true;
    }
};

878. Nth Magical Numbe 排容+二分搜

題意：若一個整數K def as K % A == 0 && K % B == 0 詢問第 N 個這樣的數字多少
思路：暴力解法顯然必TLE，因此要優化成Binary Search找到上下界線

WA解法

class Solution
{
public:
    int nthMagicalNumber(int N, int A, int B)
    {
        unsigned long long int low_bound = min(A, B), up_bound = 1e18;
        unsigned long long int mid = 0, lcm = (A * B) / gcd(A, B);
        while(low_bound <= up_bound)
        {
            mid = low_bound + (up_bound - low_bound) / 2;
            if(mid / A + mid / B - mid / lcm < N) //less than N, increase the lower bound
            {
                low_bound = mid + 1;
            }
            else if(mid / A + mid / B - mid / lcm > N)
            {
                up_bound = mid - 1;
            }
            else /*(錯在這裡)*/
            {
                break;
            }

        }
        return (mid) % (unsigned long long int)(pow(10, 9)+ 7);
    }
    unsigned long long int gcd(unsigned long long int a, unsigned long long int b)
    {
        if (a == 0 || b == 0)
        {
            return 0;
        }

        if (a == b)
        {
            return a;
        }

        if (a > b)
        {
            return gcd(a-b, b);
        }
        return gcd(a, b-a);
    }
};

缺失分析：else break 條件設錯，因為即便是數量剛好N，二分搜尋的上下界也不一定包夾、收斂在一起，因此還得繼續查找可以參見討論區別人對我的回覆

AC解法

class Solution
{
public:
    int nthMagicalNumber(int N, int A, int B)
    {
        unsigned long long int low_bound = min(A, B), up_bound = 1e18;
        unsigned long long int mid = 0, lcm = (A * B) / gcd(A, B);
        while(low_bound < up_bound)
        {
            mid = (low_bound + up_bound) / 2;
            if(mid / A + mid / B - mid / lcm < N) //less than N, increase the lower bound
            {
                low_bound = mid + 1;
            }
            else
            {
                up_bound = mid;
            }
        }
        return low_bound % (unsigned long long int)(pow(10, 9)+ 7); //
    }
    unsigned long long int gcd(unsigned long long int a, unsigned long long int b)
    {
        // Everything divides 0
        if (a == 0 || b == 0)
        {
            return 0;
        }

        // base case
        if (a == b)
        {
            return a;
        }

        // a is greater
        if (a > b)
        {
            return gcd(a-b, b);
        }
        return gcd(a, b-a);
    }
};

分析：Time complexity: O(log (1e18)), Space complexity O(1)
後續討論疑問：如果把 up_bound = mid 改為 up_bound = mid - 1 有時答案會差一，有人知道為什麼嗎，還請程式高手賜教，感謝:)

879. Profitable Schemes 背包DP/動態規劃/自己不熟悉的題型

題意：給定人數N、獲利目標P、每件任務(總共G件)所需求人數與對應利潤，問有幾種組合可以獲利達標?
思路：看了一下教學才寫出，是0-1背包問題(請點此連結到演算法筆記)
- 首先建立一張動態規劃用表格 [工作][當前利潤][人數]的三維表格，表示做完當前i個工作賺j元花費k人數的可能數。
- 走訪表格，i j k 開始走訪進行狀態轉移，每種任務都可以做與不做
  - 若當前可用人數減去此任務需求人數 < 0 則此任務不可做，是故會跟上一個任務一樣的組合情形，亦即 if(k - cur_k < 0){dp[i][j][k] = dp[i - 1][j][k] % MOD; //currrent mission cannot be done, use the last mission}
  - 若當前目標利潤減去當前任務所提供的利潤 < 0，代表該任務利潤極大，則是不做加上做，而做了要查詢0利潤的先前建表，防止越界。 else if(j - cur_p < 0){dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][0][k - cur_k]) % MOD;} 第二步驟解釋不太到位，也是這題比較難想的地方，還望各位刷提高手賜教更好的解釋，感激
  - 剩下就不做這一次＋做了之後的總和，做了就去查詢先前的結果 else{dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - cur_p][k - cur_k]) % MOD;}
  - 最後將 dp[size of tasks(做完全部)][P(目標利潤)][people from 0 to G]加總取mod就是答案
分析：Time complexity O(NGP), Space complexity O(NGP)

心得：動態規劃一直是自己的弱項，即便寫完hard這題，也是看著影片想的，總覺得有點不踏實，之後再繼續練更多的題型補強囉:)

#define LL long long
class Solution
{
public:
    const int MOD = 1e9 + 7;
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit)
    {
        int sz = group.size();
        LL dp[sz + 1][P + 1][G + 1]; //use profit for DP, 1 or padding
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1; //doing nothing is 1
        LL cur_k, cur_p;
        for(LL i = 1; i <= sz; i++)
        {
            cur_k = group[i - 1];
            cur_p = profit[i - 1];
            for(LL j = 0; j < P + 1; j++)
            {
                for(LL k = 0; k < G + 1; k++)
                {
                    if(k - cur_k < 0)
                    {
                        dp[i][j][k] = dp[i - 1][j][k] % MOD; //currrent mission cannot be done, use the last mission
                    }
                    else if(j - cur_p < 0)
                    {
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][0][k - cur_k]) % MOD;
                    }
                    else
                    {
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - cur_p][k - cur_k]) % MOD;
                    }
                }
            }
        }
        LL ans = 0;

        for(int k = 0; k < G + 1; k++)
        {
            ans += dp[sz][P][k];
        }

        return ans % MOD;

    }

};