关于java:LeetCode022括号生成

44次阅读

共计 1963 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：数字 n 代表生成括号的对数，请你设计一个函数，用于可能生成所有可能的并且无效的括号组合。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：穷举法

通过递归的形式获取所有可能的组合，而后判断每一种组合是否是无效的括号组合，如果是，增加到后果集中，最初返回合乎的后果汇合。

解法二：回溯法

也是通过递归的形式，然而能够依据曾经呈现过的左右括号的个数来判断下一个字符能够是左括号还是右括号，这样最初递归失去的都是无效的括号组合，效率较高。

import java.util.ArrayList;
import java.util.List;

public class LeetCode_022 {
    /**
     * 暴力破解法
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();
        generateAllPossibleResults(new char[2 * n], 0, result);
        return result;
    }

    /**
     * 递归办法：2*n 的字符数组，每一个字符都有 2 种可能，直到字符数组被填满，校验是否合乎
     *
     * @param current
     * @param pos
     * @param result
     */
    public static void generateAllPossibleResults(char[] current, int pos, List<String> result) {if (pos == current.length) {
            // 当字符数组被填充斥时，校验是否合乎
            if (valid(current)) {result.add(new String(current));
            }
        } else {
            // 递归
            current[pos] = '(';
            generateAllPossibleResults(current, pos + 1, result);
            current[pos] = ')';
            generateAllPossibleResults(current, pos + 1, result);
        }
    }

    /**
     * 判断是否符合条件
     *
     * @param current
     * @return
     */
    public static boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {if (c == '(') {++balance;} else {--balance;}
            if (balance < 0) {return false;}
        }
        return balance == 0;
    }

    static List<String> res = new ArrayList<>();

    /**
     * 办法二：回溯法
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis2(int n) {if (n <= 0) {return res;}
        getParenthesis("", n, n);
        return res;
    }

    private static void getParenthesis(String str, int left, int right) {if (left == 0 && right == 0) {res.add(str);
            return;
        }
        if (left == right) {
            // 残余左右括号数相等，下一个只能用左括号
            getParenthesis(str + "(", left - 1, right);
        } else if (left < right) {
            // 残余左括号小于右括号，下一个能够用左括号也能够用右括号
            if (left > 0) {getParenthesis(str + "(", left - 1, right);
            }
            getParenthesis(str + ")", left, right - 1);
        }
    }

    public static void main(String[] args) {System.out.println("===== 暴力破解法 =====");
        List<String> strings = generateParenthesis(4);
        for (String string : strings) {System.out.println(string);
        }

        System.out.println("===== 回溯法 =====");
        List<String> strings1 = generateParenthesis2(4);
        for (String s : strings1) {System.out.println(s);
        }
    }
}