题解 | #牛圈围栏问题# 回溯

牛圈围栏问题

https://www.nowcoder.com/practice/4e3bb97bbc2b4382a745abe953f44aee

知识点

回溯

思路

题意其实是问你,一个括号对数为n的全部合法字符串。

可以二进制枚举或者回溯来解决,二进制枚举的时间复杂度是O(n\times2^n),回溯的复杂度是O(2^n)

因此考虑用回溯来做,考虑字符串的从左往右的每个位置填左括号还是右括号,由于答案要求左括号优先,我们先考虑左括号,后考虑右括号。

注意必须是合法字符串,任何时候左括号的数量不少于右括号。

AC Code(c++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        vector<string> res;

        function<void(string&, int, int)> dfs = [&](string& path, int l, int r) {
            if (l > r) return;
            if (l == 0 and r == 0) {
                res.push_back(path);
                return;
            }
            if (l > 0) {
                path.push_back('(');
                dfs(path, l - 1, r);
                path.pop_back();
            }
            if (r > 0) {
                path.push_back(')');
                dfs(path, l, r - 1);
                path.pop_back();
            }
        };
        string s;
        dfs(s, n, n);
        return res;
    }
};

全部评论

相关推荐

uu们,拒offer时hr很生气怎么办我哭死
爱睡觉的冰箱哥:人家回收你的offer,或者oc后没给你发offer的时候可不会愧疚你,所以你拒了也没必要愧疚他。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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