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]
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
public class Solution {
public int[] ExclusiveTime(int n, IList<string> logs) {
Stack<int> stack = new Stack<int>();
int[] times = new int[n];
int prevTime = 0;
foreach (string log in logs) {
string[] parts = log.Split(new char[] { ':' });
int fid = int.Parse(parts[0]);
string type = parts[1];
int time = int.Parse(parts[2]);
if (type == "start") {
if (stack.Count > 0) {
times[stack.Peek()] += time - prevTime;
}
stack.Push(fid);
prevTime = time;
} else {
times[stack.Pop()] += time - prevTime + 1;
prevTime = time + 1;
}
}
return times;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int>& ExclusiveTime(int n, vector<string> logs) {
stack<int> stack = new stack<int>();
vector<int>& times = new int[n];
int prevTime = 0;
foreach (string log in logs) {
vector<string> parts = log.Split(new char[] { ':' });
int fid = int.Parse(parts[0]);
string type = parts[1];
int time = int.Parse(parts[2]);
if (type == "start") {
if (stack.size() > 0) {
times[stack.Peek()] += time - prevTime;
}
stack.push(fid);
prevTime = time;
} else {
times[stack.pop()] += time - prevTime + 1;
prevTime = time + 1;
}
}
return times;
}
}Java решение
сопоставлено/оригиналimport java.util.*;
public class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
Stack<Integer> stack = new Stack<>();
int[] times = new int[n];
int prevTime = 0;
for (String log : logs) {
String[] parts = log.split(":");
int fid = Integer.parseInt(parts[0]);
String type = parts[1];
int time = Integer.parseInt(parts[2]);
if (type.equals("start")) {
if (!stack.isEmpty()) {
times[stack.peek()] += time - prevTime;
}
stack.push(fid);
prevTime = time;
} else {
times[stack.pop()] += time - prevTime + 1;
prevTime = time + 1;
}
}
return times;
}
}JavaScript решение
сопоставлено/оригинал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;
};Python решение
сопоставлено/оригиналdef exclusiveTime(n, logs):
stack = []
times = [0] * n
prev_time = 0
for log in logs:
fid, typ, time = log.split(':')
fid, time = int(fid), int(time)
if typ == 'start':
if stack:
times[stack[-1]] += time - prev_time
stack.append(fid)
prev_time = time
else:
times[stack.pop()] += time - prev_time + 1
prev_time = time + 1
return timesGo решение
сопоставлено/оригиналpackage main
import (
"fmt"
"strconv"
"strings"
)
func exclusiveTime(n int, logs []string) []int {
stack := []int{}
times := make([]int, n)
prevTime := 0
for _, log := range logs {
parts := strings.Split(log, ":")
fid, _ := strconv.Atoi(parts[0])
typ := parts[1]
time, _ := strconv.Atoi(parts[2])
if typ == "start" {
if len(stack) > 0 {
times[stack[len(stack)-1]] += time - prevTime
}
stack = append(stack, fid)
prevTime = time
} else {
times[stack[len(stack)-1]] += time - prevTime + 1
stack = stack[:len(stack)-1]
prevTime = time + 1
}
}
return times
}Algorithm
Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.
Использование стека
Используйте стек для отслеживания текущих вызовов функций. Если лог содержит start, добавьте функцию в стек и начните отсчет времени. Если лог содержит end, снимите функцию со стека и обновите эксклюзивное время.
Обновление времени выполнения
Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.