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所占有.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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; } } |