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

[topic address]

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.

Returns the exclusive time of each function as an array, where the value of the i-th subscript represents the exclusive time of the function with identifier I.

Example 1:

Input: n = 2, logs = [0: start: "0", "1: start: 2", "1: end: 5", "0: end: 6"] output: [3, 4] interpretation: Function 0 starts execution at the beginning of timestamp 0, executes 2 unit times, and ends execution at the end of timestamp 1. Function 1 starts execution at the beginning of timestamp 2, executes 4 unit times, and ends execution at the end of timestamp 5. Function 0 resumes execution at the beginning of timestamp 6 for 1 unit of time. So function 0 takes 2 + 1 = 3 units of time, and function 1 takes 4 units of time.Copy the code

Example 2:

Input: n = 1, logs = [0: start: "0" and "0: start: 2", "0: end: 5", "0: start: 6", "0: end: 6", "0: end: 7"] output: [8] : Function 0 starts execution at the beginning of timestamp 0, executes 2 units of time, and recursively calls itself. Function 0 (recursive call) starts execution at the beginning of timestamp 2 and executes 4 units of time. Function 0 (the initial call) resumes execution and immediately calls itself again. Function 0 (the second recursive call) is executed at the beginning of timestamp 6 for 1 unit of time. Function 0 (initial call) is resumed at the start of timestamp 7 and takes 1 unit of time. So function 0 takes 2 + 4 + 1 + 1 = 8 units of time.Copy the code

Example 3:

Input: n = 2, logs = [0: start: "0" and "0: start: 2", "0: end: 5", "1: start: 6", "1: end: 6", "0: end: 7"] output: [7, 1] interpretation: Function 0 starts execution at the beginning of timestamp 0, executes 2 units of time, and recursively calls itself. Function 0 (recursive call) starts execution at the beginning of timestamp 2 and executes 4 units of time. Function 0 (the initial call) resumes execution and immediately calls function 1. Function 1 starts execution at the beginning of timestamp 6, executes 1 unit of time, and ends execution at the end of timestamp 6. Function 0 (initial call) resumes execution at the beginning of timestamp 7, executes 1 unit of time, and finishes execution at the end of timestamp 7. So function 0 takes 2 + 4 + 1 = 7 units of time, and function 1 takes 1 unit of time.Copy the code

Example 4:

Input: n = 2, logs = [0: start: "0" and "0: start: 2", "0: end: 5", "1: start: 7", "1: end: 7", "0: end: 8"] output: [8, 1]Copy the code

Example 5:

Logs = ["0:start:0","0:end:0"]Copy the code

Tip:

  • 1 <= n <= 100
  • 1 <= logs.length <= 500
  • 0 <= function_id < n
  • 0 <= timestamp <= 109
  • Two start events do not occur at the same timestamp
  • Two end events do not occur at the same timestamp
  • Each of these functions has a corresponding"start"The log"end"The log

For nesting and interrelation problems like this one, we can use stacks to maintain interrelation

The complication is that between the beginning and the end of a function, there may be calls to other functions or recursive calls of its own

We assume that each function runs without any other function running, so the function’s current run time is the end timestamp minus the start timestamp plus one

If there are other functions running in the function, then the running time of the function is the above time minus the running time of the other functions in the middle

The solution to this question is as follows:

  1. Create a length ofnAn array ofresMaintains the return value, a stack maintains the call stack of functions
  2. To iterate over the inputlogsIf the current log is a start log, push the start timestamp of the function onto the stack
  3. If the current log is an end log, the top of the stack records its start timestamp. Pop the top of the stack and add the running time of the function to the current running time (end timestamp – start timestamp +1).
  4. Add the start time stamp of other functions on the stack to the running time of this function to achieve the running time of corresponding function minus the running time of this function
  5. When the inputlogsWhen the traversal is complete,resArray records the exclusive time of each function, returnresCan be

The code is as follows:

Var exclusiveTime = function(n, logs) {const res = Array(n).fill(0), // stack = []; For (let I = 0; i<logs.length; i++){ let [ind,status,time] = logs[i].split(':'); ind *= 1; time *= 1; // If the log is started, If (status==='start') stack.push(time) else {// Const num = time-stack.pop()+1 res[ind] += num // HandleStack (num)}} return res; Function handleStack(num){for(let I =0; i<stack.length; i++){ stack[i]+=num; }}};Copy the code

This completes the exclusive time of the Leetcode-636 – function

If you have any questions or suggestions, please leave a comment!