###### Agenda: ###### 12/20 22:00(UTC+8) 12/20 07:00(UTC-7) ###### 公布這次live session題目 ###### 12/20 22:30(UTC+8) 12/20 07:30(UTC-7) ###### 開始逐步給hint ###### 12/20 23:00(UTC+8) 12/20 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 836 #### https://leetcode.com/problems/rectangle-overlap/description/ #### Leetcode 1733 #### https://leetcode.com/problems/minimum-number-of-people-to-teach/description/ --- ### Hint - Leetcode 836 : - hint 1: 兩個長方形 overlap，代表他們有同時蓋到一個點 ---- ### Hint - Leetcode 836 : - hint 1: 兩個長方形 overlap，代表他們有同時蓋到一個點 - hint 2: 想一下長方形重疊有哪幾種情況 ---- ### Hint - Leetcode 836 : - hint 1: 兩個長方形 overlap，代表他們有同時蓋到一個點 - hint 2: 想一下長方形重疊有哪幾種情況 - hint 3: 反過來想想兩個長方形不重疊的話，會有什麼樣的特性 ---- ### Hint - Leetcode 836 : - hint 1:兩個長方形 overlap，代表他們有同時蓋到一個點 - hint 2: 想一下長方形重疊有哪幾種情況 - hint 3: 反過來想想兩個長方形不重疊的話，會有什麼樣的特性 - hint 4: 由於長方形的四個邊都是平行或垂直X Y軸，不重疊的話一定可以用一條平行或垂直X Y軸的線切開。 --- ### Hint - Leetcode 1733 : - hint 1: 先把圖上不重要的資訊刪掉 ---- ### Hint - Leetcode 1733 : - hint 1: 先把圖上不重要的資訊刪掉 - hint 2: 題目要求是只能選一種語言教，不要想一次就把這個語言選出來 ---- ### Hint - Leetcode 1733 : - hint 1: 先把圖上不重要的資訊刪掉 - hint 2: 題目要求是只能選一種語言教，不要想一次就把這個語言選出來 - hint 3: 考慮並嘗試所有的可能性後，最後挑最佳的那個出來。 ---- ### Hint - Leetcode 1733 : - ###### hint 1: 先把圖上不重要的資訊刪掉 - ###### hint 2: 題目要求是只能選一種語言教，不要想一次就把這個語言選出來 - ###### hint 3: 考慮並嘗試所有的可能性後，最後挑最佳的那個出來。 - ###### hint 4: 假設我們決定要教第i種語言，除了已經會的人之外，其他那些人要學 ---- ### Hint - Leetcode 1733 : - ###### hint 1: 先把圖上不重要的資訊刪掉 - ###### hint 2: 題目要求是只能選一種語言教，不要想一次就把這個語言選出來 - ###### hint 3: 考慮並嘗試所有的可能性後，最後挑最佳的那個出來。 - ###### hint 4: 假設我們決定要教第i種語言，除了已經會的人之外，其他那些人要學 - ###### hint 5: 考慮每個friendships，對於要教第i種語言，會分成哪幾種情況 --- ### 題解 ---- ### Leetcode 836 題目 - 給定兩個長方形，判斷他們有沒有重疊，且重疊的面積需要大於0 ---- ### Leetcode 836 題目 -  ---- ### Leetcode 836 題目 -  ---- ### Leetcode 836 - 可以發現如果長方形不重疊的話，把他們的XY軸座標分別拿出來，一定有一個軸的座標裡面存在一個值k，使得第一個長方形該座標都<=這個值，而另一個都>=。  ---- ### LeetCode 836 java code ```java //time complexity: O(1) //Extra space complexity: O(1) public boolean isRectangleOverlap(int[] rec1, int[] rec2) { // rec1 x2 <= rec2 x1 if (rec1[2] <= rec2[0]) { return false; } // rec2 x2 <= rec1 x1 if (rec2[2] <= rec1[0]) { return false; } // rec1 y2 <= rec2 y1 if (rec1[3] <= rec2[1]) { return false; } // rec2 y2 <= rec1 y1 if (rec2[3] <= rec1[1]) { return false; } return true; } ``` ---- ### Test case - 重疊的各種情況 -  ---- ### Test case - 不重疊的各種情況 -  ---- ### Leetcode 1733 題目 - 有一群人，每個人會一些語言，然後這些人中間會有友誼關係，也就是兩個人可能互相為朋友 - 兩個人要能溝通的話則必須存在一種語言他們兩個人都會 - 目標是要讓每一對朋友都能互相溝通。 - 而要做的事情是，選盡量少的人，並教他們***一種***語言，使得目標成立 ---- ### Leetcode 1733 解法 - 先把有朋友關係但他們已經會同一種語言的朋友關係移除，剩下的則是該對朋友不能互相溝通。 - 假設我們今天選定一個語言教，則每對朋友關係只會有兩種可能性 - 有一個人會這種語言 - 沒有人會這種語言 - 可以發現如果有個人不會這種語言，但他有一個朋友關係不能溝通，那他就必須得學 - 窮舉所有語言，判斷還有幾個人存在有一個朋友沒辦法溝通，而且他還不會這種語言 ---- ### Leetcode 1733 java code ```java //time complexity: O(n*(m+friendships.size())) //Extra space complexity: O(n) public int minimumTeachings(int n, int[][] languages, int[][] friendships) { boolean[] degree = new boolean[languages.length + 1]; for (int[] friendship : friendships) { int u = friendship[0]; int v = friendship[1]; boolean[] language = new boolean[n + 1]; for (int lang : languages[u - 1]) { language[lang] = true; } boolean ok = false; for (int lang : languages[v - 1]) { if (language[lang]) { ok = true; break; } } if (!ok) { degree[u] = true; degree[v] = true; } } int[] languageCnt = new int[n + 1]; int tot = 0; for (int i = 0; i < languages.length; i++) { if (degree[i + 1]) { for (int lang : languages[i]) { languageCnt[lang]++; } tot++; } } int maxCnt = 0; for (int cnt : languageCnt) { maxCnt = Math.max(maxCnt, cnt); } return tot - maxCnt; } ``` ---- ### Test case - 可以不用教任何語言 - 每個人都只會唯一一種語言 - 有人沒有朋友 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/1hYGGuEi4cs1n56bA -