###### Agenda: ###### 10/19 10:00(UTC+8) 10/18 19:00(UTC-7) ###### 公布這次live session題目 ###### 10/19 10:45(UTC+8) 10/18 19:45(UTC-7) ###### 開始逐步給hint ###### 10/19 11:30(UTC+8) 10/18 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode biweekly contest 114 ### https://leetcode.com/contest/biweekly-contest-114/ ### 中文題目 ### https://leetcode.cn/contest/biweekly-contest-114/ --- ### Hint - Q1 : - ##### hint 1: 如何判斷一個數字有沒有被收集過了 ---- ### Hint - Q1 - ##### hint 1: 如何判斷一個數字有沒有被收集過了 - ##### hint 2: 照著題目的操作做 ---- ### Hint - Q1 - ##### hint 1: 如何判斷一個數字有沒有被收集過了 - ##### hint 2: 照著題目的操作做 - ##### hint 3: 如何判斷符合題目要求 ---- ### Hint - Q1 - ##### hint 1: 如何判斷一個數字有沒有被收集過了 - ##### hint 2: 照著題目的操作做 - ##### hint 3: 如何判斷符合題目要求 - ##### hint 4: 不重複且數字<=k的數字數量==k時就滿足題目要求了 --- ### Hint - Q2: - ##### hint 1: array順序不重要 ---- ### Hint - Q2: - ##### hint 1: array順序不重要 - ##### hint 2: 想一想哪種情況不能湊出來 ---- ### Hint - Q2: - ##### hint 1: array順序不重要 - ##### hint 2: 想一想哪種情況不能湊出來 - ##### hint 3: 任何一個>1的數字，都可以被3跟2湊出來 ---- ### Hint - Q2: - ##### hint 1: array順序不重要 - ##### hint 2: 想一想哪種情況不能湊出來 - ##### hint 3: 任何一個>1的數字，都可以被3跟2湊出來 - ##### hint 4: 假設全部用3去湊，最後剩1的時侯就把前一次的3拿回來用2個2去湊 --- ### Hint - Q3 - ##### hint 1: 整個array不切的score是最小的 ---- ### Hint - Q3 - ##### hint 1: 整個array不切的score是最小的 - ##### hint 2: 先考慮單一一個bit ---- ### Hint - Q3 - ##### hint 1: 整個array不切的score是最小的 - ##### hint 2: 先考慮單一一個bit 若有一個bit整個array上的數字該bit都為1，把它分成兩半，會導致總分變高 - ##### hint 3: 會希望每個subarray score都是0 ---- ### Hint - Q3 - ##### hint 1: 整個array不切的score是最小的 - ##### hint 2: 先考慮單一一個bit 若有一個bit整個array上的數字該bit都為1，把它分成兩半，會導致總分變高 - ##### hint 3: 會希望每個subarray score都是0 - ##### hint 4: subarray越長越有可能score是0，假如我們從尾巴切除了一個score為0的subarray，那剩下的問題就跟原本很類似了 ---- ### Hint - Q3 - ##### hint 1: 整個array不切的score是最小的 - ##### hint 2: 先考慮單一一個bit 若有一個bit整個array上的數字該bit都為1，把它分成兩半，會導致總分變高 - ##### hint 3: 會希望每個subarray score都是0 - ##### hint 4: subarray越長越有可能score是0，假如我們從尾巴切除了一個score為0的subarray，那剩下的問題就跟原本很類似了 - ##### hint 5: 考慮一個dp狀態，取前k個數字，且每個subarray的總分皆為0，最多可以切成幾段 --- ### Hint - Q4 - ##### hint 1: 重新整理一下這張圖吧 想一想圖要怎麼存會只去走需要的邊 ---- ### Hint - Q4 - ##### hint 1: 重新整理一下這張圖吧 想一想圖要怎麼存會只去走需要的邊 - ##### hint 2: 題目有個條件: Sum of values is divisible by k ---- ### Hint - Q4 - ##### hint 1: 重新整理一下這張圖吧 想一想圖要怎麼存會只去走需要的邊 - ##### hint 2: 題目有個條件: Sum of values is divisible by k - ##### hint 3: 可以先假設一個點為樹的root，考慮下面的子樹，把樹移掉一條邊會分成兩張圖，一張圖含有根，另一張圖不含，不含根的那張圖就稱為子樹，該子樹的根為原本邊連到的點 ---- ### Hint - Q4 - ##### hint 1: 重新整理一下這張圖吧 想一想圖要怎麼存會只去走需要的邊 - ##### hint 2: 題目有個條件: Sum of values is divisible by k - ##### hint 3: 可以先假設一個點為樹的root，考慮下面的子樹，把樹移掉一條邊會分成兩張圖，一張圖含有根，另一張圖不含，不含根的那張圖就稱為子樹，該子樹的根為原本邊連到的點 - ##### hint 4: 一棵樹的總和為x 假設他切除了一塊總和為y的子樹 那該樹剩下的總和為x-y ---- ### Hint - Q4 - ##### hint 1: 重新整理一下這張圖吧 想一想圖要怎麼存會只去走需要的邊 - ##### hint 2: 題目有個條件: Sum of values is divisible by k - ##### hint 3: 可以先假設一個點為樹的root，考慮下面的子樹，把樹移掉一條邊會分成兩張圖，一張圖含有根，另一張圖不含，不含根的那張圖就稱為子樹，該子樹的根為原本邊連到的點 - ##### hint 4: 一棵樹的總和為x 假設他切除了一塊總和為y的子樹 那該樹剩下的總和為x-y - ##### hint 5: 一棵樹的總和mod k 為k，假設他切除了一塊總和mod k為0的，那該樹剩下的總和mod k為0 --- ### 題解 ---- ### Q1 題目 - 每一次操作可以收集 array 最結尾的數字，問最少要做幾次操作後可以蒐集到1~k所有的數字 - [2,3,1] collected = [] - 一次操作後 [2,3] collected = {1} - 兩次操作後 [2] collected = {1,3} - 三次操作後 [] collected = {1,2,3} ---- ### Q1 - 每次把最後一個數字拿出來 - 如果收集過了或$>k$，就當沒事 - 如果沒收集過而且$\leq k$，則收集的數字數量 + 1 - 當收集的數字數量 = k時結束 ---- ### Q1 - [2,3,3,1] collected = [], k = 3, 收集數量 = 0 - 一次操作後 [2,3,3] collected = {1}, 收集數量 = 1 - 兩次操作後 [2,3] collected = {1,3}, 收集數量 = 2 - 三次操作後 [2] collected = {1,3},收集數量 = 2 - 四次操作後 [] collected = {1,2,3},收集數量 = 3 ---- ### Q1 c++ code ```c++ int minOperations(vector<int>& nums, int k) { unordered_set<int> vis; int cnt = 0; for (int i = nums.size() - 1; i >= 0; i--) { cnt++; if (nums[i] <= k) { vis.insert(nums[i]); } if (vis.size() == k) { return cnt; } } return 0; } ``` ---- ### Test case - array用完才蒐集到 - [3,2,1] k = 3 - 有重複且<=k的數字 - [3,2,2,1] k = 3 - 重複的數字出現在達成條件之後 - [3,3,2,1] k = 3 - 有重複但>k的數字 - [3,4,4,2,1] k = 3 ---- ### Q2 題目 - 給一個array，裡面有一些數字 - 每次可以執行兩種操作其中一種 - 挑兩個一樣的數字刪掉 - 挑三個一樣的數字刪掉 - 問最少需要多少次操作才能把array全部刪除，達不到return -1 ---- ### Q2 題目 - [2,2,5,5,5] - 移除2個2 [5,5,5] - 移除3個5 [] - 總共兩次操作 ---- ### Q2 - 計算每個數字的數量 - 若存在一個數量 = 1 return -1 - 剩下的就是 /3 然後有餘數在+1 ---- ```c++ int minOperations(vector<int>& nums) { int ans = 0; unordered_map<int, int> m; for (auto num : nums) { m[num]++; } for (auto const& [num, cnt] : m) { if (cnt == 1) { return -1; } else { ans += cnt / 3; if (cnt % 3 != 0) { ans++; } } } return ans; } ``` ---- ### Test case - 有數字只出現一次 - [1] - 有數字只出現兩次 - [1,1] - 有數字只出現三次 - [1,1,1] - 有數字只出現四次 - [1,1,1,1] - 數字沒排序過 - [1,2,1,2] - [1,2,1] ---- ### Q3 題目 - 給一個array裡面有一些數字，我們需要將他們切成幾個subarray，使得每個元素屬於剛好一個subarray - 每個subarray的分數為裡面所有數字 AND(&)起來，希望分數的總和越小越好 - 求分數總和最小的情況下，切成越多段越好 ---- ### Q3 題目 -[0,1,2,3,8] - 可以切成 - [0] [1,2,3] [8] - 三段分數為 0, 0, 8 - $1 = (01)_2$ - $2 = (10)_2$ - $3 = (11)_2$ ---- ### Q3 - 符合hint 2，就不會去切subarray - 根據hint 4想到dp， dp[x] 代表前x項，總分為0最多可以切幾個subarray。 - dp[x]一定會越來越大，我們會希望每一個bit都包到0 - 去記錄每個bit最後一次0出現在哪一個位子，那dp[x]就可以從該位子的前一個位子轉移來 - $(00)_2,(01)_2,(10)_2,(11)_2,(01)_2$ ---- ```c++ int maxSubarrays(vector<int>& nums) { int res = nums[0]; for (auto it : nums) { res &= it; } if (res) { return 1; } vector<int> dp(nums.size(), -1); int last[20]; fill(last, last + 20, -1); for (int i = 0; i < nums.size(); i++) { for (int j = 0; j < 20; j++) { if ((nums[i] & (1 << j)) == 0) { last[j] = i; } } int Min = i; for (int j = 0; j < 20; j++) { Min = min(Min, last[j]); } if (Min == -1) { dp[i] = -1; } else if (Min == 0 || dp[Min - 1] == -1) { dp[i] = 1; } else { dp[i] = dp[Min - 1] + 1; } } return dp[nums.size() - 1]; } ``` ---- ### Test case - 有一個bit全部為1 - [3,2,3] - 有一個bit只有1個為0的 - [1,0,1] - 2個或以上的bit要考慮而且會交錯的 - [0,1,2,3,1,2,1] ---- ### Q4 題目 - 給定一個樹(tree)，要將他切成盡量多塊，使的每塊的總和都是k的倍數 ---- ### Q4 題目 - [3,0,6,1,5,2,1], k = 3  ---- ### Q4 - 若我們找到一條邊使得切下去的兩邊 mod k都為0，就找到一個答案了 - 根據hint 5 ，發現上述條件不會相互影響，也就是某一條邊切完後，其他的邊切下去也符合切下去的兩邊mod k為0 - 所以就dfs下去，判斷如果下面的子樹總和mod k為0，就把他切一刀。 ---- ### Q4 - [3,0,6,1,5,2,1], k = 3  ---- ### dfs part ```java vector<vector<int>> edge; vector<int> sum; void dfs(int v, int f, int k, vector<int>& values) { for (auto u : edge[v]) { if (u != f) { dfs(u, v, k, values); sum[v] += sum[u]; sum[v] %= k; } } sum[v] += values[v]; sum[v] %= k; if (sum[v] == 0) { ans++; } } ``` ---- ### Test case - 每個節點%k都是0 - 不存在可以切任何地方 - k=5 [1,1,1,1,1] -  - 可以切一個地方 - k = 5 [2,2,1,3,2] --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/rix3P46PmXcQLAsu9 -