636.函数的独占时间

链接：636.函数的独占时间
难度：Medium
标签：栈、数组
简介：给出一个非抢占单线程 CPU 的 n 个函数运行日志，找到函数的独占时间。

题解 1 - typescript

• 编辑时间：2021-03-20
• 执行用时：116ms
• 内存消耗：42.8MB
• 编程语言：typescript
• 解法介绍：利用栈维护函数运行过程。

function exclusiveTime(n: number, logs: string[]): number[] {
  const ans = new Array(n).fill(0);
  const stack: number[] = [];
  for (let i = 0, l = logs.length, pre = 0; i < l; i++) {
    const info = logs[i].split(':');
    const id = Number(info[0]);
    const tag = info[1];
    const time = Number(info[2]);
    if (tag === 'start') {
      if (stack.length !== 0) ans[stack[stack.length - 1]] += time - pre;
      pre = time;
      stack.push(id);
    } else {
      ans[id] += time - pre + 1;
      pre = time + 1;
      stack.pop();
    }
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2022-08-07
• 执行用时：12ms
• 内存消耗：13MB
• 编程语言：cpp
• 解法介绍：stack。

class Solution {
  public:
    typedef pair<int, int> node;
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> list(n, 0);
        stack<node> s;
        for (auto &item : logs) {
            bool isStart;
            int idx = 0, time = 0;
            analysis(item, idx, isStart, time);
            if (s.size()) {
                if (isStart) {
                    node top = s.top();
                    list[top.first] += time - top.second;
                    s.push(make_pair(idx, time));
                } else {
                    node top = s.top(); s.pop();
                    list[top.first] += time - top.second + 1;
                    if (s.size()) {
                        top = s.top(); s.pop();
                        top.second = time + 1;
                        s.push(top);
                    }
                }
            } else {
                s.push(make_pair(idx, time));
            }
        }
        return list;
    }
    void analysis(string &item, int &idx, bool &isStart, int &time) {
        int i = 0;
        for (; item[i] != ':'; i++) idx = idx * 10 + item[i] - '0';
        i++;
        string temp = "";
        for (; item[i] != ':'; i++) temp += item[i];
        isStart = temp == "start";
        i++;
        for (; i < item.size(); i++) time = time * 10 + item[i] - '0';
    }
};