阅读 80

LeetCode-022-括号生成

括号生成

题目描述:数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/ge…
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:穷举法

通过递归的方式获取所有可能的组合,然后判断每一种组合是否是有效的括号组合,如果是,添加到结果集中,最后返回符合的结果集合。

解法二:回溯法

也是通过递归的方式,但是可以根据已经出现过的左右括号的个数来判断下一个字符可以是左括号还是右括号,这样最后递归得到的都是有效的括号组合,效率较高。

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);         }     } } 复制代码

【每日寄语】 一万个美丽的未来,抵不上一个温暖的现在。


作者:雄狮虎豹
链接:https://juejin.cn/post/7018327687479427079


文章分类
后端
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐