###### Agenda: ###### 11/01 22:00(UTC+8) 11/01 07:00(UTC-7) ###### 公布這次live session題目 ###### 11/01 22:30(UTC+8) 11/01 07:30(UTC-7) ###### 開始逐步給hint ###### 11/01 23:00(UTC+8) 11/01 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 1002 #### https://leetcode.com/problems/find-common-characters/description/ #### Leetcode 1042 #### https://leetcode.com/problems/flower-planting-with-no-adjacent/description/ --- ### Hint - Leetcode 1002 : - hint 1: 順序不影響答案 ---- ### Hint - Leetcode 1002 : - hint 1: 順序不影響答案 - hint 2: 先思考單一一種字母 ---- ### Hint - Leetcode 1002 : - hint 1: 順序不影響答案 - hint 2: 先思考單一一種字母 - hint 3: 當一個字母出現多次的時候需要找出最小出現的次數 ---- ### Hint - Leetcode 1002 : - hint 1: 順序不影響答案 - hint 2: 先思考單一一種字母 - hint 3: 當一個字母出現多次的時候需要找出最小出現的次數 - hint 4: 這題可以做到 $O(\sum_{word\in words} |word|)，也就是所有word長度的總和 --- ### Hint - Leetcode 1042 : - hint 1: 考慮換一個方式存圖 ---- ### Hint - Leetcode 1042 : - hint 1: 考慮換一個方式存圖 - hint 2: 當要種花在一個花園還時，要確認周圍已經種過花的花園，不要跟他們衝突 ---- ### Hint - Leetcode 1042 : - hint 1: 考慮換一個方式存圖 - hint 2: 當要種花在一個花園還時，要確認周圍已經種過花的花園，不要跟他們衝突 - hint 3: 一個花園最多只有三個鄰居，但有四種花可以選 ---- ### Hint - Leetcode 1042 : - hint 1: 考慮換一個方式存圖 - hint 2: 當要種花在一個花園還時，要確認周圍已經種過花的花園，不要跟他們衝突 - hint 3: 一個花園最多只有三個鄰居，但有四種花可以選 - hint 4: 當一個點種過花後就不要再去更動 --- ### 題解 ---- ### Leetcode 1002 題目 - 給一些字串，找出他們共同出現的字母，一個字母可能出現多次。 ---- ### Leetcode 1002 - 對於每一個 word ，我們建立出他的 counting sort array ，也就是當a出現兩次，我們就在array[0]上設定為2 - 將這些 couting sort array 蒐集起來，對每一個位子找出所有counting sort array中最小的 - $counting1 = \{1,2,3...\}$ - $counting2 = \{3,2,1...\}$ - $ans = \{1,2,1...\}$ ---- ### LeetCode 1002 java code ```java public List<String> commonChars(String[] words) { int ans[] = new int[26]; for (int i = 0; i < 26; i++) { ans[i] = Integer.MAX_VALUE; } for (String word : words) { int cnt[] = new int[26]; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); cnt[c - 'a']++; } for (int i = 0; i < 26; i++) { ans[i] = Math.min(ans[i], cnt[i]); } } List<String> res = new ArrayList<String>(); for (int i = 0; i < 26; i++) { for (int j = 0; j < ans[i]; j++) { res.add(String.valueOf((char) (i + 'a'))); } } return res; } ``` ---- ### Test case - 一個字串 - 多個字串但答案都從同一個來 - "abc" "aabbcc" "aaabbbccc" - 多個字串但答案從不同地方來 - "aaabbc" "abbbcc" "aabccc" ---- ### Leetcode 1042 題目 - 給一些花園，某些花園互為鄰居，一個花園最多只會有 $3$ 個鄰居，現在有四種花，請給每個花園決定一種花，使得任兩個互為鄰居的花園的花是不同的。 ---- ### Leetcode 1042 題目 - 轉換題目後變成，給一張圖，每一個點最多有 $3$ 條邊，有四種顏色要將點塗色，且塗完後，每條邊的兩個點為不同顏色 ---- ### Leetcode 1042 題目 -  - [1,2,1,3] ---- ### Leetcode 1042 解法 - 由於每個點最多只連接到三個點，就算他那三個點都是不一樣的顏色，該點也會剩餘一種顏色可以填。 - 想辦法走完整張圖，在填每個點的顏色時，注意不要跟他已經填過顏色的鄰居衝突就可以了。 ---- ### Leetcode 1042 dfs part ```java void dfs(int u, int[] ans, List<Integer>[] edge) { int[] vis = new int[5]; for (int v : edge[u]) { vis[ans[v]] = 1; } for (int i = 1; i <= 4; i++) { if (vis[i] == 0) { ans[u] = i; break; } } for (int v : edge[u]) { if (ans[v] == 0) { dfs(v, ans, edge); } } } ``` ---- ### Leetcode 1042 main part ```java public int[] gardenNoAdj(int n, int[][] paths) { List<Integer>[] edge = new ArrayList[n]; for (int i = 0; i < n; i++) { edge[i] = new ArrayList<Integer>(); } for (int[] path : paths) { edge[path[0] - 1].add(path[1] - 1); edge[path[1] - 1].add(path[0] - 1); } int[] ans = new int[n]; for (int i = 0; i < n; i++) { if (ans[i] == 0) { dfs(i, ans, edge); } } return ans; } ``` ---- ### Test case - 圖沒有連通 - 大小為四的完全圖 -  - 有點沒有鄰居 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/7oxfBE4LCbuKaWkx5 -