最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 括号有效配对一箭三连(三) | 刷题打卡

    正文概述 掘金(ClyingDeng)   2021-04-15   89

    一、题目描述:

    1) 任何一个左括号都能找到和其正确配对的右括号
    2) 任何一个右括号都能找到和其正确配对的左括号
    返回一个括号字符串中,最长的括号有效子串长度

    示例:

    示例 1:

    输入:(()))
    输出:4

    示例 2:

    输入:()(()))
    输出:6

    示例 3:

    输入:)()())
    输出:4

    二、思路分析:

    当问到最长有多少时,可以考虑使用动态规划去实现。定义一个辅助数组dp,用于记录字符串当前字符最大有效括号长度。

    遍历字符串

    1、当遇到'('时,最长有效字符串长度为0;

    2、当遇到')'时,就需要看前面一个dp的值
    如果i-1最长有效长度为0

    • i-2前面没有字符,那么i位置的有效长度就为2;
    • i-2前面还有字符,有效长度就为2 + dp[i-dp[i-1]-1]。

    如果i-1最长有效长度为不为0

    • 就要追溯到i-1位置最长有效长度的前一位,判断该位是不是可以和当前匹配,如果可以就需要加上dp[i-dp[i-1]-1],即2+ dp[i-dp[i-1]-1] + dp[i-1]。(例:s='(()())', s[5]可以和s[0]匹配,有效长度为2 + 0 + 4 = 6)

    总之,抽象起来就是:看第i-1个有效字符串长度是否等于'(',等于就需要看第i-1个有效字符串长度的前一位,前一位存在就需要加上,不存在就不需要加。 例: s='()()))' 括号有效配对一箭三连(三) | 刷题打卡

    例: s=')(()())' 括号有效配对一箭三连(三) | 刷题打卡

    三、AC 代码:

    function maxLength(s) {
      if (s == null || s.length < 2) return 0
      let dp = new Array(s.length).fill(0)
      let max = 0
      for (let i = 0; i < s.length; i++) {
        if (s[i] === ')') {
          let pre = i - dp[i - 1] - 1
          if (s[pre] === '(' && pre >= 0) {
            dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0)
          }
        }
        max = Math.max(max, dp[i])
      }
      console.log(dp)
      return max
    }
    

    四、总结:

    遇到最值问题,将问题抽象成以什么什么开头或结尾,求其i-1位置的值。再考虑包的含情况及关系等式。


    起源地 » 括号有效配对一箭三连(三) | 刷题打卡

    常见问题FAQ

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

    发表评论

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

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

    联系作者

    请选择支付方式

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