陕西 网站建设 陕ICP网站 栏目

陕西 网站建设 陕ICP,网站 栏目,点击关注进入公众号,抖音代运营计划书题目#xff1a; 数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1#xff1a;输入#xff1a;n 3 输出#xff1a;[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]示例 2#xff1a;…题目数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。示例 1输入n 3输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]示例 2输入n 1输出[“()”]解析这道题又是一道典型的回溯算法题重点在于递归的两个条件终止条件当左右括号都用了 n 个时得到一个有效组合选择策略只要左括号还有剩余就可以添加左括号只有当已添加的右括号数量小于左括号数量时才能添加右括号具体代码/** * 生成所有有效的括号组合 * param {number} n - 括号的对数 * return {string[]} - 所有有效的括号组合 */vargenerateParenthesisfunction(n){// 1. 初始化结果数组用于存储所有有效的括号组合letres[]// 2. 当前正在构建的括号字符串初始为空lettemp// 3. 开始深度优先搜索DFS从左右括号数量都为0开始dfs(n,0,0,res,temp)// 4. 返回所有生成的括号组合returnres};/** * 深度优先搜索函数通过回溯生成所有有效的括号组合 * param {number} n - 括号的对数 * param {number} left - 当前已使用的左括号数量 * param {number} right - 当前已使用的右括号数量 * param {string[]} res - 存储结果的数组 * param {string} temp - 当前正在构建的括号字符串 */functiondfs(n,left,right,res,temp){// 5. 终止条件当左右括号数量都达到n时说明构建完成if(leftnrightn){// 将当前有效的括号组合添加到结果数组中res.push(temp)// 返回结束当前递归分支return}// 6. 选择1添加左括号 (// 条件左括号数量还没有达到nif(leftn){// 6.1 做出选择在当前字符串末尾添加左括号temp(// 6.2 递归探索左括号数量加1继续构建dfs(n,left1,right,res,temp)// 6.3 撤销选择回溯删除刚刚添加的左括号// 注意slice(0, -1)返回新字符串所以需要重新赋值temptemp.slice(0,-1)}// 7. 选择2添加右括号 )// 条件已使用的右括号数量小于左括号数量// 这个条件是保证括号有效性的关键在任何位置右括号不能超过左括号if(rightleft){// 7.1 做出选择在当前字符串末尾添加右括号temp)// 7.2 递归探索右括号数量加1继续构建dfs(n,left,right1,res,temp)// 7.3 撤销选择回溯删除刚刚添加的右括号temptemp.slice(0,-1)}// 8. 函数结束返回到上一层递归// 注意这里没有显式的返回值通过修改res数组和temp字符串来传递结果}