当前位置:网站首页>力扣 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;
}
}
边栏推荐
- mysql 总结
- longest substring without repeating characters
- 变压器的工作原理(图解,原理图讲解,一看就懂)
- CalBioreagents超全Id 蛋白兔单克隆抗体,助力科研
- 报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS adds significant overhead and will be disab
- 细谈VR全景:数字营销时代的宠儿
- Unity C# 委托——事件,Action,Func的作用和区别
- 6 states of a thread
- AD的library中 库文件后缀有.intlib .schlib .pcblib 的区别
- 一道很简答但是没答对的SQL题
猜你喜欢
6 states of a thread
IQ Products CMV Brite Turbo试剂盒的原理
Integer 线程安全的
CMake中INSTALL_RPATH与BUILD_RPATH问题
mongo+ycsb性能测试及线程数分析
中英文说明书丨TRC D-阿卓糖(D-Altrose)
Xilinx Zynq ZynqMP DNA
2022-08-08: Given an array arr, it represents the height of the missiles that will appear in order from morning to night.When the cannon shoots missiles, once the cannon is set to shoot at a certain h
分布式id 生成器实现
Search 1688 product interface by image (item_search_img-search 1688 product by image (Politao interface) code docking tutorial
随机推荐
Fragments
flask创建数据库失败未报错
XxlJobConfig分布式定时器任务管理XxlJob配置类,替代
电学知识的疑问
阿里巴巴官方技术号
为什么以太网无法接收大于1500字节的数据包?
先序遍历,中序遍历,后序遍历,层序遍历
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
常用Oracle命令
el-table缓存数据
使用百度EasyDL实现智能垃圾箱
Inception V3 闭眼检测
C语言实现顺序栈和链队列
Simple to use Lambda expressions
运算放大器(OPA)超详细参数讲解-运放---以及8个型号的运算放大器分析对比
Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
线程池总结
简单使用Lambda表达式
TCP segment of a reassembled PDU
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道