题解 | #牛圈围栏问题#
牛圈围栏问题
https://www.nowcoder.com/practice/4e3bb97bbc2b4382a745abe953f44aee
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return string字符串一维数组 */ public static ArrayList<String> strings = new ArrayList<>(); public String[] generateParenthesis (int n) { // write code here search(0,0,n,new StringBuffer()); System.out.println(strings); String[] string_arr = new String[strings.size()]; for(int i=0;i<string_arr.length;i++){ string_arr[i]= strings.get(i); } return string_arr; } public void search(int left_cur,int right_cur,int n,StringBuffer stringBuffer){ if(right_cur > left_cur|| left_cur>n){ return; } if(left_cur==n && right_cur==n){ strings.add(stringBuffer.toString()); return; } stringBuffer.append('('); search(left_cur+1,right_cur,n,stringBuffer); stringBuffer.deleteCharAt(stringBuffer.toString().length()-1); stringBuffer.append(')'); search(left_cur,right_cur+1,n,stringBuffer); stringBuffer.deleteCharAt(stringBuffer.toString().length()-1); } }
本题的知识点考察的是二叉树的建立,可以将题目理解成一棵二叉树,每个分支节点的左节点为‘(’,分支节点的右节点为‘)’,结束条件是路径上的左括号或者有括号个数等于n,而且树延伸必须满足‘(’数目大于等于‘)’个数