“This is the 16th day of my participation in the December Gwen Challenge. See details: The Last Gwen Challenge 2021”

636. The exclusive time of a function

Power button link

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: s = "3/2" Output: 1Copy the code

Example 3:

Input: s = "3+ 5/2" Output: 5Copy 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 function has an “end” log corresponding to the “start” log

The stack

Train of thought

For this problem we use the idea of a stack to record the time of each function

  • The elapsed time of a function = the elapsed time of a function from the end of the function to the beginning of the function.

Here we need several variables to explain what they mean

  • The stack array is used to hold the ids of functions that have already been run
  • The res array subscript is the corresponding function ID and the value is the running time of the corresponding function
  • Pre Indicates the time of the last log

Then start iterating through the log

If the current log state is ‘start’ :

  • Stack is empty, which means that this is the first function, and I’m going to push it directly onto the stack, and the pre time is fn_time
  • Stack is not empty, which means running in the previous (top of stack) function, then the running time of the previous function + the current point in time – the last point in time, namely fn_time – pre

If the current log state is ‘end’:

  • Fn_time – pre +1 = fn_time – pre +1 = fn_time – pre +1 = fn_time – pre +1 = fn_id

Finally, we return our res result function

var exclusiveTime = function (n, logs) {
    // Store the id of the running function
    var stack = []
    // The subscript is function id and the value is the running time of the corresponding function
    var res = new Array(n).fill(0)
    // The time of the last log
    var pre = 0
    
    for (var i = 0; i < logs.length; i++) {
        var item = logs[i].split(':')
        / / log id
        var fn_id = item[0]
        // Log status
        var fn_state = item[1]
        // Log time point
        var fn_time = item[2]
    
        if (fn_state === 'start') {
            if (stack.length) {
                res[stack[stack.length - 1]] += (fn_time - pre)
            }
            pre = fn_time
            stack.push(fn_id)

        }
        if (fn_state === 'end') {
            res[fn_id] += (fn_time - pre + 1)
            pre = fn_time*1 + 1
            stack.pop()
        }
    }
    return res
};
Copy the code