文章目錄
- 1. 題目
- 2. 解題
1. 題目
給出一個非搶占單執行緒CPU的 n 個函式運行日志，找到函式的獨占時間，
每個函式都有一個唯一的 Id，從 0 到 n-1，函式可能會遞回呼叫或者被其他函式呼叫，
日志是具有以下格式的字串：function_id：start_or_end：timestamp，
例如："0:start:0" 表示函式 0 從 0 時刻開始運行，
"0:end:0" 表示函式 0 在 0 時刻結束，
函式的獨占時間定義是在該方法中花費的時間，呼叫其他函式花費的時間不算該函式的獨占時間，
你需要根據函式的 Id 有序地回傳每個函式的獨占時間，
示例 1:
輸入:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
輸出:[3, 4]
說明：
函式 0 在時刻 0 開始，在執行了 2個時間單位結束于時刻 1，
現在函式 0 呼叫函式 1，函式 1 在時刻 2 開始，執行 4 個時間單位后結束于時刻 5，
函式 0 再次在時刻 6 開始執行，并在時刻 6 結束運行，從而執行了 1 個時間單位，
所以函式 0 總共的執行了 2 +1 =3 個時間單位，函式 1 總共執行了 4 個時間單位，
說明：
輸入的日志會根據時間戳排序，而不是根據日志Id排序，
你的輸出會根據函式Id排序，也就意味著你的輸出陣列中序號為 0 的元素相當于函式 0 的執行時間，
兩個函式不會在同時開始或結束，
函式允許被遞回呼叫，直到運行結束，
1 <= n <= 100
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/exclusive-time-of-functions
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2. 解題
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> time(n, 0);
stack<pair<int,int>> s;// id, time
int id, t, period = 0, p1, p2;
for(auto& log : logs)
{
p1 = log.find(':');
id = stoi(log.substr(0,p1));//提取id
p2 = log.find_last_of(':');
t = stoi(log.substr(p2+1));//提取t
if(log[p1+1]=='e')//當前是結束，那么堆疊頂是開始
{
period = t-s.top().second+1;//當前函式的執行時間
time[id] += period;//函式執行時間增加
s.pop();//彈堆疊
if(!s.empty())//堆疊不為空，說明有外層函式
// 外層函式的時間要減去內層執行時間
time[s.top().first] -= period;
}
else
{
s.push({id, t});
}
}
return time;
}
};
28 ms 13 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/126489.html
標籤：其他
上一篇：iis ip地址和域限制問題