資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++函式的獨佔時間
假設在一個單執行緒CPU上，我們執行一些函式。每個函式都有一個從0到N-1的唯一ID。我們將按時間戳順序儲存描述函式何時進入或退出的日誌。
這裡的每個日誌都是一個字串，格式為：“{function_id}:{“start” | “end"}:{timestamp}”。例如，如果字串像“0:start:3”，這意味著ID為0的函式在時間戳3的開始處啟動。“1:end:2”表示ID為1的函式在時間戳2的結束處結束。函式的獨佔時間是花費在此函式上的時間單位數。
因此，如果輸入類似於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的開始處再次執行，並在時間6的結束處結束，因此執行了1個時間單位。因此我們可以看到函式0花費了2 + 1 = 3個時間單位進行總執行時間，而函式1花費了4個時間單位進行總執行時間。
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為n的陣列ret，定義堆疊st
j := 0, prev := 0
for i in range 0 to log陣列大小 – 1
temp := logs[i], j := 0, id := 0, num := 0, type := 空字串
while temp[j] 不是冒號
id := id * 10 + 將temp[j]轉換為數字
j增加1
j增加1
while temp[j] 不是冒號
type := type 連線 temp[j]
j增加1
j增加1
while j < temp的大小
num := num * 10 + 將temp[j]轉換為數字
j增加1
if type = start，則
if st不為空
ret[堆疊頂部的元素]增加 num – prev
將id插入st，prev := num
否則
x := st的頂部，並刪除堆疊的頂部
ret[x] := ret[x] + (num + 1) – prev
prev := num + 1
返回ret
示例(C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector <int> ret(n);
stack <int> st;
int id, num;
int j = 0;
string temp;
string type;
int prev = 0;
for(int i = 0; i < logs.size(); i++){
temp = logs[i];
j = 0;
id = 0;
num = 0;
type = "";
while(temp[j] != ':'){
id = id * 10 + (temp[j] - '0');
j++;
}
j++;
while(temp[j] != ':'){
type += temp[j];
j++;
}
j++;
while(j < temp.size()){
num = num * 10 + temp[j] - '0';
j++;
}
if(type == "start"){
if(!st.empty()){
ret[st.top()] += num - prev;
}
st.push(id);
prev = num;
} else {
int x = st.top();
st.pop();
ret[x] += (num + 1) - prev;
prev = num + 1;
}
}
return ret;
}
};
main(){
vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
Solution ob;
print_vector(ob.exclusiveTime(2, v));
}輸入
2 ["0:start:0","1:start:2","1:end:5","0:end:6"]
輸出
[3, 4, ]
233 次檢視
