Exclusive Time of Functions
给一个单线程CPU和一个log, 求问每个thread自己独占CPU的时间. 这个题很tricky, 因为根本看不懂题目要求, 本来以为简单的线性扫描就可以了, 然后发现thread里有递归的出现,即: 同一个id连续start多次. 那么只能模拟栈了. 然后还需要注意的是, 因为是单线程, 所以不会出现两个线程重叠的情况, 即: 一个id end在另一个id start 和end中.
用stack的时候, 只放start time, 然后遇到end的时候, 计算time chunk. 因为end在time chunk之后, 所以要做差后+1. 另外, 还需要注意, 每当一个id end, 要看是否stack中有其他thread在等待, 这时候要在等待的id中减去当前的时间, 因为对于等待的id, 这段时间已经被当前id所占有.
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
Stack<int[]> stack = new Stack<>();
int[] res = new int[n];
for(String log : logs) {
String[] strs = log.split(":");
Integer id = Integer.valueOf(strs[0]);
String opt = strs[1];
Integer time = Integer.valueOf(strs[2]);
if(opt.equals("start")) {
stack.push(new int[]{id, time});
} else {
int[] prev = stack.pop();
int diff = time - prev[1] + 1; // the time different
res[id] += diff;
if(!stack.isEmpty()) {
int[] p = stack.peek();
res[p[0]] -= diff; // use negative to mark the previous waiting thread
}
}
}
return res;
}
}