当前位置:网站首页>Leetcode one question per day (636. exclusive time of functions)
Leetcode one question per day (636. exclusive time of functions)
2022-07-07 14:27: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.
Create a stack to hold all start, Every time I meet one start Then settle the previous start To the current start Running time of , This time is added to the previous start Of function On the running time , Because from this moment on , Previous start Of function It's no longer implemented . If you encounter end Then directly settle the current function Running time of ( At present end Time - To the top of the stack start Time ), After settlement, you need to modify the previous start Time for , Because from now on end From the time of , Previous start Of is running again . Check that the stack is empty , also , The premise of all this is based on logs It is recorded according to the time axis
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
}
}
边栏推荐
猜你喜欢
手把手教会:XML建模
VSCode 配置使用 PyLint 语法检查器
用例图
Wired network IP address of VMware shared host
Parsing of XML files
Reverse non return to zero code, Manchester code and differential Manchester code of common digital signal coding
多商戶商城系統功能拆解01講-產品架構
Pert diagram (engineering network diagram)
Data flow diagram, data dictionary
Substance painter notes: settings for multi display and multi-resolution displays
随机推荐
[network security] SQL injection syntax summary
搜索引擎接口
Wired network IP address of VMware shared host
Analysis of arouter
First choice for stock account opening, lowest Commission for stock trading account opening, is online account opening safe
bashrc与profile
Mrs offline data analysis: process OBS data through Flink job
Navigation - are you sure you want to take a look at such an easy-to-use navigation framework?
通过 iValueConverter 给datagrid 的背景颜色 动态赋值
AutoCAD - how to input angle dimensions and CAD diameter symbols greater than 180 degrees?
【网络安全】sql注入语法汇总
Oracle Linux 9.0 officially released
Excuse me, when using Flink SQL sink data to Kafka, the execution is successful, but there is no number in Kafka
Substance Painter笔记:多显示器且多分辨率显示器时的设置
oracle 非自动提交解决
Hands on Teaching: XML modeling
Introduction to sakt method
LeetCode 648. 单词替换
VSCode 配置使用 PyLint 语法检查器
WPF DataGrid realizes the UI interface to respond to a data change in a single line