leetcode 636. Exclusive Time of Functions 函数的单独运行时间 + stringstream很好应用

迈不过友情╰ 2022-06-03 06:12 87阅读 0赞

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function\_id:start\_or\_end:timestamp. For example, “0:start:0” means function 0 starts from **the very beginning of time 0.** “0:end:0” means function 0 ends to **the very end of time 0.**

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:  
Input:  
n = 2  
logs =  
\[“0:start:0”,  
“1:start:2”,  
“1:end:5”,  
“0:end:6”\]  
Output:\[3, 4\]  
Explanation:  
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.  
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.  
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.  
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.  
Note:  
Input logs will be sorted by timestamp, NOT log id.  
Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.  
Two functions won’t start or end at the same time.  
Functions could be called recursively, and will always end.  
1 <= n <= 100

这道题有点绕，看了大半天才明白意思

函数开启了就压入栈，结束了就出栈，不会有函数被漏掉。这样的我们可以遍历每个log，然后把三部分分开，函数idx，类型type，时间点time。如果此时栈不空，说明之前肯定有函数在跑，那么不管当前时start还是end，之前函数时间都得增加，增加的值为time - preTime，这里的preTime是上一个时间点。然后我们更新preTime为当前时间点time。然后我们判断log的类型，如果是start，我们将当前函数压入栈；如果是end，那么我们将栈顶元素取出，对其加1秒，并且preTime也要加1秒，

建议和[\[LeetCode\] Exclusive Time of Functions 函数的独家时间][LeetCode_ Exclusive Time of Functions] 一起学习。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs)
        {
            vector<int> res(n, 0);
            stack<int> skt;
            int pretime = 0;
            for (string log : logs)
            {
                int i = log.find_first_of(':');
                int j = log.find_last_of(':');
    
                int id = stoi(log.substr(0, i));
                string type = log.substr(i + 1, j - i - 1);
                int time = stoi(log.substr(j + 1));
                if (skt.empty() == false)
                    res[skt.top()] += time - pretime;
                pretime = time;
                if (type == "start")
                    skt.push(id);
                else
                {
                    res[skt.top()] += 1;
                    skt.pop();
                    pretime++;
                }
            }
            return res;
        }
    };

[LeetCode_ Exclusive Time of Functions]: https://www.cnblogs.com/grandyang/p/7244767.html