题解 | 括号区间匹配

括号区间匹配

https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  思路来自昨天写的【染色问题】(https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2Fpractice%2F512619bee5874e85bd2812a0c9066125%3FchannelPut%3Dw25springcamp)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*int finans = 0; 失败于“([([])]”
string s;
int rfind (string& ss, char c, int index){
  for (; index >= 0; index--){
    if (ss[index] == c) break;
  }
  return index;
}
void solve(int l, int r){
  if (l > r) return;
  if (s[l] == ')') {
    finans++;
    solve(l + 1, r);
  }
  else if (s[l] == ']'){
    finans++;
    solve(l + 1, r);
  }
  else if (s[l] == '('){
    int next = rfind(s, ')', r);
    if (next < l || next == -1) {
      finans++;
      solve(l + 1, r);
    }
    else{
      solve(l + 1, next - 1);
      solve(next + 1, r);
    }
  }
  else{
    int next = rfind(s, ']', r);
    if (next < l || next == -1){
      finans++;
      solve(l + 1, r);
    }
    else{
      solve(l + 1, next - 1);
      solve(next + 1, r);
    }
  }
}
int main() {
  cin >> s;
  size_t size = s.size();
  solve(0, size - 1);
  cout << finans;
}
// 64 位输出请用 printf("%lld")*/
char dp[110][110]{ 0 };//----------最多只有100个括号,dp【i】【j】表示索引i~j区间中需要添加的最少括号
int main() {
  string s;
  cin >> s;
  size_t size = s.size();
  for (int len = 1; len <= size; len++) {//---------从小到大枚举长度
    for (int i = 0; i < size; i++) {
      int j = i + len - 1;
      if (j >= size) break;
      if (i == j) dp[i][j] = 1;//----------只有一个括号必须要补
      else {
        dp[i][j] = 110;
        if (s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']') {//----如果匹配
          if (i == j - 1) dp[i][j] = 0;//--------修正一个括号时的‘1’
          else dp[i][j] = dp[i + 1][j - 1];
        }
        for (int k = i; k < j; k++) dp[i][j] = min(static_cast<int>(dp[i][j]), static_cast<int>(dp[i][k] + dp[k + 1][j]));//----------这里注意就算匹配成功也要枚举避免样例“[])[[)]”的答案从3变成5
      }
    }
  }
  cout << static_cast<int>(dp[0][size - 1]);//----------记得类型转换
  return 0;
}

#写题解领奖励##牛客春招刷题训练营#
全部评论

相关推荐

07-25 13:42
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务