#ЛитКод
Задача:
636. Exclusive Time of FunctionsНа однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.
Пример:Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]
👨💻
Алгоритм:1⃣
Парсинг логовПройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.
2⃣
Использование стекаИспользуйте стек для отслеживания текущих вызовов функций. Если лог содержит start, добавьте функцию в стек и начните отсчет времени. Если лог содержит end, снимите функцию со стека и обновите эксклюзивное время.
3⃣
Обновление времени выполненияКогда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.
😎
Решение:
var exclusiveTime = function(n, logs) {
let stack = [];
let times = new Array(n).fill(0);
let prevTime = 0;
for (let log of logs) {
let [fid, type, time] = log.split(':');
fid = parseInt(fid);
time = parseInt(time);
if (type === 'start') {
if (stack.length) {
times[stack[stack.length - 1]] += time - prevTime;
}
stack.push(fid);
prevTime = time;
} else {
times[stack.pop()] += time - prevTime + 1;
prevTime = time + 1;
}
}
return times;
};👉
Новости 👉
Платформа
