当前位置:网站首页>力扣 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;
}
}
边栏推荐
- Service
- 05 多线程与高并发 - ThreadPoolExecutor 源码解析
- ByteDance Interview Questions: Mirror Binary Tree 2020
- Gao Zelong, a famous digital collection expert and founder of the Digital Collection Conference, was interviewed by China Entrepreneur Magazine
- Silently start over, the first page is also a new page
- Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
- Zero shift of leetcode
- [HNOI2002]营业额统计
- INSTALL_RPATH and BUILD_RPATH problem in CMake
- The working principle of the transformer (illustration, schematic explanation, understand at a glance)
猜你喜欢
使用百度EasyDL实现智能垃圾箱
Built-in macros in C language (define log macros)
Error jinja2.exceptions.UndefinedError: 'form' is undefined
workbench 数据导出
Distributed id generator implementation
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS adds significant overhead and will be disab
Go lang1.18入门精炼教程——第一章:环境搭建
治疗消化性溃疡—Toronto Research Chemicals 甘氨酸铝
普罗米修斯原理及节点发布
CalBioreagents超全Id 蛋白兔单克隆抗体,助力科研
随机推荐
AD picture PCB tutorial 20 minutes clear label shop operation process, copper network
Simple Factory Pattern
P7阿里面试题2020.07 之滑动窗算法(阿里云面试)
CalBioreagents超全Id 蛋白兔单克隆抗体,助力科研
单例模式
Go lang1.18入门精炼教程——第一章:环境搭建
Web APIs BOM- 操作浏览器:本地存储
mongo+ycsb性能测试及线程数分析
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
Simple to use Lambda expressions
Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
像天才一样思考:如何培养自己的创造力?
一道很简答但是没答对的SQL题
集合内之部原理总结
cut命令的使用实例
阿里巴巴官方技术号
leetcode 之 零移位
The singleton pattern
细谈VR全景:数字营销时代的宠儿
分布式id 生成器实现