###### Agenda: ###### 12/14 10:00(UTC+8) 12/13 19:00(UTC-7) ###### 公布這次live session題目 ###### 12/14 10:45(UTC+8) 12/13 19:45(UTC-7) ###### 開始逐步給hint ###### 12/14 11:30(UTC+8) 12/13 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode weekly contest 341 ### https://leetcode.com/contest/weekly-contest-341/ ### 中文題目 ### https://leetcode.cn/contest/weekly-contest-341/ --- ### Hint - Q1 : - ##### hint 1: 其實每一個 1 在哪個 column 並不重要 ---- ### Hint - Q1 - ##### hint 1: 其實每一個 1 在哪個 column 並不重要 - ##### hint 2: 因為數字只有 0 跟 1 ， 把數字家再一起就是1的數量 ---- ### Hint - Q1 - ##### hint 1: 其實每一個 1 在哪個 column 並不重要 - ##### hint 2: 因為數字只有 0 跟 1 ， 把數字家再一起就是1的數量 - ##### hint 3: 從第 0 個 row 往後找會比較好 maintain index 最小的 row --- ### Hint - Q2: - ##### hint 1: 要先搞清楚是誰可以被誰整除的關係，看一下範例會比較好懂 ---- ### Hint - Q2: - ##### hint 1: 要先搞清楚是誰可以被誰整除的關係，看一下範例會比較好懂 - ##### hint 2: 因為要找所有分數最高的裡面數字最小的，如果可以照大小順序判斷會比較簡單。 ---- ### Hint - Q2: - ##### hint 1: 要先搞清楚是誰可以被誰整除的關係，看一下範例會比較好懂 - ##### hint 2: 因為要找所有分數最高的裡面數字最小的，如果可以照大小順序判斷會比較簡單。 - ##### hint 3: 這題數字範圍不大，剩下的暴力處理就可以了 --- ### Hint - Q3 - ##### hint 1: 每一個字元，都可以用加兩個字元的方式讓它符合最終答案 ---- ### Hint - Q3 - ##### hint 1: 每一個字元，都可以用加兩個字元的方式讓它符合最終答案 - ##### hint 2: 因為可以 match 的 pattern 長度只有 3 ，所以可以把每種情況都分開討論一下 ---- ### Hint - Q3 - ##### hint 1: 每一個字元，都可以用加兩個字元的方式讓它符合最終答案 - ##### hint 2: 因為可以 match 的 pattern 長度只有 3 ，所以可以把每種情況都分開討論一下 - ##### hint 3: 長度為三可以 match 的很直覺。 ---- ### Hint - Q3 - ##### hint 1: 每一個字元，都可以用加兩個字元的方式讓它符合最終答案 - ##### hint 2: 因為可以 match 的 pattern 長度只有 3 ，所以可以把每種情況都分開討論一下 - ##### hint 3: 長度為三可以 match 的很直覺。 - ##### hint 4: 長度為二的可以加一個字元 match 的情況只有兩種。 ---- ### Hint - Q3 - ##### hint 1: 每一個字元，都可以用加兩個字元的方式讓它符合最終答案 - ##### hint 2: 因為可以 match 的 pattern 長度只有 3 ，所以可以把每種情況都分開討論一下 - ##### hint 3: 長度為三可以 match 的很直覺。 - ##### hint 4: 長度為二的可以加一個字元 match 的情況只有兩種。 - ##### hint 5: 剩下即為長度為一的，greedy的想法，一定希望一次 match 的越長越好。 --- ### Hint - Q4 - ##### hint 1: 考慮把問題分成兩部分，一部分把 trip 找出來，另一部分把決定誰的分數減半 ---- ### Hint - Q4 - ##### hint 1: 考慮把問題分成兩部分，一部分把 trip 找出來，另一部分把決定誰的分數減半 - ##### hint 2: 找 trip 可以從起點開始dfs， dfs 把走過的點都依序存起來，若往下走不到終點，那就把儲存的東西還原 ---- ### Hint - Q4 - ##### hint 1: 考慮把問題分成兩部分，一部分把 trip 找出來，另一部分把決定誰的分數減半 - ##### hint 2: 找 trip 可以從起點開始dfs， dfs 把走過的點都依序存起來，若往下走不到終點，那就把儲存的東西還原 - ##### hint 3: 決定把誰的分數減半，因為有個條件是相鄰數字不能同時減半，所以 greedy 會有問題 ---- ### Hint - Q4 - ##### hint 1: 考慮把問題分成兩部分，一部分把 trip 找出來，另一部分把決定誰的分數減半 - ##### hint 2: 找 trip 可以從起點開始dfs， dfs 把走過的點都依序存起來，若往下走不到終點，那就把儲存的東西還原 - ##### hint 3: 決定把誰的分數減半，因為有個條件是相鄰數字不能同時減半，所以 greedy 會有問題 - ##### hint 4: 其實我們只在意每個點被幾個trip蓋到，它的最終對分數的貢獻就是trip的數量*它的數字 ---- ### Hint - Q4 - ##### hint 1: 考慮把問題分成兩部分，一部分把 trip 找出來，另一部分把決定誰的分數減半 - ##### hint 2: 找 trip 可以從起點開始dfs， dfs 把走過的點都依序存起來，若往下走不到終點，那就把儲存的東西還原 - ##### hint 3: 決定把誰的分數減半，因為有個條件是相鄰數字不能同時減半，所以 greedy 會有問題 - ##### hint 4: 其實我們只在意每個點被幾個trip蓋到，它的最終對分數的貢獻就是trip的數量*它的數字 - ##### hint 5: 每個節點我們只考慮選或不選，一個節點可以選的條件為，它所有子樹都不選，反之就沒有差。 --- ### 題解 ---- ### Q1 題目 - 給一個 mxn matrix，問哪個 row 的 1 最多，如果有多個 row 的 1 數量相同，找出 index 最小的那個。 ---- ### Q1 - 直接把每個 row 數字加起來就相當於 1 的數量 - 從第 0 個 row 往下到最後一個 row，只有當 1 的數量更多的時候才去更新答案。 ---- ### Q1 c++ ```c++ //time complexity: O(n) //Extra space complexity: O(1) vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) { vector<int> ans{-1, -1}; for (int i = 0; i < mat.size(); i++) { int sum = 0; for (auto it : mat[i]) { sum += it; } if (sum > ans[1]) { ans[0] = i; ans[1] = sum; } } return ans; } ``` ---- ### Test case - 單一個row - 每個row 1 的數量相同 - 最後一個 row 1 的數量最多 ---- ### Q2 題目 - 給一些數字，跟一些除數。 問哪個除數可以整除最多的數字 - 若有多個，找出最小的那個。 ---- ### Q2 - 先把除數 sort 可以讓他小的會更早被判斷。 - 接下來就暴力檢查每個數字可不可以整數，跟 Q1 類似只有當答案更好的時候才更新答案 ---- ```c++ //time complexity: O(n*m) //Extra space complexity: O(1) int maxDivScore(vector<int>& nums, vector<int>& divisors) { sort(divisors.begin(), divisors.end()); int Max = -1, ans = 0; for (auto divisor : divisors) { int score = 0; for (auto num : nums) { if (num % divisor == 0) { score++; } } if (score > Max) { ans = divisor; Max = score; } } return ans; } ``` ---- ### Test case - 一樣的除數 - 除數大的可以整除比較多數字 - nums=[3,6,9] divisor=[2,3] - 很多除數可以整除一樣多數字 - nums=[3,4,6] divisor=[2,3] ---- ### Q3 題目 - 給一個string只有"abc"，加入盡量少的字元且不調換原本順序使得它變成"abc"*k ---- ### Q3 題目 - "ac" - -> "abc" - "a" - -> "abc" - "ca" - ->"abcabc" ---- ### Q3 - 因為要match的pattern很短，它在字串中出現的形式只有以下幾種 - "abc" "ab" "bc" "ac" "a" "b" "c" - 用以上幾種pattern 從小到大greedy去判斷並 match 就可以了 ---- ### Q3 code ```c++ int addMinimum(string word) { int ans = 0; for(int i = 0;i<word.size();i++){ // case "abc" if(i+2<word.size()&&word[i]=='a'&&word[i+1]=='b'&&word[i+2]=='c'){ i+=2; // case "ab" "bc" "ac" } else if(i+1<word.size()&&word[i]<word[i+1]){ i+=1; ans++; } else{ ans+=2; } } return ans; } ``` ---- ### Q3 - "abc" "ab" "bc" "ac" "a" "b" "c" - 其實重點只有前四個 pattern ，我們可以發現可以 match 的字元一定是遞增的，而如果兩個字元一樣或是往下，他們必然屬於不同的"abc" - 目標其實是讓盡量多的字元屬於同一個abc - 每一個字元可以先補兩個字元讓它變成abc - 若兩個字元可以屬於同一個abc則他們需要補的字元數量 - 3 - "ab"->"abcabc"->"abc" ---- ### Q3 code ```c++ int addMinimum(string word) { int ans = word.size() * 2; for (int i = 0; i + 1 < word.size(); i++) { if (word[i] < word[i + 1]) { ans -= 3; } } return ans; } ``` ---- ### Test case - 完全match - "abcabc" - match 長度2 - "ab" "bc" "ac" - match 長度1 - "ca" "cb" ---- ### Q4 題目 - 給一個樹，每個節點上有數字，接下來有一些trip會經過一些節點，我們需要算出所有trip走過的節點數字總和 - 我們可以將某些節點數字/2，但相鄰的節點不行同時/2 ---- ### Q4 題目  ---- ### Q4 - 每個節點只需考慮被幾個trip走過 - 最後在樹上面做dp，假設我們以1為樹的root。 - dp[x][0]，代表以x為root的子樹， - 在x不/2情況下總和最小為多少 - dp[x][1]，代表以x為root的子樹， - 在x/2情況下總和最小為多少 - $dp[x][0] = \sum min(dp[x所有的子節點][0], - dp[x所有的子節點][1])+val[x]$ - $dp[x][1] = \sum dp[x所有的子節點][0]+val[x]/2$ ---- ### Q4 code dfs 每個trip ``` c++ bool dfs(int s, int f, int t) { if (s == t) { cnt[s]++; return true; } for (auto it : v[s]) { if (it != f) { if (dfs(it, s, t)) { cnt[s]++; return true; } } } return false; } ``` ---- ### Q4 code 樹上的dp ``` c++ void dfs2(int x, int f) { for (auto it : v[x]) { if (it != f) { dfs2(it, x); dp[x][0] += min(dp[it][0], dp[it][1]); dp[x][1] += dp[it][0]; } } dp[x][0] += price[x] * cnt[x]; dp[x][1] += price[x] * cnt[x] / 2; } ``` ---- #### Q4 本體 ```c++ int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) { for (int i = 0; i < n; i++) { v[i].clear(); dp[i][0] = dp[i][1] = 0; } for (auto it : edges) { v[it[0]].push_back(it[1]); v[it[1]].push_back(it[0]); } for (auto it : trips) { dfs(it[0], it[0], it[1]); } dfs2(0, 0); return min(dp[0][0], dp[0][1]); } ``` ---- ### Test case - 分數最大的點不會被選到 - 0-1-2 trip = [0,2] - price=[9,10,9] - trip自己走到自己 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/CEWibpZ18o3WjvPG9 -