Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/03 15:42)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串335/719 (看更多)

https://leetcode.com/problems/time-needed-to-inform-all-employees/description/ 1376. Time Needed to Inform All Employees 給你數字 n 表示員工數量，headID 表示老闆，manager[] 表示每個人他的上司是誰， informTime[] 表示通知下屬要花多久(沒下屬的話是0)，今天老闆有話要通知全公司，他會通知地位最高的主管並讓主管交接給他的下級主管，題目保證所有員工都會被通知，請問全公司都收到消息最快要花多久? Example 1: Input: n = 1, headID = 0, manager = [-1], informTime = [0] Output: 0 Explanation: The head of the company is the only employee in the company. Example 2: Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] https://assets.leetcode.com/uploads/2020/02/27/graph.png

Output: 1 Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all. The tree structure of the employees in the company is shown. 思路： 1.所有員工都要被通知到，可以把關係轉變成一顆樹，老闆當作是子節點並記錄每個人的下屬有哪些。 2.對所有下屬做DFS，並比較所有底層員工收到消息時花了多久，取最長的時間。 Java Code： ---------------------------------------------------- class Solution { private ArrayList<Integer>[] subordinates; public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { subordinates = new ArrayList[n]; for (int i = 0; i < n; i++) { subordinates[i] = new ArrayList<>(); } for (int i = 0; i < n; i++){ if (manager[i] == -1) continue; subordinates[manager[i]].add(i); } return dfs(headID, informTime); } public int dfs(int id, int[] informTime) { if (subordinates[id].size() == 0) { return 0; } int max = 0; for (int subordinateId : subordinates[id]) { max = Math.max(max, dfs(subordinateId, informTime)); } return max + informTime[id]; } } ---------------------------------------------------- -- https://i.imgur.com/YPBHGGE.jpg