Java, O(N), easy to understand DFS solution


  • 0
    public class Solution {
        int idx;   //current processing index
        public int[] exclusiveTime(int n, List<String> logs) {
            idx = 0;
            int[] res = new int[n];
            while (idx < logs.size()) {
                dfs (logs, res);
            }
            return res;
        }
        
        //return the total time used in the region start from current idx
        private int dfs(List<String> logs, int[] memo) {
            String[] log = logs.get(idx).split(":");
            int fId = Integer.valueOf(log[0]), start=Integer.valueOf(log[2]); //function id, start time 
            int childrenTime = 0; //time used by its children
            idx++;
            log = logs.get(idx).split(":");
            while (Integer.valueOf(log[0]) != fId || !log[1].equals("end")) {
                childrenTime += dfs(logs, memo);
                log = logs.get(idx).split(":");
            }
            int usedTime = Integer.valueOf(log[2])+1-start;
            memo[fId] += usedTime-childrenTime; //exclude the time used by children
            idx++;
            return usedTime;   
        }                        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.