###### 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 390 ### https://leetcode.com/contest/weekly-contest-390/ ### 中文題目 ### https://leetcode.cn/contest/weekly-contest-390/ --- ### 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: 真的沒想法，可以去看課程session 3 --- ### Hint - Q2: - ##### hint 1: 一定希望元素成長越快越好 ---- ### Hint - Q2: - ##### hint 1: 一定希望元素成長越快越好 - ##### hint 2: 第一個 operation 每次都只會讓總和長1 ---- ### Hint - Q2: - ##### hint 1: 一定希望元素成長越快越好 - ##### hint 2: 第一個 operation 每次都只會讓總和長1 - ##### hint 3: 第二個 operation 一定會想找最大那個 ---- ### Hint - Q2: - ##### hint 1: 一定希望元素成長越快越好 - ##### hint 2: 第一個 operation 每次都只會讓總和長1 - ##### hint 3: 第二個 operation 一定會想找最大那個 - ##### hint 4: 好像不會對一個元素，先做第二個元素，再做第一個 --- ### Hint - Q3 - ##### hint 1: 照著題目做就好了，但需要對於每個步驟要加速。 ---- ### Hint - Q3 - ##### hint 1: 照著題目做就好了，但需要對於每個步驟要加速。 - ##### hint 2: 需要一個能快速知道每個 ID 出現幾次的資料結構 ---- ### Hint - Q3 - ##### hint 1: 照著題目做就好了，但需要對於每個步驟要加速。 - ##### hint 2: 需要一個能快速知道每個 ID 出現幾次的資料結構 - ##### hint 3: 每次只會有一個 ID 數量變動，所以需要一個快速更新，且能找到最大值的資料結構 ---- ### Hint - Q3 - ##### hint 1: 照著題目做就好了，但需要對於每個步驟要加速。 - ##### hint 2: 需要一個能快速知道每個 ID 出現幾次的資料結構 - ##### hint 3: 每次只會有一個 ID 數量變動，所以需要一個快速更新，且能找到最大值的資料結構 - ##### hint 4: 有一些特殊情況必須處理，譬如說沒有任何ID的時候 --- ### Hint - Q4 - ##### hint 1: 把字串整個反轉過來，後綴就變成前綴 ---- ### Hint - Q4 - ##### hint 1: 把字串整個反轉過來，後綴就變成前綴 - ##### hint 2: 需要一個資料結構去維護跟字串前餟有關的東西 ---- ### Hint - Q4 - ##### hint 1: 把字串整個反轉過來，後綴就變成前綴 - ##### hint 2: 需要一個資料結構去維護跟字串前餟有關的東西 - ##### hint 3: 因為需要找到最早出現在 wordContainer 的，所以可能還要多儲存最找出現的是誰 ---- ### Hint - Q4 - ##### hint 1: 把字串整個反轉過來，後綴就變成前綴 - ##### hint 2: 需要一個資料結構去維護跟字串前餟有關的東西 - ##### hint 3: 因為需要找到最早出現在 wordContainer 的，所以可能還要多儲存最找出現的是誰 - ##### hint 4: 搜尋的時候，可能要好好處理，當一個前餟不存在的時候 ---- ### Hint - Q4 - ##### hint 1: 把字串整個反轉過來，後綴就變成前綴 - ##### hint 2: 需要一個資料結構去維護跟字串前餟有關的東西 - ##### hint 3: 因為需要找到最早出現在 wordContainer 的，所以可能還要多儲存最找出現的是誰 - ##### hint 4: 搜尋的時候，可能要好好處理，當一個前餟不存在的時候 - ##### hint 5: 如果真的沒想法，可以去看 session 11 --- ### 題解 ---- ### Q1 題目 - 給一個 array ，找出一個最長的 subarray，每個元素只出現最多兩次。 ---- ### Q1 - 可以參考 session 3，但原本只記錄每個元素元素有沒有出現過，現在要記錄出現了幾次 - 對於每個右界，找出最遠的左界，使得取出來的 subarray 符合條件 - 右界每增加一位，就去檢查增加的那個元素是否出現超過兩次了，如果是的話，就縮小左界直到該元素出現次數小於等於兩次。 ---- ### Q1 c++ ```c++ //time complexity: O(n) //Extra space complexity: O(1) int maximumLengthSubstring(string s) { int cnt[26]; fill(cnt, cnt + 26, 0); int ans = 0, l = 0; for (int i = 0; i < s.size(); i++) { cnt[s[i] - 'a']++; while (cnt[s[i] - 'a'] > 2) { cnt[s[l] - 'a']--; l++; } ans = max(ans, i - l + 1); } return ans; } ``` ---- ### Test case - 左界從來沒有移動過 - 每次都連續三個元素或以上出現 - "aaaaaa" - "aaabbb" - 1 個元素 - 2 個元素 ---- ### Q2 題目 - 給一個數字 k ，假設我們有一個array剛開始裡面只有一個1，接下來有兩種操作 - 選一個元素增加1 - 複製一個元素到array的最後 - 問最少操作數使的該 array 總和 >=k ---- ### Q2 - 一定會想先做完第一個操作再做第二個操作，這樣才會讓元素總和成長幅度最大 - 窮舉第一個操作要做幾次，再來看第二個操作需要做幾次才能>=k - 因為最後出來的答案會是 $(op1+1)*(op2+1)$，只要窮舉到$\sqrt k$就可以了 ---- ```c++ //time complexity: O(sqrt(k)) //Extra space complexity: O(1) int minOperations(int k) { int ans = k; for (int i = 1; i * i <= k; i++) { int j = (k - 1) / i + 1; ans = min(ans, i + j - 2); } return ans; } ``` ---- ### Test case - k = 1 - k = 2 ---- ### Q3 題目 - 總共會有 n 個事件發生，每個事件為某個 ID 會增加或減少一些數量 - 每次事件發生完，請找出 ID 數量最大的數量為多少 ---- ### Q3 題目 - add ID1 3 - ans = 3 - add ID2 5 - ans = 5 - sub ID2 3 - ans = 3 ---- ### Q3 - 把題目步驟拆解 - 增加或扣除某個ID的出現次數 - 在所有出現次數中找出最大值 - 增加或扣除某個ID的出現次數 - 可以用 hash table 去維護每個ID出現的次數 - 在所有出現次數中找出最大值 - 可以用 balanced binary search tree，找出最大值，並支援插入跟刪除 ---- ### Q3 code ```c++ vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) { unordered_map<int, long long> m; multiset<long long> s; vector<long long> ans; for (int i = 0; i < nums.size(); i++) { if (m[nums[i]]) { s.erase(s.find(m[nums[i]])); } m[nums[i]] += freq[i]; if (m[nums[i]]) { s.insert(m[nums[i]]); } if (m[nums[i]] == 0) { m.erase(nums[i]); } if (m.empty()) { ans.push_back(0); } else { ans.push_back(*s.rbegin()); } } return ans; } ``` ---- ### Test case - ID 全部被清完 - 出現數量最大的 ID 數量減少，使得它變成不是最多的 - 多個 ID 出現數量相同且最大 ---- ### Q4 題目 - 給一些 word，接下來有幾個 query，每個 query 會給一個 queryWord，問在給定的 word 中，哪一個跟 queryWord 有最長的後綴相同 - 若有多個，找出 index 比較前面的那個。 ---- ### Q4 題目 - word = ["aaa","baa","cba"] - query = "caa" -> "aaa" - query = "cbaa" -> "baa" - query = "ba" -> "cba" ---- ### Q4 - 可以參考 session 11 ，這題是有關字典樹的應用 - 字典樹每個節點代表一個前綴，每一條邊代表一個字母，走過那條邊代表在前綴上加上該字母 - "abc" ---a---> "abca" - 題目是問後綴，但 reverse 後其實就變前綴了 - 字典樹上每個節點就去紀錄，走到這個節點最小的index，跟最短的字串 - 詢問就在這個字典樹上走，直到要走的邊不存在，或是走到底了 ---- ### Q4 code trie build ``` c++ struct node { node* n[26]; pair<int, int> val; node() { for (int i = 0; i < 26; i++) n[i] = NULL; val = make_pair(0, 0); } }* root; void add(node*& n, const char* c, int index, int size) { if (n == NULL) { n = new node(); n->val = make_pair(size, index); } else { n->val = min(n->val, make_pair(size, index)); } if (*c == 0) { return; } add(n->n[(*c) - 'a'], c + 1, index, size); } ``` ---- ### Q4 code trie query ``` c++ int query(node* n, const char* c) { if (*c == 0 || n->n[(*c) - 'a'] == NULL || *c == 0) return n->val.second; else return query(n->n[(*c) - 'a'], c + 1); } ``` ---- #### Q4 本體 ```c++ vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) { for (auto& it : wordsContainer) reverse(it.begin(), it.end()); for (int i = 0; i < wordsContainer.size(); i++) add(root, wordsContainer[i].c_str(), i, wordsContainer[i].size()); vector<int> v; for (auto it : wordsQuery) { reverse(it.begin(), it.end()); v.push_back(query(root, it.c_str())); } return v; } ``` ---- ### Test case - 有相同前綴但長度比較短 - 比較短的 index 比較前面 - 比較短的 index 比較後面 - 有相同前綴且長度一樣 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/qBx7nGg1XKmbuuov7 -