寒光博客

[CC150] 904 "()"括号的全部有效组合
题目描述 请设计一种算法,打印n对括号的全部有效组合(即左右括号正确配对). 输入:3 输出:()()(),((...
扫描右侧二维码阅读全文
01
2019/08

[CC150] 904 "()"括号的全部有效组合

题目描述

请设计一种算法,打印n对括号的全部有效组合(即左右括号正确配对).

输入:3
输出:()()(),(()()),()(()),(())(),((()))

分析

每个元素的变化分析就是 ()加到左、右、外 这三种当然 我们还得去重

  • 重点是推出 1>2>3...n-1>n的关系

逐步生成之递归解法

    public static Set<String> parenthesis(int n) {//圆括号
        Set<String> s_n = new HashSet<>();//去重
        if (n == 1) {
            s_n.add("()");
            return s_n;
        }
        Set<String> s_n_1 = parenthesis(n - 1);
        for (String eOfN_1 : s_n_1) {
            s_n.add("()" + eOfN_1);
            s_n.add(eOfN_1 + "()");
            s_n.add("(" + eOfN_1 + ")");
        }
        return s_n;
    }

逐步生成之迭代解法

    public static Set<String> parenthesis1(int n) {
        Set<String> s_n = new HashSet<>();//保存上次迭代的状态
        s_n.add("()");
        if (n == 1)//特判1
            return s_n;

        for (int i = 2; i <= n; i++) {//等于不要丢了
            Set<String> s_new = new HashSet<>();
            for (String eOFn_new : s_n) {//遍历上次生成的
                s_new.add(eOFn_new+"()");
                s_new.add("("+eOFn_new+")");
                s_new.add("()"+eOFn_new);
            }
            s_n=s_new;//把新的生成替换过去 【旧的清除】
        }
        return s_n;
    }

GitHub

本文作者:Author:     文章标题:[CC150] 904 "()"括号的全部有效组合
本文地址:https://dxoca.cn/Algorithm/208.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 21st, 2019 at 09:18 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment