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

Leetcode 636. Exclusive time of functions

The title

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”]

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

Answer key

Ask questions

  • What data structure is used to solve the problem?

Analysis of the

  • Define an arraylet res = new Array(n).fill(0)Used to record the time spent on each task
  • definego = 0Represents the current task to be executed and passeswhileTraversal executes each subtasknextmethods
  • The amount of time each subtask takes to passnextMethod to calculate
  • definedureIndicates the subtask duration
  • throughsplit(":")Divide the current task into 3 parts. This is the start task
  • When the mission is not the last mission nor the end mission, passwhileCalculate the total time spentdure
  • When the next task is finishedconst end = logs[++go].split(":")The tasksplit(":")
  • Here we calculate the net execution time of the functionlet sum = Number(end[2]) - Number(start[2]) + 1 - dure
  • Store the result in an arrayresAnd returns the time spentsum + dure
  • Repeat the preceding steps until all tasks are complete

Code implementation

/** * @param {number} n * @param {string[]} logs * @return {number[]} */ var exclusiveTime = function(n, logs) { let res = new Array(n).fill(0) let go = 0 function next(){ let dure = 0 const start = logs[go].split(":") while(go < logs.length -1 && logs[go + 1].indexOf('s') ! == -1){ go++ dure = dure + next() } const end = logs[++go].split(":") let sum = Number(end[2]) - Number(start[2]) + 1 - dure res[Number(start[0])] = res[Number(start[0])] + sum return sum + dure } while(go < logs.length){ next() go++ } return res };Copy the code