###### Agenda: ###### 10/12 10:00(UTC+8) 10/11 19:00(UTC-7) ###### 公布這次live session題目 ###### 10/12 10:45(UTC+8) 10/11 19:45(UTC-7) ###### 開始逐步給hint ###### 10/12 11:30(UTC+8) 10/11 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ## 本周題目 ## LeetCode biweekly contest 97 ## https://leetcode.com/contest/biweekly-contest-97/ --- ### Hint - Q1 : - hint 1: 想一想如何把一個數字每一位拿出來 ---- ### Hint - Q1 - hint 1: 想一想如何把一個數字每一位拿出來 - hint 2: %10 可以拿到一個數字的個位數 ---- ### Hint - Q1 - hint 1: 想一想如何把一個數字每一位拿出來 - hint 2: %10 可以拿到一個數字的個位數 - hint 3: /10 可以把數字十位數變個位數 --- ### Hint - Q2: - hint 1: n不大所以可以每一個數字掃過去 ---- ### Hint - Q2: - hint 1: n不大所以可以每一個數字掃過去 - hint 2: 如何高效率的判斷一個數字存不存在於banned ---- ### Hint - Q2: - hint 1: n不大所以可以每一個數字掃過去 - hint 2: 如何高效率的判斷一個數字存不存在於banned - hint 3: 在總和大小被限制的情況下，希望取得數字盡量多，一定希望先取小的 --- ### Hint - Q3 - hint 1: 兩個segment不要重疊會比較好 ---- ### Hint - Q3 - hint 1: 兩個segment不要重疊會比較好 - hint 2: segment的頭或尾貼著一個prize會比較好 ---- ### Hint - Q3 - hint 1: 兩個segment不要重疊會比較好 - hint 2: segment的頭或尾貼著一個prize會比較好 - hint 3: 可以統一讓prize貼在segment頭部，這樣只會有n種segment的可能性 ---- ### Hint - Q3 - hint 1: 兩個segment不要重疊會比較好 - hint 2: segment的頭或尾貼著一個prize會比較好 - hint 3: 可以統一讓prize貼在segment頭部，這樣只會有n種segment的可能性 - hint 4: 假設固定了第一個segment的位子，如何決定第二個segment的位子 --- ### Hint - Q4 - hint 1: 每走一步，x+y都會增大1 ---- ### Hint - Q4 - hint 1: 每走一步，x+y都會增大1 - hint 2: 若一個格子不能被起點走到，或是不能走到終點，把他標成0也不會影響答案 ---- ### Hint - Q4 - hint 1: 每走一步，x+y都會增大1 - hint 2: 若一個格子不能被起點走到，或是不能走到終點，把他標成0也不會影響答案 - hint 3: 考慮將棋盤逆時鐘轉45度看看 ---- ### Hint - Q4 - hint 1: 每走一步，x+y都會增大1 - hint 2: 若一個格子不能被起點走到，或是不能走到終點，把他標成0也不會影響答案 - hint 3: 考慮將棋盤逆時鐘轉45度看看 - hint 4: 旋轉45度後，grid由右往左被分成好幾層，會發現每次移動都會往右移動一層，思考一下每一層的點數對於答案的影響 --- ### 題解 ---- ### Q1 題目 - 給一些數字，在十進位情況下，將他們每一位拆開來。 - [12,34] -> [1,2,3,4] ---- ### Q1 - 考慮單一一個數字，%10可以取得個位數，/10可以將目前的個位數移掉，重複做到數字變成0就可以了。 - 記得上述方法取出來會是反的，要將他反轉。 ---- ### Q1 c++ code ```c++ vector<int> separateDigits(vector<int>& nums) { vector<int> ans; for(int num : nums) { vector<int> tmp; if(num == 0) { tmp.push_back(0); } while(num){ tmp.push_back(num % 10); num /= 10; } reverse(tmp.begin(), tmp.end()); for(int it : tmp){ ans.push_back(it); } } return ans; } ``` ---- ### Test case - 一位數 - 兩位會以上 - 有一位數為 0 - 單一一個 0 ---- ### Q2 題目 - 有$n$個數字，從$1$到$n$ - banned裡面的數字不能取 - 取越多數字的情況下，總和小於等於maxSum ---- ### Q2 題目 - 用HashTable 整理banned，這樣等下可以快速找到那些數字不能用。 - 一定先取最小的數字，所以直接用迴圈從1掃到n。 ---- ```c++ int maxCount(vector<int>& banned, int n, int maxSum) { unordered_set<int> visit; for(int num : banned) { visit.insert(num); } int sum = 0; int cnt = 0; for(int i = 1 ; i <= n ; i++) { if(visit.find(i) == visit.end() && sum + i <= maxSum) { sum += i; cnt++; } } return cnt; } ``` ---- ### Test case - 所有數字取完都不會超過maxSum - 所有數字取完會超過maxSum - 1 被 ban 掉 ---- ### Q3 題目 - 在數線上，某些位子有一些寶藏，第i個寶藏在$x_i$這個位子 - 用兩個線段長度最大為k個線段去蓋住這些寶藏，使得蓋到的寶藏數量最多 ---- ### Q3 - 以每個寶藏的位子當作線段的最左邊，去計算該線段可以蓋到多少寶藏 - 可以用 sliding window 先做計算。 - 窮舉最左邊線段的位子，根據greedy的想法我們希望兩個線段不重疊會比較好，因此計算在當前窮舉的位子尾巴的後面可以蓋到最多的寶藏 - 也可以用 sliding window 從右往左掃 - 注意當一個線段可以蓋住所有寶藏 ---- ```c++ int maximizeWin(vector<int>& prizePositions, int k) { vector<int> covered; int r = 0, cnt = 0; for (int prize : prizePositions) { while (r != prizePositions.size() && prizePositions[r] - prize <= k) { r++; cnt++; } covered.push_back(cnt); cnt--; } r = prizePositions.size(); int Max = 0, ans = 0; for (int i = prizePositions.size() - 1; i >= 0; i--) { while (prizePositions[r - 1] - prizePositions[i] > k) { r--; Max = max(Max, covered[r]); } ans = max(ans, Max + covered[i]); } return ans; } ``` ---- ### Test case - 一個線段可以蓋住所有寶藏 - Greedy會錯 - 直接選一個線段可以蓋住最多寶藏 - [1, 2, 5, 6, 7, 8, 9, 12, 13] k = 5 - 讓距離比較近的寶藏一起蓋住 - [1,4,5,8] k = 3 - 寶藏會剛好卡在線段的頭跟尾 - [1,3,4,6] k = 2 - 答案的線段會有一個蓋在剛好頭或剛好尾 - [1,2,3] k = 1 ---- ### Q4 題目 - 給一個 $m * n$ 的 grid，每一格為 $0$ 或 $1$ - 保證左上跟右下一定為 $1$ - 可以從最左上(0, 0)開始移動，每次只能移動往右或往下且只能到$1$的位子 - 判斷是否能將除了左上或右下外的其中一個 $1$ 改成 $0$，使得最左上走不到最右下 ---- ### Q4 - 根據hint 2，將不影響答案的格子先移掉 - 旋轉$45$度後，若除了頭尾外，存在一層的點數只剩下一個就是true，反之則為false。 - 假設最左邊是第0層，可以發現第$i$層的所有格子$(x,y)$，$x+y=i$ ---- ### 判斷起點能不能走到 ```c++ for (int i = 0; i < vis.size(); i++) { for (int j = 0; j < vis[0].size(); j++) { if ((i != 0 || j != 0) && vis[i][j] == 1) { if (i != 0 && vis[i - 1][j] == 1) { vis[i][j] = 1; } else if (j != 0 && vis[i][j - 1] == 1) { vis[i][j] = 1; } else { vis[i][j] = 0; } } } } ``` ---- ### 判斷能不能走到終點 ``` for (int i = vis2.size() - 1; i >= 0; i--) { for (int j = vis2[0].size() - 1; j >= 0; j--) { if ((i != vis2.size() - 1 || j != vis2[0].size() - 1) && vis2[i][j] == 1) { if (i != vis2.size() - 1 && vis2[i + 1][j] == 1) { vis2[i][j] = 1; } else if (j != vis2[0].size() - 1 && vis2[i][j + 1] == 1) { vis2[i][j] = 1; } else { vis2[i][j] = 0; } } } } ``` ---- ### 判斷答案 ``` for (int i = 1; i < grid.size() + grid[0].size() - 2; i++) { int cnt = 0; for (int j = 0; j < grid.size(); j++) { int x = j, y = i - j; if (y >= 0 && y < grid[0].size()) { if (vis[x][y] && vis2[x][y]) { cnt++; } } } if (cnt <= 1) return true; } return false; ``` ---- ### Test case - 答案為 no - 一開始就走不到 - 除了左上跟右下外都是 0 - n=1,m=1 - 在沒有做 hint2 的清除下，每一層都會有兩個以上的點 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/fgFqxJqTEdaZw1cDA -