网站建设公司 成都,做网站上加入模块怎么加入,观音桥网站建设网站建设,受欢迎的网站建设教程一、问题描述#xff1a; 数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1#xff1a; 输入#xff1a;n 3 输出#xff1a;[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2 数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 示例 1 输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2 输入n 1 输出[“()”] 二、解题思路
①创建一个空的列表ans用于存储结果然后调用backtrack方法进行回溯。 ②backtrack方法是核心通过递归的方式生成所有可能的括号组合。在递归的过程中使用两个计数器open和close来记录当前已经放置的左括号和右括号的数量以及参数max来表示所需的括号对数。 ③在每一步递归中根据以下两个条件判断 如果左括号的数量open小于max则可以放置一个左括号并递归调用backtrack方法。 如果右括号的数量close小于左括号的数量open则可以放置一个右括号并递归调用backtrack方法。 ④当括号组合的长度达到max * 2时将当前组合添加到结果列表中。
三、代码示例
class Solution {// 生成有效括号组合的方法public ListString generateParenthesis(int n) {ListString ans new ArrayListString(); // 存储结果的列表backtrack(ans, new StringBuilder(), 0, 0, n); // 调用回溯方法return ans; // 返回结果列表}// 回溯方法用于生成括号组合public void backtrack(ListString ans, StringBuilder cur, int open, int close, int max) {// 当前组合长度等于2*n时将组合加入结果列表if (cur.length() max * 2) {ans.add(cur.toString());return;}// 如果左括号数量小于n则可以添加左括号if (open max) {cur.append(();backtrack(ans, cur, open 1, close, max); // 递归调用cur.deleteCharAt(cur.length() - 1); // 回溯删除最后一个字符}// 如果右括号数量小于左括号数量则可以添加右括号if (close open) {cur.append());backtrack(ans, cur, open, close 1, max); // 递归调用cur.deleteCharAt(cur.length() - 1); // 回溯删除最后一个字符}}
}
时间复杂度分析在递归过程中每个位置有两种选择即放置左括号或右括号因此总的递归次数为2的2n次方。 在每次递归调用中都要执行一次字符串拼接和删除操作时间复杂度为O(1)。 综上所述总的时间复杂度为O(2^2n)。
