636. 函式的獨佔時間 : 簡單棧運用模擬題

語言: CN / TW / HK

題目描述

這是 LeetCode 上的 636. 函式的獨佔時間 ,難度為 中等

Tag : 「模擬」、「棧」

有一個單執行緒 CPU 正在執行一個含有 n 道函式的程式。每道函式都有一個位於  0n-1 之間的唯一識別符號。

函式呼叫 儲存在一個呼叫棧上 :當一個函式呼叫開始時,它的識別符號將會推入棧中。而當一個函式呼叫結束時,它的識別符號將會從棧中彈出。識別符號位於棧頂的函式是當前正在執行的函式。每當一個函式開始或者結束時,將會記錄一條日誌,包括函式識別符號、是開始還是結束、以及相應的時間戳。

給你一個由日誌組成的列表 logs ,其中 logs[i] 表示第 i 條日誌訊息,該訊息是一個按 "{function_id}:{"start" | "end"}:{timestamp}" 進行格式化的字串。例如, "0:start:3" 意味著識別符號為 0 的函式呼叫在時間戳 3 的 起始開始執行 ;而 "1:end:2" 意味著識別符號為 1 的函式呼叫在時間戳 2 的末尾結束執行。注意,函式可以呼叫多次,可能存在遞迴呼叫 。

函式的「獨佔時間」定義是在這個函式在程式所有函式呼叫中執行時間的總和,呼叫其他函式花費的時間不算該函式的獨佔時間。例如,如果一個函式被呼叫兩次,一次呼叫執行 2 單位時間,另一次呼叫執行 1 單位時間,那麼該函式的獨佔時間為 2 + 1 = 3

以陣列形式返回每個函式的獨佔時間,其中第 i 個下標對應的值表示識別符號 i 的函式的獨佔時間。

示例 1:

輸入: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 的開始恢復執行,執行 1 個單位時間。 
所以函式 0 總共執行 2 + 1 = 3 個單位時間,函式 1 總共執行 4 個單位時間。

示例 2:

輸入:n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]

輸出:[8]

解釋:
函式 0 在時間戳 0 的起始開始執行,執行 2 個單位時間,並遞迴呼叫它自身。
函式 0(遞迴呼叫)在時間戳 2 的起始開始執行,執行 4 個單位時間。
函式 0(初始呼叫)恢復執行,並立刻再次呼叫它自身。
函式 0(第二次遞迴呼叫)在時間戳 6 的起始開始執行,執行 1 個單位時間。
函式 0(初始呼叫)在時間戳 7 的起始恢復執行,執行 1 個單位時間。
所以函式 0 總共執行 2 + 4 + 1 + 1 = 8 個單位時間。

示例 3:

輸入:n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]

輸出:[7,1]

解釋:
函式 0 在時間戳 0 的起始開始執行,執行 2 個單位時間,並遞迴呼叫它自身。
函式 0(遞迴呼叫)在時間戳 2 的起始開始執行,執行 4 個單位時間。
函式 0(初始呼叫)恢復執行,並立刻呼叫函式 1 。
函式 1在時間戳 6 的起始開始執行,執行 1 個單位時間,於時間戳 6 的末尾結束執行。
函式 0(初始呼叫)在時間戳 7 的起始恢復執行,執行 1 個單位時間,於時間戳 7 的末尾結束執行。
所以函式 0 總共執行 2 + 4 + 1 = 7 個單位時間,函式 1 總共執行 1 個單位時間。

示例 4:

輸入:n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]

輸出:[8,1]

示例 5:

輸入:n = 1, logs = ["0:start:0","0:end:0"]

輸出:[1]

提示:

  • $1 <= n <= 100$
  • $1 <= logs.length <= 500$
  • $0 <= function_id < n$
  • $0 <= timestamp <= 10^9$
  • 兩個開始事件不會在同一時間戳發生
  • 兩個結束事件不會在同一時間戳發生
  • 每道函式都有一個對應  "start" 日誌的 "end" 日誌

模擬

我們使用「棧」來模擬執行過程:當一個函式被呼叫( op = start )時,壓入棧內,當函式呼叫完成( op = end )時,從棧頂彈出(此時棧頂元素必然是該結束函式的入棧記錄),使用變數 cur 記錄當前時間。

從前往後處理所有的 $log[i]$,根據 $log[i]$ 是屬於函式呼叫還是函式結束進行分情況討論:

  • 當 $log[i]$ 為函式呼叫:此時從該函式的呼叫發起時間 ts 到上一次記錄的當前時間,都是前一函式的執行時間,因此可以將 ts - cur 累加到棧幀中的前一函式。即若棧不為空,則將該時間累加到棧頂對應的函式上,然後將 $log[i]$ 入棧,同時更新當前時間;
  • 當 $log[i]$ 為函式結束:此時棧頂元素必然是該函式的呼叫記錄,此時 $log[i]$ 的結束時間與上一次記錄的當前時間的時長 ts - cur + 1 ,必然是該函式的執行時間,將其累加到當前函式中,並更新當前時間。

Java 程式碼:

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        Deque<Integer> d = new ArrayDeque<>();
        int cur = -1;
        for (String log : logs) {
            String[] ss = log.split(":");
            int idx = Integer.parseInt(ss[0]), ts = Integer.parseInt(ss[2]);
            if (ss[1].equals("start")) {
                if (!d.isEmpty()) ans[d.peekLast()] += ts - cur;
                d.addLast(idx);
                cur = ts;
            } else {
                int func = d.pollLast();
                ans[func] += ts - cur + 1;
                cur = ts + 1;
            }
        }
        return ans;
    }
}

TypeScript 程式碼:

function exclusiveTime(n: number, logs: string[]): number[] {
    const ans = new Array<number>(n).fill(0)
    const stk = new Array<number>()
    let he = 0, ta = 0, cur = -1
    for (let log of logs) {
        const ss = log.split(":")
        const idx = Number(ss[0]), ts = Number(ss[2])
        if (ss[1] == "start") {
            if (he < ta) ans[stk[ta - 1]] += ts - cur
            stk[ta++] = idx
            cur = ts
        } else {
            const func = stk[--ta]
            ans[func] += ts - cur + 1
            cur = ts + 1
        }
    }
    return ans
};
  • 時間複雜度:$O(n)$
  • 空間複雜度:$O(n)$

最後

這是我們「刷穿 LeetCode」系列文章的第 No.636 篇,系列開始於 2021/01/01,截止於起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們將先把所有不帶鎖的題目刷完。

在這個系列文章裡面,除了講解解題思路以外,還會盡可能給出最為簡潔的程式碼。如果涉及通解還會相應的程式碼模板。

為了方便各位同學能夠電腦上進行除錯和提交程式碼,我建立了相關的倉庫: https://github.com/SharingSou...

在倉庫地址裡,你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:

本文由mdnice多平臺釋出