Commit82a1e5f

committed

Added Number of Ways to Reorder Array to Get Same BST.java

1 parent5ff5951 commit82a1e5fCopy full SHA for 82a1e5f

File tree

+38

-0

lines changed

+38

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,38 @@`
	`1`	`+classSolution {`
	`2`	`+`
	`3`	`+privatestaticfinallongMOD =1000_000_007;`
	`4`	`+`
	`5`	`+publicintnumOfWays(int[]nums) {`
	`6`	`+intn =nums.length;`
	`7`	`+long[][]dp =newlong[n][n];`
	`8`	`+for (inti =0;i <n;i++) {`
	`9`	`+dp[i][0] =dp[i][i] =1;`
	`10`	`+ }`
	`11`	`+for (inti =2;i <n;i++) {`
	`12`	`+for (intj =1;j <i;j++) {`
	`13`	`+dp[i][j] = (dp[i -1][j -1] +dp[i -1][j]) %MOD;`
	`14`	`+ }`
	`15`	`+ }`
	`16`	`+List<Integer>list =Arrays.stream(nums).boxed().collect(Collectors.toList());`
	`17`	`+return (int) ((dfs(list,dp) -1) %MOD);`
	`18`	`+ }`
	`19`	`+`
	`20`	`+privatelongdfs(List<Integer>nums,long[][]dp) {`
	`21`	`+intn =nums.size();`
	`22`	`+if (n <3) {`
	`23`	`+return1;`
	`24`	`+ }`
	`25`	`+List<Integer>leftNodes =newArrayList<>();`
	`26`	`+List<Integer>rightNodes =newArrayList<>();`
	`27`	`+for (inti =1;i <n;i++) {`
	`28`	`+if (nums.get(i) <nums.get(0)) {`
	`29`	`+leftNodes.add(nums.get(i));`
	`30`	`+ }else {`
	`31`	`+rightNodes.add(nums.get(i));`
	`32`	`+ }`
	`33`	`+ }`
	`34`	`+longleftCount =dfs(leftNodes,dp) %MOD;`
	`35`	`+longrightCount =dfs(rightNodes,dp) %MOD;`
	`36`	`+return (((leftCount rightCount) %MOD) dp[n -1][leftNodes.size()]) %MOD;`
	`37`	`+ }`
	`38`	`+}`

Comments

(0)