原题
给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。
每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。
日志是具有以下格式的字符串：function_id：start_or_end：timestamp。例如："0:start:0" 表示函数 0 从 0 时刻开始运行。"0:end:0" 表示函数 0 在 0 时刻结束。
函数的独占时间定义是在该方法中花费的时间，调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。
示例 1:
输入:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"] 输出:[3, 4] 说明：
函数 0 在时刻 0 开始，在执行了 2个时间单位结束于时刻 1。
现在函数 0 调用函数 1，函数 1 在时刻 2 开始，执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行，并在时刻 6 结束运行，从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位，函数 1 总共执行了 4 个时间单位。
说明：
- 输入的日志会根据时间戳排序，而不是根据日志Id排序。
- 你的输出会根据函数Id排序，也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。
- 两个函数不会在同时开始或结束。
- 函数允许被递归调用，直到运行结束。
- 1 <= n <= 100
解法
思想
函数的调用天生符合栈的思想
代码
我一开始使用了辅助类记录足够的信息。
class FunctionTime{
String function_id;
String timestamp;
FunctionTime(String function_id,String timestamp){
this.function_id = function_id;
this.timestamp = timestamp;
}
}
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] ans = new int[n];
Stack<FunctionTime> stack = new Stack<>();
for(String i:logs){
String[] info = i.split(":");
if(!stack.isEmpty()&&info[1].equals("end")){
FunctionTime func = stack.pop();
ans[Integer.valueOf(func.function_id)]+=(Integer.valueOf(info[2])-Integer.valueOf(func.timestamp)+1);
//新方法结束时把原方法开始的时间设为当前时间+1。
if(!stack.isEmpty())
stack.peek().timestamp = String.valueOf(Integer.valueOf(info[2])+1);
}else{
if(!stack.isEmpty()) {
//新方法开始时给上一个方法加上时间。
FunctionTime peek = stack.peek();
ans[Integer.valueOf(peek.function_id)]+=(Integer.valueOf(info[2])-Integer.valueOf(peek.timestamp));
}
FunctionTime func = new FunctionTime(info[0],info[2]);
stack.push(func);
}
}
return ans;
}
}
然后发现可以简化。
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] ans = new int[n];
Stack<Integer> stack = new Stack();
int curTime = 0;
for(String i:logs){
String[] info = i.split(":");
int id = Integer.valueOf(info[0]);
int timestamp = Integer.valueOf(info[2]);
if(info[1].equals("start")){
if(!stack.isEmpty()){
ans[stack.peek()] += timestamp - curTime;
}
stack.push(id);
curTime = timestamp;
}else{
timestamp++;
ans[stack.pop()] += timestamp - curTime;
}
curTime = timestamp;
}
return ans;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode636-%e5%87%bd%e6%95%b0%e7%9a%84%e7%8b%ac%e5%8d%a0%e6%97%b6%e9%97%b4/
