[Medium] 636. Exclusive Time of

Description

On a single threaded CPU, we execute some functions. Each function has a unique id between 0 and N-1.

We store logs in timestamp order that describe when a function is entered or exited.

Each log is a string with this format: "{function_id}:{"start" | "end"}:{timestamp}". For example, "0:start:3" means the function with id 0 started at the beginning of timestamp 3. "1:end:2" means the function with id 1 ended at the end of timestamp 2.

A function's exclusive time is the number of units of time spent in this function. Note that this does not include any recursive calls to child functions.

The CPU is single threaded which means that only one function is being executed at a given time unit.

Return the exclusive time of each function, sorted by their function id.

Solution

1.Stack 更节省时间的做法

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stack = []
        res=[0]*n
        last_start = None
        for log in logs:
            nid,op,t = log.split(':')
            nid,t=int(nid),int(t)
            if op =="start":
                if stack:
                    res[stack[-1]]+= t - last_start
                stack.append(nid)
            else:
                t +=1
                stack.pop()
                interval = t - last_start 
                res[nid] += interval
            last_start = t
        return res

使用stack解决

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stack = []
        res={}
        for log in logs:
            nid,op,t = log.split(':')
            nid,t=int(nid),int(t)
            if op =="start":
                stack.append([nid,t])
            else:
                _,t_start = stack.pop()
                t_start=int(t_start)
                interval = t-t_start +1
                if nid in res:  
                    res[nid] += interval
                else:
                    res[nid] = interval
                if stack:
                    if stack[-1][0] not in res:
                        res[stack[-1][0]] =- interval
                    else:
                        res[stack[-1][0]] -= interval
              
        return [res[k] for k in sorted(res.keys())]