Skip to content

leetcode_OJ WC94 解題心得 + おまけ

  • Contest time: Jul 22, 2018

PA. Leaf-similar Trees 樹水題

  • 題意:從左到右葉子順序一樣的樹
  • 思路:DFS一遍,放入葉子即可
  • 分析:Time complexity O(N), Space complexity O(N), (auxiliary vector to store the leaf data)
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    #define pb push_back
    class Solution
    {
    public:
        vector<int> l1;
        vector<int> l2;
    
        bool leafSimilar(TreeNode* root1, TreeNode* root2)
        {
            get_leaf(root1, l1);
            get_leaf(root2, l2);
            return l1 == l2;
        }
        void get_leaf(TreeNode* root, vector<int>& lv)
        {
            if(root == NULL)
            {
                return;
            }
            else if(root->left == NULL && root->right == NULL)
            {
                lv.pb(root->val);
            }
    
            if(root->left)
            {
                get_leaf(root->left, lv);
            }
            if(root->right)
            {
                get_leaf(root->right, lv);
            }
        }
    
    };
    

PB. 874. Walking Robot Simulation 自己比較弱的模擬題

  • 題意:模擬機器人走路,遇到障礙物座標則會停在他 前一個位置(例如障礙物的X=6,則遇到障礙物至多行走到X=5)

解法一

  • 思路:用數學硬幹,確認四個方向看往哪走,例如朝向+y的方向(向北),則以下條件成立代表撞上障礙物 posx == obstacles[j][0] && posy < obstacles[j][1] && posy + commands[i] >= obstacles[j][1] 表示X軸一致,往北走剛好撞上,再把Y軸設為障礙物前一個即可。
  • 分析:Time complexity O(N + K)where N, K = # of commands and obstacles respectively. Space complexity O(1)
    class Solution {
    public:
        int robotSim(vector<int>& commands, vector<vector<int>>& obstacles)
        {
            int posx = 0, posy = 0, dir = 0, ans = 0; //0 north 1 east 2 south 3 west
            int cango = 1;
            for(int i = 0; i < commands.size(); i++)
            {
    
                if(commands[i] == -1)
                {
                    dir = (dir + 1) % 4;
                }
                else if(commands[i] == -2)
                {
                    if(dir == 0)
                    {
                        dir = 3;
                    }
                    else
                    {
                        dir--;
                        dir %= 4;
                    }
                }
                else
                {
                    cango = 1;
                    for(int j = 0; j < obstacles.size(); j++)
                    {
                        switch (dir)
                        {
                            case 0:
                            {
                                if(posx == obstacles[j][0])
                                {
                                    if(posy < obstacles[j][1] && posy + commands[i] >= obstacles[j][1])
                                    {
    
                                        posy = obstacles[j][1] - 1;
                                        cango = 0;
                                    }
                                }
                                break;
                            }
                            case 1:
                            {
                                if(posy == obstacles[j][1])
                                {
                                    if(posx < obstacles[j][0] && posx + commands[i] >= obstacles[j][0])
                                    {
                                        posx = obstacles[j][0] - 1;
    
                                        cango = 0;
                                    }
                                }
                                break;
                            }
                            case 2:
                            {
                                if(posx == obstacles[j][0])
                                {
                                    if(posy > obstacles[j][1] && posy - commands[i] <= obstacles[j][1])
                                    {
                                        posy = obstacles[j][1] + 1;
    
                                        cango = 0;
                                    }
                                }
                                break;
                            }
                            case 3:
                            {
                                if(posy == obstacles[j][1])
                                {
                                    if(posx > obstacles[j][0] && posx - commands[i] <= obstacles[j][0])
                                    {
                                        posx = obstacles[j][0] + 1;
    
                                        cango = 0;
                                    }
                                }
                                break;
                            }
                            cout << endl;
                            default: break;
                        }
                        if(cango == 0)
                        {
                            break;
                        }
                    }
                    if(cango)
                    {
                        switch (dir)
                        {
                            case 0:
                            {
    
                                posy += commands[i];
                                break;
                            }
                            case 1:
                            {
    
                                posx += commands[i];
                                break;
                            }
                            case 2:
                            {
    
                                posy -= commands[i];
                                break;
                            }
                            case 3:
                            {
    
                                posx -= commands[i];
                                break;
                            }
                            default: break;
                        }
                    }
                }
                ans = max(ans, posx * posx + posy * posy);
            }
            return ans;
        }
    };
    

解法二

  • 思路:用set存障礙物,模擬四方位,dx dy,北東南西,用dir變數搭配mod4來做轉向的動作,每次向指定的移動方向走一單位,並且檢查當前位置是否存在於障礙物的set中,便會自然而然走到障礙物前停下。
  • 分析:Time complexity O(N + K)where N, K = # of commands and obstacles respectively. Space complexity O(K), use a set to store the positions of obstacles.
    class Solution {
    public:
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int robotSim(vector<int>& commands, vector<vector<int>>& obstacles)
        {
            int posx = 0, posy = 0, dir = 0, ans = 0, tmpx = 0, tmpy = 0; //0 north 1 east 2 south 3 west
            int cango = 1;
            set<pair<int, int>> obst_set;
            for(auto &it : obstacles)
            {
                obst_set.insert(make_pair(it[0], it[1]));
            }
            for(int i = 0; i < commands.size(); i++)
            {
                if(commands[i] == -1)
                {
                    dir = (dir + 1) % 4;
                }
                else if(commands[i] == -2)
                {
                    if(dir == 0)
                    {
                        dir = 3;
                    }
                    else
                    {
                        dir--;
                        dir %= 4;
                    }
                }
                else
                {
                    for(int j = 0; j < commands[i] ;j++) //move grid one by one
                    {
                        tmpx = posx + dx[dir];
                        tmpy = posy + dy[dir];
                        if(obst_set.find(make_pair(tmpx, tmpy)) != obst_set.end())
                        {
                            break;
                        }
                        else
                        {
                            posx = tmpx;
                            posy = tmpy;
                        }
                    }
                }
                ans = max(ans, posx * posx + posy * posy);
            }
            return ans;
        }
    };
    

PC. 875. Koko Eating Bananas 二分搜

  • 題意:猴子吃香蕉,一小時吃K個,除不盡也算一小時,有數堆香蕉,從第一堆開始食用,警衛會在H時間後回來,否則猴子會被抓包,問最小的K為何。
  • TLE思路:

    • 警衛可能很久才回來(H大,K勢必就可以很小)或相反,因此 決定從最大的時間(1e9)降下,以及從0上升,同時看這兩種食用速度是否逾時
    • mxm從1e9降下(一定吃得完,時間逾時將flg設1代表找到能食用速度K的上界)/zr從零開始算,當不會逾時(因為從零開始算,不會逾時代表找到最少),代表找到K的下界。
  • 缺失分析:若食用速度趨於1e9的中間,則從頭尾走要相當久,即便一次走雙向,是故應該用二分搜尋,每次切半看時間上下界線中位數是否趕得及食用完畢。

  • 分析:Time complexity O(N^2), Space complexity O(1)
  • 以下為TLE的程式碼

    class Solution
    {
    public:
        int minEatingSpeed(vector<int>& pls, int hr)
        {
            int mxm = 1e9, minn = 0;
            int zr = 1;
            int tmp_time = 0;
            int flg = 0, flg2 = 0;
            while(1)
            {
                //cnt down from max
                tmp_time = 0;
                if(!flg)
                {
                    for(auto &j : pls)
                    {
                        tmp_time += ceil((float) ((float)j / (float)mxm));
                    }
                    mxm--;
                }
                if(tmp_time > hr)
                {
                    flg = 1;
                }
                //cnt up from min
                tmp_time = 0;
                if(!flg2)
                {
                    for(auto &j : pls)
                    {
                        tmp_time += ceil((float) ((float)j / (float)zr));
                    }
                    zr++;
                }
                if(tmp_time < hr)
                {
                    flg2 = 1;
                }
                if(flg && flg2)
                {
                    break;
                }
                if(zr >= mxm)
                {
                    break;
                }
            }
            return zr > mxm ? mxm + 2 : zr + 2;
        }
    };
    

  • 改進思路:二分搜尋

  • 分析:Time complexity O(N log K) where N is the number of piles and K is the maximum size of a pile(binary search according to pile size to determine the eating speed and each round in testing we have to run through the whole pile to sum up the time = sum(pile[i] / current eating speed)) Space complexity O(1)
    //binary search
    class Solution
    {
    public:
        int minEatingSpeed(vector<int>& pls, int hr)
        {
            int mxm = 1e9, minn = 1, mid = 0, ans = 1e9;
            while(minn < mxm)
            {
                int tmp_time = 0; //count the time for current eating speed K
                mid = (mxm + minn) / 2;
                for(auto &j : pls)
                {
                    tmp_time += ceil(((float)j / (float)mid));
                }
                if(tmp_time > hr) //cannot finish before guard back, should eat faster
                {
                    minn = mid + 1;
                }
                else //can finish before guard back, may eat slower
                {
                    mxm = mid;
                    ans = min(ans, mid);
                }
            }
            return ans;
        }
    };
    

PD.873. Length of Longest Fibonacci Subsequence LIS 的費波那契版本

  • 題意:一樣給一個嚴格增的序列,問最長嚴格增的費波那契子序列
  • TLE思路:

    • 稍微優化的暴力解,首先將費氏數列三項定好。
    • 接著看現在一(i) 二(j) 項目加總是否能大於等於j + 1(因為嚴格增,小於就沒機會從此點出發形成費氏數列,例如1 2 5 9 14 .... 便不可能從1為起點,因為1 + 2 < 5)
    • 若大於 j + 1,則持續搜索j + 1之後的序列,並且 三個數字一組移動,列出第三項預期數值 thr_expected,符合arr[k]就持續往後走並且遞增(三項並不一定要毗鄰,因此thr_expected符合的時候,只要向後移動即可) 例如 1 2 3 4 5 6 8 10 14 從 1(fir) 2(sec) 3(thr_expected) ->(4被跳掉,因為 arr[3] != thr_expected) 2(fir) 3(sec) 5(thr_expected) -> 3(fir) 5(sec) 8(thr_expected)...
    • 最後看長度是否大於二確認有費氏子序列,無則回傳0
  • 缺失分析:O(N^3)太暴力,在查找 thr_expected 實際上可以用unordered_set加速(儲存整份array),將平均線性的時間優化為常數(unordered_set worst = linear, average = constant)

  • 分析:Time complexity O(N^3), Space complexity O(1)

    class Solution
    {
    public:
        int lenLongestFibSubseq(vector<int>& arr)
        {
            int fir = arr[0], sec = arr[1], thr_expected = 0, res = 0, cur_len;
            for(int i = 0; i < arr.size() - 2; i++)
            {
    
                for(int j = i + 1; j < arr.size() - 1; j++)
                {
                    if(arr[i] + arr[j] >= arr[j + 1])
                    {
                        fir = arr[i];
                        sec = arr[j];
                        thr_expected = arr[i] + arr[j];
                        cur_len = 2;
                        for(int k = j + 1; k < arr.size(); k++)
                        {
                            if(thr_expected == arr[k])
                            {
                                fir = sec;
                                sec = thr_expected;
                                thr_expected = fir + sec;
                                cur_len++;
                                res = max(cur_len, res);
                            }
                        }
                    }
                }
            }
            return res == 2 ? 0 : res;
        }
    };
    

  • 改進思路:將查詢的結構優化為unordered_map(實際上map也行,但我們不在意順序,沒差)

  • 分析:Time complexity O(N^2), Space complexity O(N)
class Solution
{
public:
    int lenLongestFibSubseq(vector<int>& arr)
    {
        int fir = arr[0], sec = arr[1], thr_expected = 0, res = 0, cur_len;
        unordered_set<int> myset(arr.begin(), arr.end());
        for(int i = 0; i < arr.size() - 2; i++)
        {

            for(int j = i + 1; j < arr.size() - 1; j++)
            {
                if(arr[i] + arr[j] >= arr[j + 1])
                {
                    fir = arr[i];
                    sec = arr[j];
                    thr_expected = arr[i] + arr[j];
                    cur_len = 2;
                    while(myset.find(thr_expected) != myset.end()) //keep going the rest in the array
                    {
                        fir = sec;
                        sec = thr_expected;
                        thr_expected = fir + sec;
                        cur_len++;
                        res = max(cur_len, res);
                    }
                }
            }
        }
        return res == 2 ? 0 : res;
    }
};

--- 

おまけ 856. Score of Parentheses stack應用

  • 題意:給一堆平衡好的括號, () = 1, (()) = 2, ()() = 2, (()(()) = 2 * ( 1 + 2 ) = 6
  • 思路:用stack記錄左括號位置以及當前分數,遇到右括號,棧頂端是-1則代表,對稱形式的括號已經配對,將分數一分推入棧;反之若不是代表還沒有-1就一路pop裡面的元素直到-1又出現(代表此又刮好已經一路將內部的分數加總,回溯到他自己對應對稱的左括號), 例如 (()(())) (可以將程式碼自己stdout棧的內容會比較好懂唷 :D)

    • ( stack top [-1] back
    • (( stack top [-1,-1] back
    • (() stack top is -1, pop -1 out, push -1 in (source code line 17), now stack top [1,-1] back
    • (()( stack top [-1,1,-1] back
    • (()(( stack top [-1,-1,1,-1] back
    • (()(() pop -1 out, push -1 in stack top [1,-1,1,-1] back
    • (()(()) stack top is not -1, keep popping until -1 and x2 the pushed score in, pop -1 out, now stack top [2,1,-1] back
    • (()(())) stack top is not -1, keep popping until -1 and x2 the pushed score in, pop -1 out now stack top [6] back
    • 最後的while loop 將沒有加總完成的分數全數加總
  • 分析:Space complexity O(N), Time complexity O(N)

class Solution
{
public:
    int scoreOfParentheses(string str)
    {
        stack<int> stk;
        unsigned int total_score = 0;
        for(int i = 0; i < str.size(); i++)
        {
            int acculmulate_score = 0;
            if(str[i] == '(')
            {
                stk.push(-1);
            }
            else
            {
                if(stk.top() == -1)
                {
                    stk.pop();
                    stk.push(1);
                }
                else //keep adding until maching the symmetric part
                {
                    while(stk.top() != -1)
                    {
                        acculmulate_score += stk.top();
                        stk.pop();
                    }
                    stk.pop(); //pop the symmetrically matched left parenthesis
                    acculmulate_score *= 2;
                    stk.push(acculmulate_score);
                }
            }
        }
        //accumulate the rest if not finished
        while(stk.size())
        {
            total_score += stk.top();
            stk.pop();
        }
        return total_score;
    }
};