最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • [路飞]_leetcode-636-函数的独占时间 - 掘金

    正文概述 掘金(前端_奔跑的蜗牛)   2021-11-25   450

    「这是我参与11月更文挑战的第20天,活动详情查看:2021最后一次更文挑战」

    [题目地址] [B站地址]

    有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于  0 和 n-1 之间的唯一标识符。

    函数调用 存储在一个 调用栈 上 :当一个函数调用开始时,它的标识符将会推入栈中。而当一个函数调用结束时,它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数 。每当一个函数开始或者结束时,将会记录一条日志,包括函数标识符、是开始还是结束、以及相应的时间戳。

    给你一个由日志组成的列表 logs ,其中 logs[i] 表示第 i 条日志消息,该消息是一个按 "{function_id}:{"start" | "end"}:{timestamp}" 进行格式化的字符串。例如,"0:start:3" 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ;而 "1:end:2" 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意,函数可以 调用多次,可能存在递归调用

    函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和,调用其他函数花费的时间不算该函数的独占时间。例如,如果一个函数被调用两次,一次调用执行 2 单位时间,另一次调用执行 1 单位时间,那么该函数的 独占时间 为 2 + 1 = 3 。

    以数组形式返回每个函数的 独占时间 ,其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。

    示例 1:

    [路飞]_leetcode-636-函数的独占时间 - 掘金

    输入: 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 个单位时间。 
    

    示例 2:

    输入: 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 个单位时间。
    

    示例 3:

    输入: 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 个单位时间。 
    

    示例 4:

    输入: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]
    输出: [8,1]
    

    示例 5:

    输入: n = 1, logs = ["0:start:0","0:end:0"]
    输出: [1]
    

    提示:

    • 1 <= n <= 100
    • 1 <= logs.length <= 500
    • 0 <= function_id < n
    • 0 <= timestamp <= 109
    • 两个开始事件不会在同一时间戳发生
    • 两个结束事件不会在同一时间戳发生
    • 每道函数都有一个对应 "start" 日志的 "end" 日志

    涉及到类似本题这种存在嵌套和相互关系的问题,我们可以用 来维护相互关系

    本题复杂的点就在于在一个函数开始和结束之间,可能存在其他函数的调用或者自身的递归调用

    我们假设每个函数的运行中没有其他函数的运行,则该函数的本次运行时间就是结束时间戳减去开始时间戳加一

    那如果函数的运行中有其他函数的运行,则该函数本次运行时间就是如上得到的时间减去中间其他函数的运行时间

    基于这个思考本题的题解如下:

    1. 创建长度为 n 的数组 res 维护返回值,一个栈维护函数的调用栈
    2. 遍历输入的 logs,如果当前日志为开始日志,将该函数的开始时间戳压入栈
    3. 如果当前日志为结束日志,则栈顶值记录的是它的开始时间戳,弹出栈顶值,将该函数的运行时间加上本次运行时间(结束时间戳-开始时间戳+1)
    4. 将栈中的其他函数的开始时间戳加上本次函数的运行时间,达到对应函数的运行时间减去该函数运行时间的目的
    5. 当输入 logs 遍历完成后,res 数组就记录了每个函数的独占时间,返回 res 即可

    代码如下:

    var exclusiveTime = function(n, logs) {
      // 初始化结果数组
      const res = Array(n).fill(0),
      // 函数调用栈
      stack = [];
      // 遍历日志
      for(let i = 0;i<logs.length;i++){
        let [ind,status,time] = logs[i].split(':');
        ind *= 1;
        time *= 1;
        // 如果为开始日志,将函数开始时间戳压入栈
        if(status==='start') stack.push(time)
        else {
          // 计算函数本次于行时间
          const num = time-stack.pop()+1
          res[ind] += num
          // 处理栈中函数的开始时间戳
          handleStack(num)
        }
      }
      return res;
      // 处理栈中函数开始时间戳,达到对应函数运行时间减去本次函数运行时间的目的
      function handleStack(num){
        for(let i =0;i<stack.length;i++){
          stack[i]+=num;
        }
      }
    };
    

    至此我们就完成了 leetcode-636-函数的独占时间

    如有任何问题或建议,欢迎留言讨论!


    起源地下载网 » [路飞]_leetcode-636-函数的独占时间 - 掘金

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元