###### Agenda: ###### 11/22 22:00(UTC+8) 11/22 07:00(UTC-7) ###### 公布這次live session題目 ###### 11/22 22:30(UTC+8) 11/22 07:30(UTC-7) ###### 開始逐步給hint ###### 11/22 23:00(UTC+8) 11/22 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 2095 #### https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/ #### Leetcode 2192 #### https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/ --- ### Hint - Leetcode 2095 : - hint 1: 可以走過整個linked list不只一次 ---- ### Hint - Leetcode 2095 : - hint 1: 可以走過整個linked list不只一次 - hint 2: 考慮先計算出整個link list有幾個節點 ---- ### Hint - Leetcode 2095 : - hint 1: 可以走過整個linked list不只一次 - hint 2: 考慮先計算出整個link list有幾個節點 - hint 3: 當多設定一個變數可以計算我們已經走過幾個節點 --- ### Hint - Leetcode 2192 : - hint 1: DAG的意思是從任何一個點往下走後不會走回來自己 ---- ### Hint - Leetcode 2192 : - hint 1: DAG的意思是從任何一個點往下走後不會走回來自己 - hint 2: 若A可以走到B，則A是B的ancestor ---- ### Hint - Leetcode 2192 : - hint 1: DAG的意思是從任何一個點往下走後不會走回來自己 - hint 2: 若A可以走到B，則A是B的ancestor - hint 3: 需要注意若之前已經從A走到B過了就不用再走一次了 ---- ### Hint - Leetcode 2192 : - hint 1: DAG的意思是從任何一個點往下走後不會走回來自己 - hint 2: 若A可以走到B，則A是B的ancestor - hint 3: 需要注意若之前已經從A走到B過了就不用再走一次了 - hint 4: 每一個點做一次類似的事情 --- ### 題解 ---- ### Leetcode 2095 題目 - 給一個linked list，假設長度為 n ，假設 head 是第 0 個 node，請移除第 $\lfloor \frac n 2 \rfloor$個node ---- ### Leetcode 2095 題目 - 1->2->3->4 - 移除3，因為他在第2個位子，n/2 = 2 - 1->2->3->4->5 - 移除3，因為他在第2個位子，n/2 = 2.5 ---- ### Leetcode 2095 - 走過兩次 linked list - 第一次 - 數這個 linked list 有幾個節點 - 第二次 - 依序數到第 $\lfloor \frac n 2 \rfloor$ 個node 後把他移除 - 移除一個node - node -> next = node->next->next - 注意一個 n=1的 case ---- ### LeetCode 2095 java code ```java //time complexity: O(n) //Extra space complexity: O(1) public ListNode deleteMiddle(ListNode head) { int n = 0; ListNode now = head; while(now != null){ n++; now = now.next; } if(n==1) { return null; } int cnt = 0; now = head; while(now != null){ cnt++; if(cnt == n/2){ now.next = now.next.next; break; } now = now.next; } return head; } ``` ---- ### Test case - n = 1 - n = 2 - 因為被移掉的後一位是null - n 是奇數 - n 是偶數 ---- ### Leetcode 2192 題目 - 給定一個 DAG 對於每個節點找出所有的點可以走到這個點。 - DAG 的意思為圖上不存在 cycle，也就是任何一個節點走出去後走不回自己。 ---- ### Leetcode 2192 題目  ---- ### Leetcode 2192 解法 - 剛開始先把每個點的List開出來，接下來每個點開始往下DFS。 - 每個被DFS過的點都把起始點放進去，因為起始點即為他的ancestor。 - 開一個visit array去紀錄每個點在這一個倫次是否被走過，讓對於一個起始點做DFS時，所有點只會被走到最多一次。 ---- ### Leetcode 2192 dfs part ```java void dfs(int x, int s, List<List<Integer>> ans) { if (x != s) { ans.get(x).add(s); } vis[x] = 1; for (int nxt : edge.get(x)) { if (vis[nxt] == 0) { dfs(nxt, s, ans); } } } ``` ---- ### Leetcode 2192 main part ```java //time complexity: O((n+m)*n) //Extra space complexity: O(n^2+m) public List<List<Integer>> getAncestors(int n, int[][] edges) { List<List<Integer>> ans = new ArrayList<>(); edge = new ArrayList<>(); vis = new int[n]; for (int i = 0; i < n; i++) { ans.add(new ArrayList<>()); edge.add(new ArrayList<>()); } for (int[] e : edges) { edge.get(e[0]).add(e[1]); } for (int i = 0; i < n; i++) { Arrays.fill(vis, 0); dfs(i, i, ans); } return ans; } ``` ---- ### Test case - 圖不連通 - 存在單一一個點 - 一條鍊 - 星狀圖 - 編號打亂 - 4->5->6->0->1->2->3 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/whG5RRKEgUm4rrV9A -