leetcode636-函数的独占时间

原题

给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。

每个函数都有一个唯一的 Id,从 0n-1,函数可能会递归调用或者被其他函数调用。

日志是具有以下格式的字符串:function_id:start_or_end:timestamp。例如:"0:start:0" 表示函数 0 从 0 时刻开始运行。"0:end:0" 表示函数 0 在 0 时刻结束。

函数的独占时间定义是在该方法中花费的时间,调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。

示例 1:

输入:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"] 输出:[3, 4] 说明:
函数 0 在时刻 0 开始,在执行了 2个时间单位结束于时刻 1。
现在函数 0 调用函数 1,函数 1 在时刻 2 开始,执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行,并在时刻 6 结束运行,从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位,函数 1 总共执行了 4 个时间单位。

说明:

  1. 输入的日志会根据时间戳排序,而不是根据日志Id排序。
  2. 你的输出会根据函数Id排序,也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。
  3. 两个函数不会在同时开始或结束。
  4. 函数允许被递归调用,直到运行结束。
  5. 1 <= n <= 100

解法

思想

函数的调用天生符合栈的思想

代码

我一开始使用了辅助类记录足够的信息。

class FunctionTime{
    String function_id;
    String timestamp;
    FunctionTime(String function_id,String timestamp){
        this.function_id = function_id;
        this.timestamp = timestamp;
    }
}

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        Stack<FunctionTime> stack = new Stack<>();
        for(String i:logs){
            String[] info = i.split(":");
            if(!stack.isEmpty()&&info[1].equals("end")){
                FunctionTime func = stack.pop();
                ans[Integer.valueOf(func.function_id)]+=(Integer.valueOf(info[2])-Integer.valueOf(func.timestamp)+1);
                //新方法结束时把原方法开始的时间设为当前时间+1。
                if(!stack.isEmpty()) 
                    stack.peek().timestamp = String.valueOf(Integer.valueOf(info[2])+1);
            }else{
                if(!stack.isEmpty()) {
                    //新方法开始时给上一个方法加上时间。
                    FunctionTime peek = stack.peek();
                    ans[Integer.valueOf(peek.function_id)]+=(Integer.valueOf(info[2])-Integer.valueOf(peek.timestamp));
                }
                FunctionTime func = new FunctionTime(info[0],info[2]);
                stack.push(func);
            }
        }
        return ans;
    }
}

然后发现可以简化。

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        Stack<Integer> stack = new Stack();
        int curTime = 0;
        for(String i:logs){
            String[] info = i.split(":");
            int id = Integer.valueOf(info[0]);
            int timestamp = Integer.valueOf(info[2]);
            if(info[1].equals("start")){
                if(!stack.isEmpty()){
                    ans[stack.peek()] += timestamp - curTime;
                }
                stack.push(id);
                curTime = timestamp;
            }else{
                timestamp++;
                ans[stack.pop()] += timestamp - curTime; 
            }
            curTime = timestamp;
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode636-%e5%87%bd%e6%95%b0%e7%9a%84%e7%8b%ac%e5%8d%a0%e6%97%b6%e9%97%b4/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月2日 02:16
下一篇 2020年2月2日

相关推荐

  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0140
  • leetcode430-扁平化多级双向链表

    原题 您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示…

    2019年12月17日
    090
  • leetcode34--在排序数组中查找元素的第一个和最后一个位置

    原题 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数…

    算法 2020年1月3日
    0140
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0180
  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0120
  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    080
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • leetcode53-最大子序和

    原题 原题 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4],…

    算法 2020年2月20日
    0120
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01540

发表回复

登录后才能评论