“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”
Topic:
636. The exclusive time of a function
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 codeExample 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 codeExample 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 codeExample 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 codeExample 5:
Logs = ["0:start:0","0:end:0"]Copy the code
Tip:
1 <= n <= 1001 <= logs.length <= 5000 <= function_id < n0 <= 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
Ideas:
- According to create a length of
nAn array ofresultIs used to record the occurrence time of each function. The initial value is 0. - New stack variable
stackEvery time I meetstartThe node,pushTo the last element of the stack; - encounter
endIs taken from the stack and added to the resultResult [current element], the result is equal toendTime minusstartThe time of + 1 is called the variablelet temp = Number(time) - Number(last.time) + 1; - If an element is removed from the stack and the remaining elements are found, it is a nested function, and the start time of the remaining elements is added
temp, because this period of time has already been occupied, we do not need to calculate the difference.
Implementation:
/ * * *@param {number} n
* @param {string[]} logs
* @return {number[]}* /
var exclusiveTime = function(n, logs) {
let stack = [];
const len = logs.length;
// Create an array of length N to record the occurrence time of each function
let result = new Array(n).fill(0);
for (let i = 0; i < len; i++) {
let [ target, flag, time ] = logs[i].split(":");
// Start is stored, end is retrieved
if (flag === "start") {
stack.push({ target, time });
} else {
// Record the time difference
const last = stack.pop();
let temp = Number(time) - Number(last.time) + 1;
// Tell the first person that this period of time is occupied, do not roll
stack.forEach(item= > {
item.time = Number(item.time) + temp;
});
// Record the exclusive time of the time pointresult[last.target] += temp; }}return result;
};
Copy the codeIf you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.