“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topic describes

A single-threaded CPU is running a program with n functions. Each function has a unique identifier between 0 and n-1.

Function calls are stored on a call stack: When a function call is started, its identifier is pushed onto the stack. When a function call ends, its identifier pops off the stack. The function whose identifier is at the top of the stack is the currently executing function. Each time a function starts or ends, a log is logged, including the function identifier, whether it started or ended, and the corresponding timestamp.

Give you a list of log logs, which logs [I] said article I log message, the message is a “{function_id}, {” start” | “end”}, {timestamp} “to format strings. For example, “0:start:3” means that the function call with identifier 0 starts execution at the beginning of timestamp 3; “1:end:2” means that the function call with identifier 1 ends execution at the end of timestamp 2. Note that functions can be called multiple times, and there may be recursive calls.

The exclusive time of a function is defined as the sum of the execution time of the function in all calls to the program. The time spent calling other functions does not count the exclusive time of the function. For example, if a function is called twice, with one call executing 2 units of time and the other one executing 1 units of time, the function’s exclusive time is 2 + 1 = 3.

LeetCode: leetcode-cn.com/problems/ex…

Their thinking

  1. When adjacent logs are started, the execution time of previous logs is calculated and the previous log time is updated
Previous log execution time = Current log time - Previous log timeCopy the code
  1. To end a log, the system calculates the execution time of the current function and sets the current log time + 1 to the previous log time. In this way, if there are adjacent end logs, the previous end log time is the start time
Function execution time = current log time - Previous log time + 1 Previous log time = previous log time + 1Copy the code

If the stack is not empty, the top of the stack is also the start of the log, which updates the execution time of the previous log. Then the stack starts logging function ID. When the end log is encountered, the end log and the top of the stack log are the same function, and the stack is removed after calculating the function call.

For example

The case of a function call

[0:start:0, 0:end:3] 0 exclusive time: end-start = 3-0 + 1 = 4Copy the code

Multiple function calls

[0:start:0, 1:start:2, 2:start:4, 2:end:5, 1:end:7, 0:end:9] 0 exclusive time: (2-0) + (9-7) = 4 (4-2) + (7-5) = 4 2 exclusive time :(5-4) + 1 = 2Copy the code

Notice that we’re counting from zero.

Code implementation

var exclusiveTime = function(n, logs) { const res = new Array(n).fill(0) const stack = [] let prevTime = 0 logs.forEach(log => { const arr = Log.split (':') const currTime = Number(arr[2]) const offset = currTime - prevTime // Calculates the offset of the current and last logs prevTime = currTime If (arr[1] === 'start') {if (stack.length > 0) {// If (arr[1] === 'start') { Res [stack[stack.length-1]] += offset} stack.push(Number(arr[0]))} else { Res [Number(arr[0])] += offset + 1 PrevTime++ stack.pop()}}) return res}Copy the code

If there are mistakes welcome to point out, welcome to discuss together!