###### Agenda: ###### 11/29 22:00(UTC+8) 11/29 07:00(UTC-7) ###### 公布這次live session題目 ###### 11/29 22:30(UTC+8) 11/29 07:30(UTC-7) ###### 開始逐步給hint ###### 11/29 23:00(UTC+8) 11/29 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 1894 #### https://leetcode.com/problems/find-the-student-that-will-replace-the-chalk/description/ #### Leetcode 827 #### https://leetcode.com/problems/making-a-large-island/description/ --- ### Hint - Leetcode 1894 : - hint 1: 一定會想照著題目做，但有沒有辦法模擬得快一點 ---- ### Hint - Leetcode 1894 : - hint 1: 一定會想照著題目做，但有沒有辦法模擬得快一點 - hint 2: 問題出在如果要重複從第一個人開始好幾次，會導致花比較多時間 ---- ### Hint - Leetcode 1894 : - hint 1: 一定會想照著題目做，但有沒有辦法模擬得快一點 - hint 2: 問題出在如果要重複從第一個人開始好幾次，會導致花比較多時間 - hint 3: 如果有方法在走訪完 array 一次後，只要在走訪 array 一次就可以得到答案，就可以解決這個問題了 ---- ### Hint - Leetcode 1894 : - hint 1: 一定會想照著題目做，但有沒有辦法模擬得快一點 - hint 2: 問題出在如果要重複從第一個人開始好幾次，會導致花比較多時間 - hint 3: 如果有方法在走訪完 array 一次後，只要在走訪 array 一次就可以得到答案，就可以解決這個問題了 - hint 4: 每走訪整個 array 一次，扣除的 chalk 都是固定的 --- ### Hint - Leetcode 827 : - hint 1: 可以每一格都轉換成 1 看看。 ---- ### Hint - Leetcode 827 : - hint 1: 可以每一格都轉換成 1 看看 - hint 2: 當某一格轉換成 1，會影響的範圍只有他的周圍四格 ---- ### Hint - Leetcode 827 : - hint 1: 可以每一格都轉換成 1 看看 - hint 2: 當某一格轉換成 1，會影響的範圍只有他的周圍四格 - hint 3: 可能可以預先計算出每個島的大小 ---- ### Hint - Leetcode 827 : - hint 1: 可以每一格都轉換成 1 看看 - hint 2: 當某一格轉換成 1，會影響的範圍只有他的周圍四格 - hint 3: 可以預先計算出每個島的大小 - hint 4: 需要處理原本就連在一起的島 --- ### 題解 ---- ### Leetcode 1894 題目 - 給一個array還有一個數字k，接著依序走過array的每個數字，若該數字$array[i] \le k$，則k = k - array[i]，反之回傳i。若走完整個array都還沒有回傳數字，則從頭再走一次，直到出現一個數字>k ---- ### Leetcode 1894 題目 - [5,1,5], k = 11 - 11 - array[0] = 6 - 6 - array[1] = 5 - 5 - array[2] = 0 - 0 < array[0], return 0 ---- ### Leetcode 1894 - 若要重複走過整個array數次會很花時間 - 每次走過整個array扣除的數字都相等 - 假設整個 array 總和為 sum，那可以直接把 k mod sum，之後只要再走一次就絕對會停下來 ---- ### LeetCode 1894 java code ```java //time complexity: O(n) //Extra space complexity: O(1) public int chalkReplacer(int[] chalk, int k) { long sum = 0; for(int value: chalk){ sum += value; } k %= sum; for(int i = 0;i<chalk.length;i++){ if(chalk[i]>k){ return i; } k-=chalk[i]; } return -1; } ``` ---- ### Test case - 剛好扣完 - [5,1,5] k = 11 - 不會走完整個array - [5,1,5] k = 6 - 第一個位子>k - [5,1,5] k = 4 ---- ### Leetcode 827 題目 - 給定一個0 1 的二維陣列，最多可以把一個0改成1，問做完上述操作後，最大可以得到多大的連通塊，裡面全部都是1。 - 兩個1連通，代表他們第一維加第二維的差距為1 ---- ### Leetcode 827 題目  ---- ### Leetcode 827 解法 - 用 disjoint set(union find)，把每個1都union起來，且我們也知道每一格若他是1，則他屬於哪個連通塊 - 接著將每一個0都翻成1看看，檢查上下左右是不是1，如果是的話把他們隸屬哪個連通塊記錄起來，最多只有四塊，將他們unique後算一下大小總和。 ---- ### Find ```java int[] parent, size; int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } ``` ---- ### 初始化 ```java int[] dX = { 0, 0, 1, -1 }; int[] dY = { 1, -1, 0, 0 }; int n = grid.length; int m = grid[0].length; int[][] id = new int[n][m]; int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { id[i][j] = index++; } } parent = new int[index]; size = new int[index]; for (int i = 0; i < index; i++) { parent[i] = i; size[i] = 1; } ``` ---- ### 對每個1做union find ```java for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { for (int k = 0; k < 4; k++) { int x = i + dX[k], y = j + dY[k]; if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) { int a = id[i][j], b = id[x][y]; int pa = find(a), pb = find(b); if (pa != pb) { parent[pa] = pb; size[pb] += size[pa]; } } } } } } ``` ---- ### 計算答案 ```java int ans = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 0) { HashSet<Integer> set = new HashSet<>(); for (int k = 0; k < 4; k++) { int x = i + dX[k], y = j + dY[k]; if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) { set.add(find(id[x][y])); } } int sum = 1; for (int root : set) { sum += size[root]; } ans = Math.max(ans, sum); } else { ans = Math.max(ans, size[find(id[i][j])]); } } } return ans; ``` ---- ### Test case - 全是1 - 全是0 - 只有一個連通塊 - 四個連通塊可以剛好被連在一起 - [0,1,0] - [1,0,1] - [0,1,0] ---- ### Test case - 有些陸地原本就被連在一起 - [1,1,0] - [1,0,1] - [0,1,0] - 長寬不同 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/oRp9u8AuQQqa4TDF9 -