LeetCode Exclusive Time of Functions 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:

1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won’t start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100

---

给定一个单核单线程的CPU，并且给出了该CPU跑不同函数的开始时间和结束时间，问每个函数单独运行的时间是多少。因为有些函数可能会调用其他函数，还可能递归调用自己，所以需要去掉调用其他函数的时间，只给出该函数自己运行的时间。 用Node记录每一个记录，Node包含四个属性：function_id，start_or_end，timestamp和exclude_time，前三个就是题目中描述的属性，最后一个exclude_time是指该函数调用其他函数花费的时间，需要减去的时间。 考虑到递归调用，递归返回之类的，马上想到函数调用的时候需要用堆栈保存现场，所以这里也用堆栈保存所有递归调用的函数。每次遇到新函数的start时，压栈，遇到end时，和栈顶求一下时间差，弹栈，并把时间差记录到结果数组中。同时，需要把这个函数用掉的时间累加到栈顶（也就是主调函数）Node的exclude_time中，这一点非常重要。 最后，因为一个函数可能出现多次，所以不论是对结果数组的赋值还是对exclude_time的赋值，都用+=，不能用赋值，否则会覆盖掉之前的数据。 完整代码如下： [cpp] class Solution { private: struct Node { int id_; bool start_; int timestamp_; int exclude_time_; }; void ParseLog(const string& log, Node& node) { size_t colon_pos = log.find(‘:’); node.id_ = stoi(log.substr(0, colon_pos)); if (log[colon_pos + 1] == ‘s’) node.start_ = true; else node.start_ = false; colon_pos = log.find(‘:’, colon_pos + 1); node.timestamp_ = stoi(log.substr(colon_pos + 1)); node.exclude_time_ = 0; } public: vector<int> exclusiveTime(int n, vector<string>& logs) { vector<int> ans(n); stack<Node> stk; for (const auto& log : logs) { Node node; ParseLog(log, node); if (node.start_) { stk.push(node); } else { Node start_node = stk.top(); stk.pop(); int cur_time = node.timestamp_ – start_node.timestamp_ + 1 – start_node.exclude_time_; // caution ans[node.id_] += cur_time; // caution if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution } } return ans; } }; [/cpp] 本代码提交AC，用时23MS。]]>