【算法】剑指 Offer II 085. 生成匹配的括号|22. 括号生成|面试题 08.09. 括号(多语言实现)

简介: 正整数 n 代表生成括号的对数,请设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

剑指 Offer II 085. 生成匹配的括号|22. 括号生成|面试题 08.09. 括号

正整数 n 代表生成括号的对数,请设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

样例 1:

输入:
    n = 3
    
输出:
    ["((()))","(()())","(())()","()(())","()()()"]

样例 2:

输入:
    n = 1
    
输出:
    ["()"]

提示:

  • 1 <= n <= 8

分析

  • 首先想到的是全排列排列方式,然后再从中挑选满足括号规则的序列。每个字符只可能是 '(' 或者 ')' 两种选择,所以全排列的数量是 22n 个。真正有效的括号序列远远少于这个量。
  • 是否可以直接去穷举生成有效的括号序列呢?
  • 首先要判断什么样的序列是有效的括号序列?
  • 很显然,首先左右括号字符的数量应该相等。
  • 右括号一定是匹配前面某个左括号。
  • 所以只包含左右括号字符,并且从左往右看,右括号数始终小于等于左括号数,最终左右括号数相等的序列就是合理合法合规的括号序列了。

题解

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();

        this.dfs(n, ans, new char[n * 2], 0, 0);

        return ans;
    }

    private void dfs(int n, List<String> ans, char[] cs, int left, int right) {
        if (left == n && right == n) {
            ans.add(new String(cs));
            return;
        }

        if (left < n) {
            cs[left + right] = '(';
            dfs(n, ans, cs, left + 1, right);
        }
        if (right < left) {
            cs[left + right] = ')';
            dfs(n, ans, cs, left, right + 1);
        }
    }
}

c

#define MAX_SIZE 1430

void dfs(int n, int *returnSize, char **ans, char *cs, int left, int right) {
    if (left == n && right == n) {
        ans[(*returnSize)] = calloc((n * 2 + 1), sizeof(char));
        strcpy(ans[(*returnSize)], cs);
        ++(*returnSize);
        return;
    }

    if (left < n) {
        cs[left + right] = '(';
        dfs(n, returnSize, ans, cs, left + 1, right);
    }
    if (right < left) {
        cs[left + right] = ')';
        dfs(n, returnSize, ans, cs, left, right + 1);
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char **generateParenthesis(int n, int *returnSize) {
    *returnSize = 0;
    char **ans = malloc(MAX_SIZE * sizeof(char *));
    char *cs = calloc((n * 2 + 1), sizeof(char));
    dfs(n, returnSize, ans, cs, 0, 0);
    return ans;
}

c++

class Solution {
private:
    void dfs(int n, vector<string> &ans, string &buf, int left, int right) {
        if (left == n && right == n) {
            ans.push_back(buf);
            return;
        }

        if (left < n) {
            buf.push_back('(');
            dfs(n, ans, buf, left + 1, right);
            buf.pop_back();
        }
        if (right < left) {
            buf.push_back(')');
            dfs(n, ans, buf, left, right + 1);
            buf.pop_back();
        }
    }

public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string buf;
        dfs(n, ans, buf, 0, 0);
        return ans;
    }
};

python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        def dfs(s, left, right):
            if left == n and right == n:
                ans.append(''.join(s))
                return
            if left < n:
                s.append('(')
                dfs(s, left + 1, right)
                s.pop()
            if right < left:
                s.append(')')
                dfs(s, left, right + 1)
                s.pop()

        dfs([], 0, 0)
        return ans
        

go

func generateParenthesis(n int) []string {
    var ans []string

    var dfs func(cs []byte, left int, right int)
    dfs = func(cs []byte, left int, right int) {
        if left == n && right == n {
            ans = append(ans, string(cs))
            return
        }

        if left < n {
            cs[left+right] = '('
            dfs(cs, left+1, right)
        }
        if right < left {
            cs[left+right] = ')'
            dfs(cs, left, right+1)
        }
    }

    dfs(make([]byte, n*2), 0, 0)

    return ans
}

rust

impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut ans = Vec::new();

        fn dfs(n: usize, ans: &mut Vec<String>, buf: &mut String, left: usize, right: usize) {
            if left == n && right == n {
                ans.push(buf.clone());
                return;
            }
            if left < n {
                buf.push('(');
                dfs(n, ans, buf, left + 1, right);
                buf.pop();
            }
            if right < left {
                buf.push(')');
                dfs(n, ans, buf, left, right + 1);
                buf.pop();
            }
        }

        dfs(n as usize, &mut ans, &mut String::new(), 0, 0);

        ans
    }
}

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/IDBivT/

原题传送门:https://leetcode-cn.com/problems/generate-parentheses/

原题传送门:https://leetcode.cn/problems/bracket-lcci/


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

相关文章
|
4天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
4天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
8天前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
11天前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
10 0
|
12天前
|
算法 Java C语言
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
12 1
|
12天前
|
消息中间件 算法 Java
抖音面试:说说延迟任务的调度算法?
Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。 ## 1.延迟任务实现 在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码: ```java public class DelayTaskExample { public static void main(String[] args) { System.ou
22 5
抖音面试:说说延迟任务的调度算法?
|
15天前
|
算法 自然语言处理 Rust
【算法】16. 最接近的三数之和(多语言实现)
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。
|
26天前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
26天前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
26天前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈

热门文章

最新文章