Giả sử trên một CPU đơn luồng, chúng ta thực thi một số chức năng. Bây giờ mỗi hàm có một id duy nhất từ 0 đến N-1. Chúng tôi sẽ lưu trữ nhật ký theo thứ tự dấu thời gian mô tả thời điểm một hàm được nhập hoặc thoát.
Ở đây mỗi nhật ký là một chuỗi được viết theo định dạng sau:"{function_id}:{" start "|" end "}:{timestamp}". Ví dụ:nếu chuỗi giống như "0:start:3", điều này có nghĩa là hàm có id 0 bắt đầu ở đầu dấu thời gian 3. "1:end:2" có nghĩa là hàm có id 1 kết thúc ở cuối dấu thời gian 2. Thời gian dành riêng cho một chức năng là số đơn vị thời gian dành cho chức năng này.
Vì vậy, nếu đầu vào là n =2 và logs =["0:start:0", "1:start:2", "1:end:5", "0:end:6"], thì đầu ra sẽ được [3,4]. Điều này là do hàm 0 bắt đầu ở đầu thời điểm 0, sau đó nó thực hiện 2 đơn vị thời gian và đến cuối thời gian 1. Sau đó hàm 1 bắt đầu ở đầu thời điểm 2, thực hiện 4 đơn vị thời gian và kết thúc ở thời điểm 5 . Hàm 0 đang chạy lại vào đầu thời điểm 6 và cũng kết thúc vào cuối thời điểm 6, do đó thực thi trong 1 đơn vị thời gian. Vì vậy, chúng ta có thể thấy rằng hàm 0 dành 2 + 1 =3 đơn vị tổng thời gian để thực thi và hàm 1 dành 4 đơn vị tổng thời gian để thực thi.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định ret mảng có kích thước n, xác định ngăn xếp
-
j:=0, trước:=0
-
cho tôi trong phạm vi từ 0 đến kích thước của mảng nhật ký - 1
-
temp:=logs [i], j:=0, id:=0, num:=0, type:=blank string
-
-
trong khi temp [j] không phải là dấu hai chấm
-
id:=id * 10 + temp [j] là số
-
tăng j lên 1
-
-
tăng j lên 1
-
trong khi temp [j] không phải là dấu hai chấm
-
type:=type concatenate temp [j]
-
tăng j lên 1
-
-
tăng j lên 1
-
trong khi j
-
num:=num * 10 + temp [j] là số
-
tăng j lên 1
-
-
if type =start, then
-
nếu st không trống
-
tăng ret [phần tử trên cùng của ngăn xếp] theo num - trước
-
-
chèn d vào st, prev:=num
-
-
nếu không thì
-
x:=top of st và xóa top of stack
-
ret [x]:=ret [x] + (num + 1) - trước
-
trước:=num + 1
-
-
trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
2 ["0:start:0","1:start:2","1:end:5","0:end:6"]
Đầu ra
[3, 4, ]