当前位置:网站首页>LeetCode每日一题(636. Exclusive Time of Functions)
LeetCode每日一题(636. Exclusive Time of Functions)
2022-07-07 12:29:00 【wangjun861205】
On a single-threaded CPU, we execute a program containing n functions. Each function has a unique ID between 0 and n-1.
Function calls are stored in a call stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed. Each time a function starts or ends, we write a log with the ID, whether it started or ended, and the timestamp.
You are given a list logs, where logs[i] represents the ith log message formatted as a string “{function_id}:{“start” | “end”}:{timestamp}”. For example, “0:start:3” means a function call with function ID 0 started at the beginning of timestamp 3, and “12” means a function call with function ID 1 ended at the end of timestamp 2. Note that a function can be called multiple times, possibly recursively.
A function’s exclusive time is the sum of execution times for all function calls in the program. For example, if a function is called twice, one call executing for 2 time units and another call executing for 1 time unit, the exclusive time is 2 + 1 = 3.
Return the exclusive time of each function in an array, where the value at the ith index represents the exclusive time for the function with ID i.
Example 1:
Input: n = 2, logs = [“0:start:0”,“1:start:2”,“15”,“06”]
Output: [3,4]
Explanation:
Function 0 starts at the beginning of time 0, then it executes 2 for units of time and reaches the end of time 1.
Function 1 starts at the beginning of time 2, executes for 4 units of time, and ends at the end of time 5.
Function 0 resumes execution at the beginning of time 6 and executes for 1 unit of time.
So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.
Example 2:
Input: n = 1, logs = [“0:start:0”,“0:start:2”,“05”,“0:start:6”,“06”,“07”]
Output: [8]
Explanation:
Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.
Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.
Function 0 (initial call) resumes execution then immediately calls itself again.
Function 0 (2nd recursive call) starts at the beginning of time 6 and executes for 1 unit of time.
Function 0 (initial call) resumes execution at the beginning of time 7 and executes for 1 unit of time.
So function 0 spends 2 + 4 + 1 + 1 = 8 units of total time executing.
Example 3:
Input: n = 2, logs = [“0:start:0”,“0:start:2”,“05”,“1:start:6”,“16”,“07”]
Output: [7,1]
Explanation:
Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.
Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.
Function 0 (initial call) resumes execution then immediately calls function 1.
Function 1 starts at the beginning of time 6, executes 1 unit of time, and ends at the end of time 6.
Function 0 resumes execution at the beginning of time 6 and executes for 2 units of time.
So function 0 spends 2 + 4 + 1 = 7 units of total time executing, and function 1 spends 1 unit of total time executing.
Constraints:
- 1 <= n <= 100
- 1 <= logs.length <= 500
- 0 <= function_id < n
- 0 <= timestamp <= 109
- No two start events will happen at the same timestamp.
- No two end events will happen at the same timestamp.
- Each function has an “end” log for each “start” log.
创建一个栈保存所有的 start, 每遇到一个 start 则结算从前一个 start 到当前 start 的运行时间, 这个时间加到前一个 start 的 function 的运行时间上, 因为从这一刻起, 前一个 start 的 function 等于不再执行了。如果遇到 end 则直接结算当前 function 的运行时间(当前 end 时间-栈顶 start 时间), 结算完还需要修改前一个 start 的时间,因为从当前 end 的时间起, 前一个 start 的又开始运行了。注意检查栈为空的情况, 还有,这一切的前提是建立在 logs 是按时间轴来进行记录的条件下的
impl Solution {
pub fn exclusive_time(n: i32, logs: Vec<String>) -> Vec<i32> {
let mut ans = vec![0; n as usize];
let mut stack: Vec<(i32, i32)> = Vec::new();
for log in logs {
let group: Vec<String> = log.split(":").map(|v| v.to_owned()).collect();
let num = group[0].parse::<i32>().unwrap();
let typ = group[1].clone();
let t = group[2].parse::<i32>().unwrap();
if typ == "start" {
if let Some(prev) = stack.pop() {
ans[prev.0 as usize] += t - prev.1;
stack.push(prev);
}
stack.push((num, t));
continue;
}
let prev = stack.pop().unwrap();
ans[prev.0 as usize] += t - prev.1 + 1;
if let Some(mut p) = stack.pop() {
p.1 = t + 1;
stack.push(p);
}
}
ans
}
}
边栏推荐
- The longest ascending subsequence model acwing 1014 Mountaineering
- 请问,PTS对数据库压测有好方案么?
- mysql ”Invalid use of null value“ 解决方法
- wpf dataGrid 实现单行某个数据变化 ui 界面随之响应
- Mysql怎样控制replace替换的次数?
- IP address home location query
- 使用day.js让时间 (显示为几分钟前 几小时前 几天前 几个月前 )
- 請問,在使用flink sql sink數據到kafka的時候出現執行成功,但是kafka裏面沒有數
- bashrc与profile
- C # use TCP protocol to establish connection
猜你喜欢
带你掌握三层架构(建议收藏)
The longest ascending subsequence model acwing 1014 Mountaineering
AutoCAD - how to input angle dimensions and CAD diameter symbols greater than 180 degrees?
最长上升子序列模型 AcWing 482. 合唱队形
LeetCode 648. 单词替换
Supply chain supply and demand estimation - [time series]
libSGM的horizontal_path_aggregation程序解读
Transferring files between VMware and host
Selenium库
Horizontal of libsgm_ path_ Interpretation of aggregation program
随机推荐
[untitled]
Laravel5 call to undefined function OpenSSL cipher IV length() error php7 failed to open OpenSSL extension
最长上升子序列模型 AcWing 1012. 友好城市
mysql ”Invalid use of null value“ 解决方法
[fortress machine] what is the difference between cloud fortress machine and ordinary fortress machine?
When FC connects to the database, do you have to use a custom domain name to access it outside?
Environment configuration
Arm cortex-a9, mcimx6u7cvm08ad processor application
Clickhouse (03) how to install and deploy Clickhouse
How to check the ram and ROM usage of MCU through Keil
高等数学---第八章多元函数微分学1
C # use TCP protocol to establish connection
mysql导入文件出现Data truncated for column ‘xxx’ at row 1的原因
Selenium库
OAuth 2.0 + JWT 保护API安全
VSCode 配置使用 PyLint 语法检查器
请问,在使用flink sql sink数据到kafka的时候出现执行成功,但是kafka里面没有数
Is the spare money in your hand better to fry stocks or buy financial products?
请问指南针股票软件可靠吗?交易股票安全吗?
How does MySQL control the number of replace?