Commit8bf2e2a

committed

permutation 2

1 parenta8282f9 commit8bf2e2aCopy full SHA for 8bf2e2a

File tree

+47

-2

lines changed

+47

-2

lines changed

Lines changed: 2 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -13,7 +13,7 @@ public static void main(String[] strs) {`
`13`	`13`
`14`	`14`	`permute(num);`
`15`	`15`	`System.out`
`16`		`- .println("Computing time withArrayDeque used as Queue/Deque: "`
	`16`	`+ .println("Computing time withHASHMAP: "`
`17`	`17`	`+timer1.elapsedTime() +" millisec.");`
`18`	`18`
`19`	`19`	`System.out.printf("Test size:%d\n",num.length);`
`@@ -22,7 +22,7 @@ public static void main(String[] strs) {`
`22`	`22`
`23`	`23`	`permute2(num);`
`24`	`24`	`System.out`
`25`		`- .println("Computing time withArrayDeque used as Queue/Deque: "`
	`25`	`+ .println("Computing time withlist: "`
`26`	`26`	`+timer2.elapsedTime() +" millisec.");`
`27`	`27`	`}`
`28`	`28`

Lines changed: 45 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,45 @@`
	`1`	`+packageAlgorithms.permutation;`
	`2`	`+importjava.util.ArrayList;`
	`3`	`+importjava.util.Arrays;`
	`4`	`+importjava.util.List;`
	`5`	`+`
	`6`	`+publicclassPermuteUnique {`
	`7`	`+publicList<List<Integer>>permuteUnique(int[]num) {`
	`8`	`+List<List<Integer>>ret =newArrayList<List<Integer>>();`
	`9`	`+if (num ==null \|\|num.length ==0) {`
	`10`	`+returnret;`
	`11`	`+ }`
	`12`	`+`
	`13`	`+// For deal with the duplicate solution, we should sort it.`
	`14`	`+Arrays.sort(num);`
	`15`	`+boolean[]visit =newboolean[num.length];`
	`16`	`+`
	`17`	`+dfs(num,newArrayList<Integer>(),ret,visit);`
	`18`	`+`
	`19`	`+returnret;`
	`20`	`+ }`
	`21`	`+`
	`22`	`+publicvoiddfs(int[]num,ArrayList<Integer>path,List<List<Integer>>ret,boolean[]visit) {`
	`23`	`+intlen =num.length;`
	`24`	`+if (path.size() ==len) {`
	`25`	`+ret.add(newArrayList<Integer>(path));`
	`26`	`+return;`
	`27`	`+ }`
	`28`	`+`
	`29`	`+for (inti =0;i <len;i++) {`
	`30`	`+// 只能连续地选，这样就可以避免生成重复的solution.`
	`31`	`+// 例子：1 2 3 4 4 4 5 6 7 8`
	`32`	`+// 444这个的选法只能:4, 44, 444连续这三种选法`
	`33`	`+if (visit[i] \|\| (i !=0 &&visit[i -1] &&num[i] ==num[i -1])) {`
	`34`	`+continue;`
	`35`	`+ }`
	`36`	`+`
	`37`	`+// 递归以及回溯`
	`38`	`+visit[i] =true;`
	`39`	`+path.add(num[i]);`
	`40`	`+dfs(num,path,ret,visit);`
	`41`	`+path.remove(path.size() -1);`
	`42`	`+visit[i] =false;`
	`43`	`+ }`
	`44`	`+ }`
	`45`	`+}`

Comments

(0)