###### Agenda: ###### 12/07 10:00(UTC+8) 12/06 19:00(UTC-7) ###### 公布這次live session題目 ###### 12/07 10:45(UTC+8) 12/06 19:45(UTC-7) ###### 開始逐步給hint ###### 12/07 11:30(UTC+8) 12/06 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode biweekly contest 108 ### https://leetcode.com/contest/biweekly-contest-108/ ### 中文題目 ### https://leetcode.cn/contest/biweekly-contest-108/ --- ### Hint - Q1 : - ##### hint 1: 其實題目就是要找一個最長 subarray，他長的樣子是$[a,a+1,a,a+1....]$ ---- ### Hint - Q1 - ##### hint 1: 其實題目就是要找一個最長 subarray，他長的樣子是$[a,a+1,a,a+1....]$ - ##### hint 2: 符合答案的array，確定好前兩個數字後，後面也都確定了 ---- ### Hint - Q1 - ##### hint 1: 其實題目就是要找一個最長 array，他長的樣子是$[a,a+1,a,a+1....]$ - ##### hint 2: 符合答案的array，確定好前兩個數字後，後面也都確定了 - ##### hint 3: 這題$O(n^2)$可以過，但實際上可以做到O(n) ---- ### Hint - Q1 - ##### hint 1: 其實題目就是要找一個最長 array，他長的樣子是$[a,a+1,a,a+1....]$ - ##### hint 2: 符合答案的array，確定好前兩個數字後，後面也都確定了 - ##### hint 3: 這題$O(n^2)$可以過，但實際上可以做到O(n) - ##### hint 4: 若當前的答案延長到後面發現不符合答案了，可以只留最後兩項或最後一項再繼續做 --- ### 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: 觀察一下題目範圍 ---- ### Hint - Q3 - ##### hint 1: 想像一下最後答案出來長什麼樣子 - ##### hint 2: 觀察一下題目範圍 - ##### hint 3: 題目的範圍讓任意一個substring 轉換成數字後都不會int範圍的問題 ---- ### Hint - Q3 - ##### hint 1: 想像一下最後答案出來長什麼樣子 - ##### hint 2: 觀察一下題目範圍 - ##### hint 3: 題目的範圍讓任意一個substring 轉換成數字後都不會int範圍的問題 - ##### hint 4: 思考一下答案的partition，若把最後一個partition移掉，其實還是一個類似的問題 --- ### Hint - Q4 - ##### hint 1: 每一個黑色格子只會影響周圍四格 ---- ### Hint - Q4 - ##### hint 1: 每一個黑色格子只會影響周圍四個 2*2的矩陣 - ##### hint 2: 沒有被影響到的就都是白色的 ---- ### Hint - Q4 - ##### hint 1: 每一個黑色格子只會影響周圍四格 - ##### hint 2: 沒有被影響到的就都是白色的 - ##### hint 3: 可能需要一個資料結構去快速找到某一格是不是黑色的 ---- ### Hint - Q4 - ##### hint 1: 每一個黑色格子只會影響周圍四格 - ##### hint 2: 沒有被影響到的就都是白色的 - ##### hint 3: 可能需要一個資料結構去快速找到某一格是不是黑色的 - ##### hint 4: 也需要另一個資料結構去找哪一個2*2被計算過了 --- ### 題解 ---- ### Q1 題目 - 給一個array，要找一個最長 subarray，他長的樣子是$[a,a+1,a,a+1....]$ ---- ### Q1 - 如果我們知道答案array的前兩個數字了，後面就確定了，可以直接比對後面是不是符合答案 - 當不符合答案時，可以分成以下幾種情況 - a+1 後面接 a+2 - a+1 -> a+2 可以當成一個新的開頭 - a 後面接 a-1 - 由於開頭一定是要a->a+1，因此也直接開始計算新的 - 其他 - 其他情況因為完全沒辦法將他接起來因此可以直接開始計算新的 ---- ### Q1 c++ ```c++ //time complexity: O(n) //Extra space complexity: O(1) int alternatingSubarray(vector<int>& nums) { int ans = 0; int cnt = 0; int last = nums[0], flag = 1; for (auto it : nums) { if (it == last + flag) { cnt++; flag = -flag; last = it; } else { if (it == last + 1) { flag = -1; cnt = 2; } else { flag = 1; cnt = 1; } last = it; } ans = max(cnt, ans); } if (ans <= 1) { return -1; } return ans; } ``` ---- ### Test case - 整條array都是答案 - array長度為1 - 不符合答案的第一種case - [1,2,3,2,3] - 不符合答案的第二種case - [2,3,2,1,2,1,2] ---- ### Q2 題目 - 給一個array裡面有些數字，接下來有一些操作，每個操作是把array中某個數字換成另一個數字 - 問最後那些數字有出現過，排序後回傳 ---- ### Q2 題目 - [1,2,3] - moveFrom 1 To 2 - [2,2,3] - moveFrom 2 To 3 - [3,3,3] - return [3] ---- ### Q2 - 因為回傳值的關係，只需要考慮某個數字有沒有出現過。 - 需要一個資料結構支援，快速找到及刪除(moveFrom)，及快速加入(moveTo) - HashTable - 因為最後還是需要排序，所以用ordered set也可以。 ---- ```c++ //time complexity: O(nlogn) //Extra space complexity: O(n) vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) { set<int> s; for(auto it:nums){ s.insert(it); } for(int i = 0;i<moveFrom.size();i++){ if(s.find(moveFrom[i])==s.end()){ continue; } s.erase(moveFrom[i]); s.insert(moveTo[i]); } vector<int> ans; for(auto it:s){ ans.push_back(it); } return ans; } ``` ---- ### Test case - 所有數字剛開始就相同 - moveFrom的數字最後還是會出現 - [1,2] - moveFrom 2 to 3 - moveFrom 1 to 2 ---- ### Q3 題目 - 給一個binary array，請將它分成，盡量少的substring，使得每個字元都屬於剛好一個substring，且substring符合以下條件 - 該substring第一個字元非0 - 該substring轉成十進位後是5的次方 ---- ### Q3 題目 - 11011 - [1][101][1] ---- ### Q3 - 由於字串長度很短，所以不用擔心整數會存不下 - dp[i]為考慮前i個字元，最少需要多少partition才能符合條件 - dp[i] = dp[j-1] + 1 if(s[j..i]轉成十進位為5的次方) ---- ### Q3 code ```c++ bool isPow5(int x) { while (x % 5 == 0) { x /= 5; } return x == 1; } int minimumBeautifulSubstrings(string s) { vector<int> dp(s.size(), -1); for (int i = 0; i < s.size(); i++) { int val = 0; if (s[i] != '0' && (i == 0 || dp[i - 1] != -1)) { for (int j = i; j < s.size(); j++) { val = val * 2 + s[j] - '0'; if (isPow5(val)) { if (i == 0) { dp[j] = 1; } else { if (dp[j] == -1) { dp[j] = dp[i - 1] + 1; } else { dp[j] = min(dp[j], dp[i - 1] + 1); } } } } } } return dp[s.size() - 1]; } ``` ---- ### Test case - 可以切出答案 - 1 - 沒切出答案 - 01 - 110 ---- ### Q4 題目 - 有一個很大的grid，裡面有一些黑色格子，問這個很大的grid中，所有2*2的子grid，黑色格子數量為0 1 2 3 4的各有幾個 ---- ### Q4 題目  - [3,1,0,0,0] ---- ### Q4 - 只需要考慮所有黑色格子，左邊，上面，左上，及他自己做為2*2矩陣的左上角即可 - 對於每個要考慮的2*2矩陣，去檢查每格是不是black - 另外還要記錄已經考慮過得2*2矩陣 - 全白的2*2矩陣就是由(n-1)*(m-1)減去有黑色的矩陣 ---- ### Q4 code ``` c++ //time complexity: O(|coordinates|) //Extra space complexity: O(|coordinates|) vector<long long> countBlackBlocks(int n, int m, vector<vector<int>>& coordinates) { vector<long long> ans{0, 0, 0, 0, 0}; set<pair<int, int>> vis;// a hash table set<pair<int, int>> black;// a hash table for (auto it : coordinates) { black.insert(make_pair(it[0], it[1])); } int X[4] = {0, 0, 1, 1}, Y[4] = {0, 1, 0, 1}; for (auto it : black) { for (int j = -1; j <= 0; j++) { for (int k = -1; k <= 0; k++) { int x = it.first + j, y = it.second + k; if (x >= 0 && x < n - 1 && y >= 0 && y < m - 1 && vis.find(make_pair(x, y)) == vis.end()) { vis.insert(make_pair(x, y)); int cnt = 0; for (int a = 0; a < 4; a++) { int xx = x + X[a], yy = y + Y[a]; if (black.find(make_pair(xx, yy)) != black.end()) cnt++; } ans[cnt]++; } } } } ans[0] += (n - 1) * 1ll * (m - 1) - ans[1] - ans[2] - ans[3] - ans[4]; return ans; } ``` ---- ### Test case - 黑色格子佔據的各種情況 -  -   --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/GWGg38fveZ35dSoA9