###### Agenda: ###### 12/28 10:00(UTC+8) 12/27 19:00(UTC-7) ###### 公布這次live session題目 ###### 12/28 10:45(UTC+8) 12/27 19:45(UTC-7) ###### 開始逐步給hint ###### 12/28 11:30(UTC+8) 12/27 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode weekly contest 180 ### https://leetcode.com/contest/weekly-contest-180/ ### 中文題目 ### https://leetcode.cn/contest/weekly-contest-180/ --- ### Hint - Q1 : - ##### hint 1: 每一個元素去檢查有沒有符合答案 ---- ### Hint - Q1 - ##### hint 1: 每一個元素去檢查有沒有符合答案 - ##### hint 2: 可以先把每個column跟row的必要資訊算出來之後就不用重算 ---- ### Hint - Q1 - ##### hint 1: 每一個元素去檢查有沒有符合答案 - ##### hint 2: 可以先把每個column跟row的必要資訊算出來之後就不用重算 - ##### hint 3: row需要存最小值，column需要存最大值 --- ### Hint - Q2: - ##### hint 1: 其實大部分操作都跟stack 類似，除了inc ---- ### Hint - Q2: - ##### hint 1: 其實大部分操作都跟stack 類似，除了inc - ##### hint 2: inc 就是把某一個元素以前的所有數字都加上去 ---- ### Hint - Q2: - ##### hint 1: 其實大部分操作都跟stack 類似，除了inc - ##### hint 2: inc 就是把某一個元素以前的所有數字都加上去 - ##### hint 3: 假設inc增加前k個值的數值，第k-1個數值會在第k個數值存取之後才需要知道 ---- ### Hint - Q2: - ##### hint 1: 其實大部分操作都跟stack 類似，除了inc - ##### hint 2: inc 就是把某一個元素以前的所有數字都加上去 - ##### hint 3: 假設inc增加前k個值的數值，第k-1個數值會在第k個數值存取之後才需要知道 - ##### hint 4: 其實可以先把增加的值放在某一個元素身上，之後再往前推就好了 --- ### Hint - Q3 - ##### hint 1: 不用真的去思考如何旋轉整個二元樹 ---- ### Hint - Q3 - ##### hint 1: 不用真的去思考如何旋轉整個二元樹 - ##### hint 2: 題目就是造一顆平衡的二元樹包含給定的二元樹上所有數值 ---- ### Hint - Q3 - ##### hint 1: 不用真的去思考如何旋轉整個二元樹 - ##### hint 2: 題目就是造一顆平衡的二元樹包含給定的二元樹上所有數值 - ##### hint 3: 選來當root的節點，所有比他小的數字都會在左子樹，所有比他大的數字都會在右子樹 ---- ### Hint - Q3 - ##### hint 1: 不用真的去思考如何旋轉整個二元樹 - ##### hint 2: 題目就是造一顆平衡的二元樹包含給定的二元樹上所有數值 - ##### hint 3: 選來當root的節點，所有比他小的數字都會在左子樹，所有比他大的數字都會在右子樹 - ##### hint 4: 如果二元樹兩邊子樹的size差距<=1他們其實就會平衡了 --- ### Hint - Q4 - ##### hint 1: 不要一次就想直接算出最佳解，可以考慮每一種可能的方式並從中選出最好的 ---- ### Hint - Q4 - ##### hint 1: 不要一次就想直接算出最佳解，可以考慮每一種可能的方式並從中選出最好的 - ##### hint 2: 考慮每次都固定一個最低的efficiency，那speed會如何選擇 ---- ### Hint - Q4 - ##### hint 1: 不要一次就想直接算出最佳解，可以考慮每一種可能的方式並從中選出最好的 - ##### hint 2: 考慮每次都固定一個最低的efficiency，那speed會如何選擇 - ##### hint 3: 因為不想要當嘗試另一個efficiency的時候就要全部重算，efficiency的考慮順序很重要 ---- ### Hint - Q4 - ##### hint 1: 不要一次就想直接算出最佳解，可以考慮每一種可能的方式並從中選出最好的 - ##### hint 2: 沒考慮每次都固定一個最低的efficiency，那speed會如何選擇 - ##### hint 3: 因為不想要當嘗試另一個efficiency的時候就要全部重算，efficiency的考慮順序很重要 - ##### hint 4: 若每次考慮的speed都會增加一個，我們想要取前k大的要怎麼做，相當於把不是前k大的移除掉 --- ### 題解 ---- ### Q1 題目 - 給一個matrix，每個數字都不同，找出所有數字符合下列條件 - 該數字在他所屬的row上是最小的 - 該數字在他所屬的column上是最大的 ---- ### Q1 - 可以先計算出每個row的最小值跟每個column的最大值 - 接下來搜尋每個元素，看該row的最小值與該column的最大值是否與該值相同即可 ---- ### Q1 c++ ```c++ //time complexity: O(n*m) //Extra space complexity: O(n+m) vector<int> luckyNumbers(vector<vector<int>>& matrix) { int n = matrix.size(); int m = matrix[0].size(); vector<int> res; vector<int> row(n, INT_MAX), column(m, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { row[i] = min(row[i], matrix[i][j]); column[j] = max(column[j], matrix[i][j]); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (row[i] == matrix[i][j] && column[j] == matrix[i][j]) { res.push_back(matrix[i][j]); } } } return res; } ``` ---- ### Test case - 沒有答案 - [1,3] - [4,2] - 一個答案 - [1,3] - [2,4] ---- ### Q2 題目 - 寫一個資料結構支援以下操作 - 最多只能儲存maxSize個數字 - push x 放入一個值在最上面，若當下已經存了maxSize個數字，則不做任何事 - pop 取出並移除最上面的值，若資料結構已經空了，則回傳-1 - inc k val將最底下k個值增加val，若資料結構內資料<=k個則全部增加val ---- ### Q2 題目 - push 2 ->[2] - push 3 ->[2,3] - push 4 ->[2,3,4] - add 2 4 ->[6,7,4] - pop -> [6,7] 4 ---- ### Q2 - 其實大部分操作跟stack差不多所以可以用一個stack去模擬 - inc這個操作可以直接操作在第k個元素上，但用一個額外的數字去記錄，當我使用到這個元素時，就把相關的資料再加給第k-1個元素就好了 ---- ```c++ //time complexity for eacy operation: O(1) //Extra space complexity: O(|operations|) vector<pair<int, int>> stk; int size; CustomStack(int maxSize) { size = maxSize; } void push(int x) { if (stk.size() != size) { stk.push_back(make_pair(x, 0)); } } int pop() { if (stk.empty()){ return -1; } pair<int, int> p = stk.back(); stk.pop_back(); if (stk.size()) { stk.back().second += p.second; } return p.first + p.second; } void increment(int k, int val) { if (stk.size()) { stk[min(k, (int)stk.size()) - 1].second += val; } } ``` ---- ### Test case - 加入數字超過 maxSize個 - 當資料結構空了執行pop - inc的資料數量超過當下的資料總數 ---- ### Q3 題目 - 給一個binary search tree，請將他平衡 - 平衡的binary search tree的定義為，每一個子樹，左子樹跟右子樹的高度相差<=1 ---- ### Q3 題目 -  ---- ### Q3 - 題目其實是在說AVL tree的定義 - AVL tree可以做到空間O(1)時間O(n) - 但可以直接把所有數字取出來後自己重新組裝一個balanced binary search tree - 照數字大小去把數字取出來可以做到空間O(n)時間O(n) ---- ### Q3 code ```c++ //time complexity: O(n) //Extra space complexity: O(n) vector<int> v; void dfs(TreeNode* n) { if (!n) { return; } dfs(n->left); v.push_back(n->val); dfs(n->right); } TreeNode* build(int l, int r) { if (l > r) { return NULL; } TreeNode* res = new TreeNode(v[(l + r) / 2]); int mid = (l + r) / 2; res->left = build(l, mid - 1); res->right = build(mid + 1, r); return res; } TreeNode* balanceBST(TreeNode* root) { dfs(root); return build(0, v.size() - 1); } ``` ---- ### Test case - 一個節點 - 原本樹就平衡 - 一條鍊 ---- ### Q4 題目 - 有n個人，每個人有兩個數值，speed efficiency，要挑最多k個人組成一個team，team的performace定義為，所有人裡最低的efficiency * 所有人的speed總和 ---- ### Q4 題目 - speed= [2,4,6] efficiency = [1,3,5] -> performace = (2+4+6)*1 = 12 - speed= [6] efficiency = [5] -> performace = 6*5 = 30 ---- ### Q4 - 將efficiency從大到小排，然後從最大的依序考慮 - 那speed就是前面有考慮過的人中挑前k大的，因為這些人的efficiency都比當下的人高，所以只需要知道當下的人的efficiency就好了 - 挑前k大的方法就是，使用priority queue儲存我目前有考慮的人，每次多考慮一個人時就把speed放進priority queue，若裡面存超過k個人時，就將最小speed的人移除 ---- ### Q4 code ``` c++ //time complexity: O(nlogn) //Extra space complexity: O(nlogn) const int mod = 1e9+7; int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) { vector<pair<int, int>> p(n); for (int i = 0; i < n; i++) { p[i] = make_pair(efficiency[i], speed[i]); } sort(p.begin(), p.end()); reverse(p.begin(), p.end()); priority_queue<int,vector<int>,greater<int>> pq; long long ans = 0, sum = 0; for (int i = 0; i < n; i++) { sum += p[i].second; pq.push(p[i].second); if(pq.size()>k){ sum-=pq.top(); pq.pop(); } ans = max(ans, p[i].first * sum); } return ans % mod; } ``` ---- ### Test case - 挑少於k個人會比較好 - k=3 - speed= [2,4,6] efficiency = [1,3,5] - efficiency遞增 speed遞減 - k=2 - speed= [4,3,2,1] efficiency = [1,2,3,4] --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/vKPEDpArJhi1wpq1A