当前位置:网站首页>力扣 636. 函数的独占时间
力扣 636. 函数的独占时间
2022-08-09 06:39:00 【冷酷的摸鱼小将】
题目
有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 0 和 n-1 之间的唯一标识符。
函数调用 存储在一个 调用栈 上 :当一个函数调用开始时,它的标识符将会推入栈中。而当一个函数调用结束时,它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数 。每当一个函数开始或者结束时,将会记录一条日志,包括函数标识符、是开始还是结束、以及相应的时间戳。
给你一个由日志组成的列表 logs ,其中 logs[i] 表示第 i 条日志消息,该消息是一个按 “{function_id}:{“start” | “end”}:{timestamp}” 进行格式化的字符串。例如,“0:start:3” 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ;而 “12” 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意,函数可以 调用多次,可能存在递归调用 。
函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和,调用其他函数花费的时间不算该函数的独占时间。例如,如果一个函数被调用两次,一次调用执行 2 单位时间,另一次调用执行 1 单位时间,那么该函数的 独占时间 为 2 + 1 = 3 。
以数组形式返回每个函数的 独占时间 ,其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。
示例
输入:n = 2, logs = [“0:start:0”,“1:start:2”,“1: end:5”,“0: end:6”]
输出:[3,4]
解释:
函数 0 在时间戳 0 的起始开始执行,执行 2 个单位时间,于时间戳 1 的末尾结束执行。
函数 1 在时间戳 2 的起始开始执行,执行 4 个单位时间,于时间戳 5 的末尾结束执行。
函数 0 在时间戳 6 的开始恢复执行,执行 1 个单位时间。
所以函数 0 总共执行 2 + 1 = 3 个单位时间,函数 1 总共执行 4 个单位时间。
输入:n = 1, logs = [“0:start:0”,“0:start:2”,“0: end:5”,“0:start:6”,“0: end:6”,“0: end:7”]
输出:[8]
解释:
函数 0 在时间戳 0 的起始开始执行,执行 2 个单位时间,并递归调用它自身。
函数 0(递归调用)在时间戳 2 的起始开始执行,执行 4 个单位时间。
函数 0(初始调用)恢复执行,并立刻再次调用它自身。
函数 0(第二次递归调用)在时间戳 6 的起始开始执行,执行 1 个单位时间。
函数 0(初始调用)在时间戳 7 的起始恢复执行,执行 1 个单位时间。
所以函数 0 总共执行 2 + 4 + 1 + 1 = 8 个单位时间。
输入:n = 2, logs = [“0:start:0”,“0:start:2”,“0: end:5”,“1:start:6”,“1: end:6”,“0: end:7”]
输出:[7,1]
解释:
函数 0 在时间戳 0 的起始开始执行,执行 2 个单位时间,并递归调用它自身。
函数 0(递归调用)在时间戳 2 的起始开始执行,执行 4 个单位时间。
函数 0(初始调用)恢复执行,并立刻调用函数 1 。
函数 1在时间戳 6 的起始开始执行,执行 1 个单位时间,于时间戳 6 的末尾结束执行。
函数 0(初始调用)在时间戳 7 的起始恢复执行,执行 1 个单位时间,于时间戳 7 的末尾结束执行。
所以函数 0 总共执行 2 + 4 + 1 = 7 个单位时间,函数 1 总共执行 1 个单位时间。
输入:n = 2, logs = [“0:start:0”,“0:start:2”,“0: end:5”,“1:start:7”,“1: end:7”,“0: end:8”]
输出:[8,1]
输入:n = 1, logs = [“0:start:0”,“0: end:0”]
输出:[1]
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/exclusive-time-of-functions
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方法1:栈
Java实现
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
int var = 0;
for (String log : logs) {
String[] cur = log.split(":");
int idx = Integer.parseInt(cur[0]), time = Integer.parseInt(cur[2]);
if (cur[1].equals("start")) {
if (!stack.isEmpty()) {
res[stack.peek()] += time - var;
}
stack.push(idx);
var = time;
} else {
res[stack.pop()] += time - var + 1;
var = time + 1;
}
}
return res;
}
}
边栏推荐
- Quectel EC20 4G module dial related
- Integer 线程安全的
- 直接用的zip包 缺少很多依赖,pip没有,感觉用anaconda create一个环境会方便点
- The AD in the library of library file suffix. Intlib. Schlib. Pcblib difference
- 缓存技术使用
- 长沙学院2022暑假训练赛(一)六级阅读
- Singleton DCL (double check the lock) full han mode and the hungry
- 图论,二叉树,dfs,bfs,dp,最短路专题
- uniapp实现防抖搜索
- workbench 数据导出
猜你喜欢
随机推荐
默默重新开始,第一页也是新的一页
6 states of a thread
The water problem of leetcode
分布式id 生成器实现
ZIP压缩包文件删除密码的方法
Singleton DCL (double check the lock) full han mode and the hungry
Leetcode 70 stairs issues (Fibonacci number)
DDD 领域驱动设计
工控设备的系统如何进行加固
Error: flask: TypeError: 'function' object is not iterable
SIGINT,SIGKILL,SIGTERM信号区别,各类信号总结
如何操作数据库
物理层课后作业
TCP segment of a reassembled PDU
ByteDance Interview Questions: Mirror Binary Tree 2020
mysql 总结
io.lettuce.core。RedisCommandTimeoutException命令超时
Example of using the cut command
字节跳动面试题之镜像二叉树2020
推进产教融合 赋能教育创新发展 | 华云数据荣获“企业贡献奖”