Java solution, easy to understand by defining a FunctionCall class


  • 0
    A
    public class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        // algorithm 2017/07/22: use a stack to track calls. 
        // For each start time, push an element into the stack; for each end time, pop
        // Each time we pop, we make sure the execution time is reduced from its caller
        int[] results = new int[n];
        if (null == logs || 0 == logs.size()) {
            return results;
        }
        
        Stack<FunctionCall> stack = new Stack<>();
        for (String log : logs) {
            String[] components = log.split(":");
            assert 3 == components.length;
            int funcId    = Integer.parseInt(components[0]);
            int timeStamp = Integer.parseInt(components[2]);
            if ("start".equals(components[1])) {
                // we are making a call
                stack.push(new FunctionCall(funcId, timeStamp));
            } else {
                // we are returning from a call
                assert !stack.isEmpty();
                FunctionCall functionCall = stack.pop();
                assert funcId == functionCall.funcId;
                
                int totalTime = timeStamp + 1 - functionCall.startTime;
                // exclusiveTime of this function
                int exclusiveTime = totalTime - functionCall.offsetFromCalls;
                results[funcId] += exclusiveTime;
                
                // the totalTime of its caller function
                if (!stack.isEmpty()) {
                    stack.peek().offsetFromCalls += totalTime;
                }
            }
        }
        
        return results;
    }
    
    class FunctionCall {
        public FunctionCall(int funcId, int startTime) {
            this.funcId    = funcId;
            this.startTime = startTime;
        }
        int funcId;
        int startTime;
        int offsetFromCalls;
    }
    

    }


Log in to reply
 

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