###### Agenda: ###### 12/13 22:00(UTC+8) 12/13 07:00(UTC-7) ###### 公布這次live session題目 ###### 12/13 22:30(UTC+8) 12/13 07:30(UTC-7) ###### 開始逐步給hint ###### 12/13 23:00(UTC+8) 12/13 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 1052 #### https://leetcode.com/problems/grumpy-bookstore-owner/description/ #### Leetcode 802 #### https://leetcode.com/problems/find-eventual-safe-states/description/ --- ### Hint - Leetcode 1052 : - hint 1: 當決定好，要在哪一段時間使用 secret technical 後，那段時間的 grumpy 就不重要了 ---- ### Hint - Leetcode 1052 : - hint 1: 當決定好，要在哪一段時間使用 secret technical 後，那段時間的 grumpy 就不重要了 - hint 2: 會需要計算兩種區間和，一種是不管 grumpy 的，一種是要管 grumpy 的 ---- ### Hint - Leetcode 1052 : - hint 1: 當決定好，要在哪一段時間使用 secret technical 後，那段時間的 grumpy 就不重要了 - hint 2: 會需要計算兩種區間和，一種是不管 grumpy 的，一種是要管 grumpy 的 - hint 3: 可能不能馬上決定要在哪一段時間使用 secret technical，那就所有可能嘗試候選最好的 ---- ### Hint - Leetcode 1052 : - ###### hint 1: 當決定好，要在哪一段時間使用 secret technical 後，那段時間的 grumpy 就不重要了 - ###### hint 2: 會需要計算兩種區間和，一種是不管 grumpy 的，一種是要管 grumpy 的 - ###### hint 3: 可能不能馬上決定要在哪一段時間使用 secret technical，那就所有可能嘗試候選最好的 - ###### hint 4: 假設要在 l,r 中間使用 secret technical，那總和就會是 sum1[l..r] + sum2[0..l-1] + sum2[r+1,n-1]，其中 sum1 是不考慮 grumpy 的，而 sum2 要考慮 --- ### Hint - Leetcode 802 : - hint 1: terminal 的點就是 safety node ---- ### Hint - Leetcode 802 : - hint 1: terminal 的點就是 safety node - hint 2: 一個點如果他所有指出去的邊都是 safety node，那他就是 safety node ---- ### Hint - Leetcode 802 : - hint 1: terminal 的點就是 safety node - hint 2: 一個點如果他所有指出去的邊都是 safety node，那他就是 safety node - hint 3: 如果判斷出一個點是 safety node，那可以向所有指向他的人，更新他們指出去的點 safety node又多一個。 ---- ### Hint - Leetcode 802 : - ###### hint 1: terminal 的點就是 safety node - ###### hint 2: 一個點如果他所有指出去的邊都是 safety node，那他就是 safety node - ###### hint 3: 如果判斷出一個點是 safety node，那可以向所有指向他的人，更新他們指出去的點 safety node又多一個。 - ###### hint 4: 根據 hint 3，若把邊反過來可能會比較好做 ---- ### Hint - Leetcode 802 : - ###### hint 1: terminal 的點就是 safety node - ###### hint 2: 一個點如果他所有指出去的邊都是 safety node，那他就是 safety node - ###### hint 3: 如果判斷出一個點是 safety node，那可以向所有指向他的人，更新他們指出去的點 safety node又多一個。 - ###### hint 4: 根據 hint 3，若把邊反過來可能會比較好做 - ###### hint 5: 想像把已經是 safety node 的點拔掉 --- ### 題解 ---- ### Leetcode 1052 題目 - 有一家書店會開 $n$ 分鐘，第 $i$ 分鐘會有 customer[$i$]個人進來 - 老闆在某些分鐘會脾氣暴躁，這個時間進來的客人會對書店不滿意，其他時候進來的客人會對書店滿意 - 老闆有一個秘密科技可以讓他保證在接下來連續 $minutes$ 分鐘脾氣不暴躁 - 問最多可以讓多少客人滿意 ---- ### Leetcode 1052 題目 - customer = [1,2,3,4] - grumpy = [0,1,0,1] ---- ### Leetcode 1052 - 我們可以用一個新的 array 去紀錄不使用科技的情況下，每分鐘滿意的客人 satisfiedCustomer[i] = costomer[i] * ( 1 - grumpy[i]) - 當我們使用科技在 [l..r] 的區間時，滿意的客人數量為 satisfiedCustomer[0...l-1] + customer[l...r] + satisfiedCustomer[r+1...n-1] - 只有n種可能使用科技的方法，剩下的可以用 prefix sum 求解直到找到最好的一個 ---- ### LeetCode 1052 java code ```java //time complexity: O(n) //Extra space complexity: O(n) public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int n = customers.length; int[] satisfiedCustomer = new int[n + 1]; int[] originCustomer = new int[n + 1]; for (int i = 0; i < n; i++) { satisfiedCustomer[i + 1] = satisfiedCustomer[i] + customers[i] * (1 - grumpy[i]); originCustomer[i + 1] = originCustomer[i] + customers[i]; } int ans = 0; for (int i = 0; i + minutes <= n; i++) { int cur = satisfiedCustomer[i] + (originCustomer[i + minutes] - originCustomer[i]) + (satisfiedCustomer[n] - satisfiedCustomer[i + minutes]); ans = Math.max(ans, cur); } return ans; } ``` ---- ### Test case - grumpy 全部都 1 - grumpy 全部都 0 - normal case - customer = [1,2,3,4] - grumpy = [0,1,0,1] - minutes = 2 ---- ### Leetcode 802 題目 - 給一張有向圖，定義一個點當它沒有 out edge 時為 terminal。 - 而定義一個點，當沿著他的邊一直走，沒辦法無限走下去時，為 safety node。 ---- ### Leetcode 802 題目  ---- ### Leetcode 802 解法 - 當一個點為 terminal 時，他為 safety node. - 當我們把一個點判斷為 safety node 後可以把它從圖上拔掉，而新的圖若存在一個點為 terminal 時，他也會為 safety node。 - 每次都把 out degree 為 0 的點拔掉，當拔掉一個點的時候，把所有指向他的點的 out degree - 1。 - 做完上述操作後，有點的 out degree 變成 0 時，也把它拔掉 - 可以用 queue 去儲存即將要被拔掉的點並作上述處理 ---- ### Leetcode 802 java code ```java //time complexity: O(n+m) //Extra space complexity: O(n) public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; List<List<Integer>> rgraph = new ArrayList<>(); for (int i = 0; i < n; i++) { rgraph.add(new ArrayList<>()); } int[] degree = new int[n]; for (int i = 0; i < n; i++) { degree[i] = graph[i].length; for (int v : graph[i]) { rgraph.get(v).add(i); } } Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) { if (degree[i] == 0) { q.offer(i); } } List<Integer> ans = new ArrayList<>(); while (!q.isEmpty()) { int x = q.poll(); ans.add(x); for (int prev : rgraph.get(x)) { if (--degree[prev] == 0) { q.offer(prev); } } } Collections.sort(ans); return ans; } ``` ---- ### Test case - 所有點都是 safety node - 所有點都不是 safety node - 自己走到自己 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/fnESLNH69v2vzBUt7 -