###### Agenda: ###### 10/11 22:00(UTC+8) 10/11 07:00(UTC-7) ###### 公布這次live session題目 ###### 10/11 22:30(UTC+8) 10/11 07:30(UTC-7) ###### 開始逐步給hint ###### 10/11 23:00(UTC+8) 10/11 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 766 #### https://leetcode.com/problems/toeplitz-matrix/description/ #### Leetcode 1004 #### https://leetcode.com/problems/max-consecutive-ones-iii/description/ --- ### Hint - Leetcode 766 : - hint 1: 參考一下基礎講義的陣列那一章的二維陣列 ---- ### Hint - Leetcode 766 : - hint 1: 參考一下基礎講義的陣列那一章的二維陣列 - hint 2: 想一想在答案為yes的情況下 每一個的數值會跟他周圍哪個人一樣 ---- ### Hint - Leetcode 766 : - hint 1: 參考一下基礎講義的陣列那一章的二維陣列 - hint 2: 想一想在答案為yes的情況下 每一個的數值會跟他周圍哪個人一樣 - hint 3: 假設有三格的數值為 a b c，若我們知道 a=b 也知道 b=c那我們就可以知道a=c --- ### Hint - Leetcode 1004 : - hint 1: 不用先考慮要翻哪幾個位子。 ---- ### Hint - Leetcode 1004 : - hint 1: 不用先考慮要翻哪幾個位子。 - hint 2: 不要朝直接找到最佳答案去想，嘗試窮舉出一些可能的答案，並從中找到最好的 ---- ### Hint - Leetcode 1004 : - hint 1: 不用先考慮要翻哪幾個位子。 - hint 2: 不要朝直接找到最佳答案去想，嘗試窮舉出一些可能的答案，並從中找到最好的 - hint 3: 找一個最長的subarray，他可以在k次操作內全部變成1 ---- ### Hint - Leetcode 1004 : - hint 1: 不用先考慮要翻哪幾個位子。 - hint 2: 不要朝直接找到最佳答案去想，嘗試窮舉出一些可能的答案，並從中找到最好的 - hint 3: 找一個最長的subarray，他可以在k次操作內全部變成1 - hint 4: 一個subarray若有<=k個0 就可以全部變成1 --- ### 題解 ---- ### Leetcode 766 題目 - 給你一個二維array，請確認這個二維array是否從左上到右下的每個斜線上數字都一樣 ---- ### Leetcode 766 - hint2: 一個符合題目要求的配置，每個格子$(x,y)$的左上$(x-1,y-1)$跟右下$(x+1,y+1)$會跟自己一樣 - 實際上檢查$(x-1,y-1)$就好了，$(x+1,y+1)$會在迴圈跑到他自己的時候檢查。 - 做這個檢查就好了 ---- ### Q1 java code ```java public boolean isToeplitzMatrix(int[][] matrix) { for(int i = 1; i < matrix.length ; i++) { for(int j = 1; j < matrix[0].length ; j++) { if(matrix[i][j]!=matrix[i-1][j-1]) { return false; } } } return true; } ``` ---- ### Test case - $n\gt m$ yes - $n\gt m$ no - $n\lt m$ yes - $n\lt m$ no - $n= m$ yes - $n= m$ no ---- ### Leetcode 1004 題目 - 給一個 array 裡面只有 $0$ 跟 $1$，最多可以把 $k$ 個位子的 $0$ 改成 $1$。 - 問最佳改動的情況下，改完之後最長且裡面都是$1$的 subarray 長度。 ---- ### Leetcode 1004 解法 - 先想給一個 subarray 我們可不可以在把 $k$ 個位子的 $0$ 改成 $1$ 的情況下，讓這個 subarray 都是 $1$。 - 裡面只有最多 $k$ 個 $0$。 - 對於每個位子當subarray的結尾，去找出可以延伸到的最左邊使得 subarray 內的 0 小於 $k$ 個。 - 參考一下課程 Session 3 ---- ### Leetcode 1004 ```java public int longestOnes(int[] nums, int k) { int l = 0, cnt = 0; int ans = 0; for(int i = 0 ; i < nums.length ; i++) { if(nums[i] == 0) { cnt++; } while(cnt > k){ if(nums[l] == 0) { cnt--; } l++; } ans = Math.max(i - l + 1, ans); } return ans; } ``` ---- ### Test case - count(0) < k - 會讓greedy錯的 - k = 2 - 1010111001110101 - 答案跟最連續的1無關 - k = 3 - 1110000110110110000111 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/FTdAnBFuh8HsDFVz7 -