@(LeetCode)
问题描述
我们将在一个单线程 cpu 上执行一些函数。每个函数有个唯一 id, 范围是 [0, N-1]。
我们按时间顺序存储日志，这些日志描述了函数进入或退出的时机。
每个日志是个字符串，其格式为：{function_id}:{"start" | "end"}:{timestamp}。
举个栗子，"0:start:3" 表示函数 0 在时间戳为 3 时启动。"1:end:2" 表示函数 1 在时间戳为 2 的时候停止。
一个函数的独占执行时间是指在该函数上花费的时间片。注意函数没有递归调用或者调用子函数。
CPU 是单线程的，意味着在一个时间片中只能执行一个函数。
要求按照函数 id 顺序，返回每个函数的独占执行时间。
栗 1：
WX20200419-143646@2x.png
输入：
n = 2
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
输出：[3, 4]
解释：
函数 0 在 0 时启动，它会执行 2 个时间片；
函数 1 在 2 时启动，在 5 时结束，执行了 4 个时间片；
函数 0 在 6 时结束，执行了 1 个时间片。
因此，函数 0 总共执行时间为 2 + 1 = 3，函数 1 的时间为 4。
注意：
-
1 <= n <= 100。 - 两个函数不会在相同的时间点开始或结束。
- 当函数退出时，也会打印日志。
解题思路
首先梳理一下题意：
- 日志是按时间顺序存储的。
-
start、end代表了函数的开始和结束。 - 由于是单线程，所以
end的函数一定是前一个start的函数。 - 如果
cpu空闲了，前一个被挂起的函数会执行。 - 按函数 id 大小返回结果。
这里有个小技巧。由于至多只有0 <= n <= 100个函数，完全可以初始化一个有n个元素的数组，且值都为0。之后直接根据函数id填值即可。
另外还有重要的一点：
同一个函数可能被
start多次。
这是我在提交代码出错后，看它的测试用例才知道。此时才发现原来我的解法完全的错了。
初始想法
由于没有考虑到一个函数会被 start 多次，因此按照常规的思路，将每个函数执行的开始/结束时间存下来，然后判断是否在其他函数执行时间段内，来计算真正的执行时间。
但提交代码时，傻眼了，原来还有多次 start 的情况。那么这种解法完全不行。
正确思路
由于日志是按时间顺序排列的，那么我们按照这个顺序去遍历就好。
但是遍历时，前后函数 log 可能存在的情况较多，假设前一个函数的时间戳为 t1，后一个函数的时间戳为 t2。具体情况如下：
-
start-start
在这种情况下，又分为同一个函数和不同的函数。- 对于同一个函数
0：["0:start:0","0:start:2",...]，此时函数0的执行时间为：2-0=2。 - 对于不同的函数：
["0:start:0","1:start:2",...]，此时也还是函数0的执行时间：2。
因此，对于同一个函数或者不同函数来说，其计算方法都一样。通用计算公式为：
t=t2-t1。 - 对于同一个函数
-
end-end- 对于同一个函数：
[...,"1:end:5","1:end:6"]，此时函数1的执行时间为：6-5=1。 - 对于不同的函数：
[...,"1:end:5","0:end:6"]，此时函数0的执行时间为：6-5=1。
与上面
start-start的情况类似，t=t2-t1。 - 对于同一个函数：
-
start-end
这种情况下，前后函数id一定是匹配的。比如：
["1:start:2","1:end:5",...]。因此函数
1的执行时间为：5-2+1=4。通用计算公式为：t=t2-t1+1。 -
end-start这种情况表示：一个函数结束，另一个函数开始。这中间可能会有段空闲时间，可用于执行前一个挂起的函数。
举个栗子：
logs = ["0:start:0","1:start:3","1:end:5","0:start:8",...]- 函数
0在0时开始，函数1在3时开始，此时函数0挂起； - 函数
1在5时结束； - 函数
0在8时开始。
因此，这中间会有
8-5-1=2个空闲的时间片，供前一个挂起的函数0来执行。通用计算公式为：t=t2-t1-1。所以在这种情况下，我们需要记录之前未结束的函数
id，当有空闲时间片时，取出最近的一个函数来执行。 - 函数
通过分析上述情形，我们可以得出：
-
start-start和end-end是同一种处理方式，t=t2-t1。 -
start-end是一次开始和结束的完整过程，t=t2-t1+1。 -
end-start，中间的空闲时间片可以执行挂起的函数，t=t2-t1-1。 - 需要用队列/栈记录未结束的函数
id。在start时记录，在end时删除。
按照各种不同的情况，将对应函数的执行时间片进行累加即可。
case 简化
以上分析的各种情形有点复杂，其实并不用细化到那么多场景。只需要判断当前的日志是 start 还是 end 即可。
- 若当前日志是
start，则：// curTime 表示当前日志的时间戳 // preTime 表示之前的时间戳 t = curTime - preTime preTime = curTime - 若当前日志是
end，则// curTime 表示当前日志的时间戳 // preTime 表示之前的时间戳 t = curTime - preTime + 1 // 注意，这里需要 + 1。因为如果当前时间戳为 5，下一个日志为 start 且时间戳为 6，那么计算出的时间应该为 0，所以要 +1。 preTime = curTime + 1
python 代码如下：
def exclusiveTime(self, N, logs):
ans = [0] * N
stack = []
prev_time = 0
for log in logs:
fn, typ, time = log.split(':')
fn, time = int(fn), int(time)
if typ == 'start':
if stack:
ans[stack[-1]] += time - prev_time
stack.append(fn)
prev_time = time
else:
ans[stack.pop()] += time - prev_time + 1
prev_time = time + 1
return ans
网友评论