636. Exclusive Time of Functions

leetcode medium

#array#csharp#leetcode#medium#recursion#stack#string

Task

На однопоточном процессоре выполняется программа, содержащая 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# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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 times

Go solution

matched/original

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
}

Explanation

Algorithm

Парсинг логов

Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

Использование стека

Используйте стек для отслеживания текущих вызовов функций. Если лог содержит start, добавьте функцию в стек и начните отсчет времени. Если лог содержит end, снимите функцию со стека и обновите эксклюзивное время.

Обновление времени выполнения

Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.

😎