每日一题(2022-01-14):括号生成

每日一题(2022-01-14):括号生成

来源:力扣
难度:中等
题目:22. 括号生成

题目详情

原题截图.png

题解思路

第一反应是应该有比较巧妙的做法,想来想去写了个递归,结果却出错了,直到看过题解评论区一位与我思路相仿的道友才恍然大悟,于是优化得到了一个C++翻版代码;解题思路如下:

  • 使用递归分别对括号字符串的每一位进行生成,递归时记录剩余左括号和右括号的数量;
  • 如果二者剩余量均为0,那么此时得到的是最终结果字符串,直接push进数组就好了;
  • 如果二者数量相等,那么下一位生成的必为左括号(自己写的时候就是忽略了这点导致失之毫厘谬以千里);
  • 剩下的情况只有剩余左括号数量小于右括号的情况了(左括号剩余量多于右括号的情况在这种处理逻辑下不存在),这种情况下下一位既有可能是左括号,也有可能是右括号,只需要分别生成就行了;

官方题解的第一种思路竟然是暴力,回头读读题目倒也说得通,毕竟条件中限制了括号对数的范围为1~8,属于是可以早下班的题目了……

代码结果

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        Process("", n, n);
        return vecResult;
    }

private:
    vector<string> vecResult;
    void Process(string str, int numRemainLeft, int numRemainRight)
    {
        if (numRemainLeft == 0 && numRemainRight == 0)
        {
            vecResult.push_back(str);
            return;
        }

        if (numRemainLeft == numRemainRight)
            Process(str + "(", numRemainLeft - 1, numRemainRight);
        else
        {
            if (numRemainLeft > 0) 
                Process(str + "(", numRemainLeft - 1, numRemainRight);
            Process(str + ")", numRemainLeft, numRemainRight - 1);
        }
    }
};

运行结果.png