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; } };