C++函数的独占时间

假设在一个单线程CPU上，我们执行一些函数。每个函数都有一个从0到N-1的唯一ID。我们将按时间戳顺序存储描述函数何时进入或退出的日志。

这里的每个日志都是一个字符串，格式为：“{function_id}:{“start” | “end"}:{timestamp}”。例如，如果字符串像“0:start:3”，这意味着ID为0的函数在时间戳3的开始处启动。“1:end:2”表示ID为1的函数在时间戳2的结束处结束。函数的独占时间是花费在此函数上的时间单位数。

因此，如果输入类似于n = 2且logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]，则输出将为[3,4]。这是因为函数0从时间0开始，然后执行2个时间单位并到达时间1的结束。之后，函数1从时间2开始，执行4个时间单位并在时间5结束。函数0在时间6的开始处再次运行，并在时间6的结束处结束，因此执行了1个时间单位。因此我们可以看到函数0花费了2 + 1 = 3个时间单位进行总执行时间，而函数1花费了4个时间单位进行总执行时间。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个大小为n的数组ret，定义堆栈st

• j := 0, prev := 0

• for i in range 0 to log数组大小 – 1

  • temp := logs[i], j := 0, id := 0, num := 0, type := 空字符串

• while temp[j] 不是冒号

  • id := id * 10 + 将temp[j]转换为数字

  • j增加1

• j增加1

• while temp[j] 不是冒号

  • type := type 连接 temp[j]

  • j增加1

• j增加1

• while j < temp的大小

  • num := num * 10 + 将temp[j]转换为数字

  • j增加1

• if type = start，则

  • if st不为空

    • ret[堆栈顶部的元素]增加 num – prev

  • 将id插入st，prev := num

• 否则

  • x := st的顶部，并删除堆栈的顶部

  • ret[x] := ret[x] + (num + 1) – prev

  • prev := num + 1

• 返回ret

示例(C++)

让我们看看下面的实现，以便更好地理解：

 在线演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> exclusiveTime(int n, vector<string>& logs) {
      vector <int> ret(n);
      stack <int> st;
      int id, num;
      int j = 0;
      string temp;
      string type;
      int prev = 0;
      for(int i = 0; i < logs.size(); i++){
         temp = logs[i];
         j = 0;
         id = 0;
         num = 0;
         type = "";
         while(temp[j] != ':'){
            id = id * 10 + (temp[j] - '0');
            j++;
         }
         j++;
         while(temp[j] != ':'){
            type += temp[j];
            j++;
         }
         j++;
         while(j < temp.size()){
            num = num * 10 + temp[j] - '0';
            j++;
         }
         if(type == "start"){
            if(!st.empty()){
               ret[st.top()] += num - prev;
            }
            st.push(id);
            prev = num;
         } else {
            int x = st.top();
            st.pop();
            ret[x] += (num + 1) - prev;
            prev = num + 1;
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
   Solution ob;
   print_vector(ob.exclusiveTime(2, v));
}

输入

2
["0:start:0","1:start:2","1:end:5","0:end:6"]

输出

[3, 4, ]

Arnab Chakraborty

更新于：2020年5月2日

233 次查看

启动你的职业生涯

通过完成课程获得认证

开始学习