22 括号生成(2021-07-20)

22. 括号生成

链接:https://leetcode-cn.com/problems/generate-parentheses/

题目描述见链接内容。

思考

昨天做这道题,没思路,看了题解学习了

写代码一直没休息,写到眼睛疼想吐

图啥

解法1:成对匹配

把一对括号()看做一个从整体,当n === 1是,结果是[()]n === 2时,对[()]进行遍历,()有三个位置可以插入,插入的结果是()()(())()(),显然是有重复的结果,可以利用Set来去重:

var generateParenthesis = function (n) {
  if (n === 0) {
    return [];
  }

  if (n === 1) {
    return ['()'];
  }

  const set = new Set();

  for (const str of generateParenthesis(n - 1)) {
    for (let i = 0, len = str.length; i < len + 2; i++) {
      set.add(str.slice(0, i + 1) + '()' + str.slice(i + 1, len));
    }
  }

  return [...set];
};

解法2:递归

需要找到规律:

  • 当剩下的左括号和右括号数量相同时,下一个位置必须是左括号(如果是右括号,这个右括号就没人和它匹配了)
  • 当剩下的左括号数量小于右括号数量时,下一个位置可以是左括号也可以是右括号
  • 当剩下的左括号数量大于右括号数量时,无法再匹配成对

根据这个规律,进行递归

var generateParenthesis = function (n) {
  const res = [];
  generate('', n, n, res);
  return res;
};

function generate(str, left, right, res) {
  if (left === 0 && right === 0) {
    res.push(str);
    return;
  }

  if (left === right) {
    generate(str + '(', left - 1, right, res);
  } else if (left < right) {
    if (left > 0) {
      generate(str + '(', left - 1, right, res);
    }
    generate(str + ')', left, right - 1, res);
  }
}
上一篇:MySQL核心知识之DML数据操纵语言


下一篇:Go msgp序列化使用详解!比Json更快!面试时吊打面试官!