数据结构
网络
关系数据库管理系统 (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 次查看
