LeetCode 636. 函数的独占时间

636. 函数的独占时间

题目：详情看链接
链接 https://leetcode.cn/problems/exclusive-time-of-functions/

个人思路

1. 循环，把相邻两个日志之间的时间算出来，然后相应函数所用时间增加，但难以判断起止，目前写不出来：

cache = []
for i in range(0,len(logs)-1):
    a = logs[i].split(':')
    b = logs[i+1].split(':')

    if a[0] == b[0]:
        if a[1] == b[1]:
            res[int(a[0])] += int(b[2]) - int(a[2])
        elif a[1] ==  'start' and b[1] == 'end':
            res[int(a[0])] += int(b[2]) - int(a[2]) + 1
        elif a[1] ==  'end' and b[1] == 'start':
            res[int(a[0])] += int(b[2]) - int(a[2]) - 1
    elif :
        cache.append(int(a[0]))
    # 后续不知道怎么写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 栈，一个start对应一个end，将start压入栈中，遇到end时弹出，但当有嵌套时，初始的函数所用时间难以算出，应该要减去里面的函数的运行时间，然后想到用旗帜来标记是否应该减去时间

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stack1 = [] # 函数
        stack2 = [] # 开始时间
        temp = 0 # 嵌套时间
        stack3 = [0] # 记录是否刚进栈
        res = [0] * n
        for i in range(0,len(logs)):
            a = logs[i].split(':')
            if a[1] == 'start':
                stack1.append(int(a[0]))
                stack2.append(int(a[2]))
                if len(stack3) == 0:
                    stack3.append(0)
                else:
                # 如果其前面还有函数没出栈，那么前面的函数对应的旗帜标为1
                    stack3[-1] = 1
                    stack3.append(0)
             # 当函数都出栈后，记录嵌套时间重置为0
            elif len(stack1) == 1:
                fun = stack1.pop()
                t1 = stack2.pop()
                res[fun] = res[fun] + int(a[2])-t1+1-temp
                temp = 0
            else:
                fun = stack1.pop()
                t1 = stack2.pop()
        #  一个函数所用的时间要减去其前面嵌套了的其他函数所用的时间
                res[fun] = res[fun] + int(a[2]) - t1 + 1 -temp*stack3.pop()
                # 更新temp
                temp = temp + int(a[2]) - t1 + 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

但这个代码过不了第九个实例：
[“0:start:0”,“0:start:1”,“0:start:2”,“0: end:3”,“0: end:4”,“0: end:5”]预期答案为6，但输出为4；错误的原因是，在多重嵌套时，temp会一直累加，但其实只需要减去上一层函数的时间

3. 理清思路后，一个函数所用时间其实就是把其结束时间减去开始时间再减去里面不是该函数的时间即可，重新写如下：
   那么只需要留一个栈来记录每个函数在结束前在其时间段内被占用的时间

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stack1 = [] # 函数
        stack2 = [] #开始时间
        # temp = 0 # 嵌套时间
        stack3 = [0] # 记录是否刚进栈
        res = [0]*n
        for i in range(0,len(logs)):
            a = logs[i].split(':')
            if a[1] == 'start':
                stack1.append(int(a[0]))
                stack2.append(int(a[2]))
        #         if len(stack3) == 0:
        #             stack3.append(0)
        #         else:
        #             stack3[-1] = 1
        #             stack3.append(0)
        # 记录函数将要被其他函数占用的时间，不被占用即进去后就能立刻出即为0
                stack3.append(0)
            elif len(stack1) == 1:
                fun = stack1.pop()
                t1 = stack2.pop()
                time = stack3.pop()
                res[fun] = res[fun] + int(a[2]) - t1 + 1 - time
            else:
                fun = stack1.pop()
                t1 = stack2.pop()
                time = stack3.pop()
                res[fun] = res[fun] + int(a[2]) - t1 + 1 - time
                # 被占用的时间为int(a[2]) - t1 + 1
                stack3[-1] = stack3[-1]+int(a[2]) - t1 + 1
        return res
                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

其实elif那一部分也可以省掉：

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stack1 = [] # 函数
        stack2 = [] #开始时间
        stack3 = [0] # 记录是否刚进栈
        res = [0]*n
        for i in range(0,len(logs)):
            a = logs[i].split(':')
            if a[1] == 'start':
                stack1.append(int(a[0]))
                stack2.append(int(a[2]))
                stack3.append(0)
            else:
                fun = stack1.pop()
                t1 = stack2.pop()
                time = stack3.pop()
                res[fun] = res[fun] + int(a[2]) - t1 + 1 - time
                # 被占用的时间为int(a[2]) - t1 + 1
                stack3[-1] = stack3[-1]+int(a[2]) - t1 + 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

官方思路

1. 思路1
   思路与算法
   （1）我们可以用栈来模拟函数调用的过程，栈顶的元素为当前正在执行函数：
   （2）当函数调用开始时，如果当前有函数正在运行，则当前正在运行函数应当停止，此时计算其的执行时间，然后将调用函数入栈。
   （3）当函数调用结束时，将栈顶元素弹出，并计算相应的执行时间，如果此时栈顶有被暂停的函数，则开始运行该函数。
   由于每一个函数都有一个对应的start 和end 日志，且当遇到一个end 日志时，栈顶元素一定为其对应的 start 日志。那么我们对于每一个函数记录它的函数标识符和上次开始运行的时间戳，此时我们只需要在每次函数暂停运行的时候来计算执行时间和开始运行的时候更新时间戳即可。

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        ans = [0] * n
        st = []
        for log in logs:
            idx, tp, timestamp = log.split(':')
            idx, timestamp = int(idx), int(timestamp)
            if tp[0] == 's':
                if st:
                    ans[st[-1][0]] += timestamp - st[-1][1]
                    st[-1][1] = timestamp
                st.append([idx, timestamp])
            else:
                i, t = st.pop()
                ans[i] += timestamp - t + 1
                if st:
                    st[-1][1] = timestamp + 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析
时间复杂度：O(n)，其中 n 为全部日志 logs 的数量，n 条日志信息对应总共 n 次入栈和出栈操作。
空间复杂度：O(n)，其中 n 为全部日志 logs 的数量，n 条日志信息对应n/2次入栈操作，最坏的情况下全部n/2条日志入栈后才会依次弹栈。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/exclusive-time-of-functions/solution/han-shu-de-du-zhan-shi-jian-by-leetcode-d54e2/

# A code block
foo = 'bar';
1
2

2. 思路2

# A code block
foo = 'bar';
1
2

3. 思路3

# A code block
foo = 'bar';
1
2