python - space optimized - time count


  • 0
    S
    class Solution(object):
        def exclusiveTime(self, n, logs):
            """
            :type n: int
            :type logs: List[str]
            :rtype: List[int]
            """
            if not (n and logs):
                return []
            
            stack = []
            fids = {}
            # stack entry : (fid, (re-)start time, refcount)
            for entry in logs:
                
                # get the log entry
                curr_fid, curr_action, curr_time = entry.split(":")
                curr_fid, curr_time = int(curr_fid), int(curr_time)
                if curr_fid not in fids:
                    fids[curr_fid] = 0
                
                # get top of stack
                if stack:
                    top = stack[-1]
                    top_fid, top_time, top_count = top
                else:
                    stack.append([curr_fid, curr_time, 1])
                    continue
                    
                if curr_action == "start":
                    
                    # for recursion
                    if curr_fid == top_fid:
                        top[2] += 1
                        top[1] = curr_time
                    else:
                        stack.append([curr_fid, curr_time,1])  
                        
                    fids[top_fid] = fids.get(top_fid, 0) + curr_time - top_time
                    
                else:
                    top[2] -= 1
                    fids[curr_fid] = fids.get(curr_fid, 0) + curr_time - top_time + 1
                    
                    # for recursion
                    if top[2] == 0:
                        stack.pop()
                    
                    if stack:
                        top = stack[-1]
                        top_id, top_time, top_count = top
                    
                    top[1] = curr_time + 1
            
            return [fids[k] for k in sorted(fids.keys())]
                        
                        
                        
                        
                        
                        
                        
                        
    

Log in to reply
 

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