文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給出一個(gè)非搶占單線程CPU的 n 個(gè)函數(shù)運(yùn)行日志，找到函數(shù)的獨(dú)占時(shí)間。

每個(gè)函數(shù)都有一個(gè)唯一的 Id，從 0 到 n-1，函數(shù)可能會(huì)遞歸調(diào)用或者被其他函數(shù)調(diào)用。

日志是具有以下格式的字符串：function_id：start_or_end：timestamp。
例如："0:start:0" 表示函數(shù) 0 從 0 時(shí)刻開始運(yùn)行。
"0:end:0" 表示函數(shù) 0 在 0 時(shí)刻結(jié)束。

函數(shù)的獨(dú)占時(shí)間定義是在該方法中花費(fèi)的時(shí)間，調(diào)用其他函數(shù)花費(fèi)的時(shí)間不算該函數(shù)的獨(dú)占時(shí)間。
你需要根據(jù)函數(shù)的 Id 有序地返回每個(gè)函數(shù)的獨(dú)占時(shí)間。

示例 1: 輸入: n = 2 logs = ["0:start:0","1:start:2","1:end:5","0:end:6"] 輸出:[3, 4]說(shuō)明： 函數(shù) 0 在時(shí)刻 0 開始，在執(zhí)行了 2個(gè)時(shí)間單位結(jié)束于時(shí)刻 1。 現(xiàn)在函數(shù) 0 調(diào)用函數(shù) 1，函數(shù) 1 在時(shí)刻 2 開始，執(zhí)行 4 個(gè)時(shí)間單位后結(jié)束于時(shí)刻 5。 函數(shù) 0 再次在時(shí)刻 6 開始執(zhí)行，并在時(shí)刻 6 結(jié)束運(yùn)行，從而執(zhí)行了 1 個(gè)時(shí)間單位。 所以函數(shù) 0 總共的執(zhí)行了 2 +1 =3 個(gè)時(shí)間單位，函數(shù) 1 總共執(zhí)行了 4 個(gè)時(shí)間單位。說(shuō)明： 輸入的日志會(huì)根據(jù)時(shí)間戳排序，而不是根據(jù)日志Id排序。 你的輸出會(huì)根據(jù)函數(shù)Id排序，也就意味著你的輸出數(shù)組中序號(hào)為 0 的元素相當(dāng)于函數(shù) 0 的執(zhí)行時(shí)間。 兩個(gè)函數(shù)不會(huì)在同時(shí)開始或結(jié)束。 函數(shù)允許被遞歸調(diào)用，直到運(yùn)行結(jié)束。 1 <= n <= 100

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/exclusive-time-of-functions
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution {public:vector<int> exclusiveTime(int n, vector<string>& logs) {vector<int> time(n, 0);stack<pair<int,int>> s;// id, timeint id, t, period = 0, p1, p2;for(auto& log : logs){p1 = log.find(':');id = stoi(log.substr(0,p1));//提取idp2 = log.find_last_of(':');t = stoi(log.substr(p2+1));//提取tif(log[p1+1]=='e')//當(dāng)前是結(jié)束，那么棧頂是開始{period = t-s.top().second+1;//當(dāng)前函數(shù)的執(zhí)行時(shí)間time[id] += period;//函數(shù)執(zhí)行時(shí)間增加s.pop();//彈棧if(!s.empty())//棧不為空，說(shuō)明有外層函數(shù)// 外層函數(shù)的時(shí)間要減去內(nèi)層執(zhí)行時(shí)間time[s.top().first] -= period;}else{s.push({id, t});}}return time;} };

28 ms 13 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 636. 函数的独占时间（栈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。