“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
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.
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.
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.
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]
Example 5:
Logs = [“0:start:0″,”0:end:0”]
My first impression is that this problem is similar to valid parentheses, which also require the use of a stack, start on the stack, end off the stack. Valid parentheses only need to determine whether the stack is empty at the end. This problem needs to determine how long each type of start to end stays in the stack.
We want to push the corresponding ID if we don’t encounter a start. When we encounter an end, we push the corresponding ID off the stack. Only functions at the top of the stack are recorded as being executed.
The previous function does not continue execution until the top function has been removed from the stack.
We go through all the logs. For the i-th log, if it contains start, then the top of the stack function runs from its timestamp time[I], that is, prev = time[I]; If it contains end, then the top of the stack function runs from the next time after its timestamp time[I], that is, prev = time[I] + 1. For the I + 1 log, if it contains start, then a new function is called at timestamp time[I + 1], so the original top-stack function has an exclusive time of time[I + 1] -prev; If it contains end, then at timestamp time[I + 1], the original top of the stack function is finished, and the exclusive time is time[I + 1] -prev + 1. After that, we update the prev and iterate through the I + 2 log. At the end of the walk, we can get the exclusive times of all the functions.
Var exclusiveTime = function (n, logs) {let res = new Array(n).fill(0); // let stack = []; // let prev = 0; For (const item of logs) {let temp = item.split(":") // log ID let ID = temp[0]; // Log status let status = temp[1]; // Start/end time let time = temp[2]; If (status == "start") {if (stack.length) {if (stack.length) {if (stack.length) { Res [stack[stack.length-1]] += time-prev} // Record the time prev = time. Stack. Push (id)} else {// Status = end, indicating the end of the function res[id] += time-prev + 1; prev = parseInt(time) + 1; stack.pop() } } console.log(res); }Copy the codeComplexity analysis
- Time complexity: O(N). We need to iterate over all the logs, because there are N functions, so the number of logs is 2N.
- Space complexity: O(N) is the space occupied by the stack.