LeetCode 636 : Exclusive Time of Functions（python）

原题

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions. Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function. A log is a string has this format : function_id:start_or_end:timestamp. For example, “0:start:0” means function 0 starts from the very beginning of time 0. “0:end:0” means function 0 ends to the very end of time 0. Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1: Input: n = 2 logs = [“0:start:0”,”1:start:2”,”1:end:5”,”0:end:6”] Output:[3, 4] Explanation: Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1. Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5. Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time. So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note: Input logs will be sorted by timestamp, NOT log id. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0. Two functions won’t start or end at the same time. Functions could be called recursively, and will always end. 1 <= n <= 100

思路

题目讲的是单线程CPU时间片计算的问题。所谓单线程，就是CPU在任意时刻只能运行一个线程。假设线程a在运行过程中，另一个线程b要抢占资源，那么a必须进入等待状态，直到b运行完之后再继续运行。 如题目中的例子： [“0:start:0”,”1:start:2”,”1:end:5”,”0:end:6”]。 线程0在时间片0开始运行；时间片2时运行线程1（此时线程0已经运行了0和1两个时间片，还没运行结束，只能进入等待状态）；时间片5时，线程1运行结束（那么线程1运行了2、3、4、5四个时间片）；时间片6时，刚刚等待的线程0运行结束（其实时间片5线程1运行一结束，刚刚等待的线程0就马上进入运行，直到6结束，刚好占用了6一个时间片）。 综合上面分析，线程1运行了0、1、6三个时间片，线程2运行了2、3、4、5四个时间片。 在本题中，用Id、Kind和Time分别表示logs[i]中线程Id、start or end、时刻，preId、preKind、preTime分别表示logs[i-1]中线程Id、start or end、时刻。线程运行时间计算可分为两类：（1）没有被抢占的线程，其运行时间=结束时刻-开始时刻+1；（2）被抢占的线程，其运行时间=被抢占前运行时间+被抢占后运行时间。判断线程是否被抢占，本题通过对Kind和preKind分4种情况进行讨论，详见代码及注释。 由于是递归调用，本题还需维持一个startList。startList维持的是还没结束运行的线程列表。如果有线程运行，即加入startList末端；如果有线程结束运行，则删除startList的最后一个元素。startList的作用就如同一个栈，用于在有线程等待的情况下，判断最后进入等待的线程Id，因为这是下一个要进入运行的线程！

代码

class Solution: def exclusiveTime(self, n, logs): """ :type n: int :type logs: List[str] :rtype: List[int] """ rList=[0]*n startList=[] preId=int(logs[0].split(':')[0]) preKind=logs[0].split(':')[1] preTime=int(logs[0].split(':')[2]) startList.append(preId) for i in range(1,len(logs)): Id=int(logs[i].split(':')[0]) Kind=logs[i].split(':')[1] Time=int(logs[i].split(':')[2]) if(Kind=='start'): startList.append(Id) #被抢占，抢占前运行时间 #Id抢占资源，preId进入等待。这种情况要计算preId等待前已经运行的时间 if(preKind=='start'): rList[preId]+=(Time-preTime) #被抢占，抢占后运行时间 #preId结束后到Id开始前，有一段时间，这段时间其实就是startList上最近一个等待的线程在运行的时间，参考实例如下 #example2:n=2,logs=["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"] #在"0:end:5","1:start:7"期间，有个时间片6，这个时间就是"0:start:0"运行的时间 else: if(len(startList)>1): rList[startList[-2]]+=(Time-preTime-1) else: del startList[-1] #没有被抢占的线程运行时间 #由于是递归调用，所以这种情况下，必有Id=preId，参考实例如下 #example1:n=1,logs=["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"] #在"0:start:2","0:end:5"，出现一个end，如果前一个是start，则必有Id=preId if(preKind=='start'): rList[Id]+=(Time-preTime+1) #被抢占，抢占后运行时间 else: rList[Id]+=(Time-preTime) preId=Id preKind=Kind preTime=Time return rList