Commit8bff680

applewjg

committed

add iteration solution

Change-Id: Ic427cd78746a2a3234c4f75d7b153086f999af17

1 parentaed6fa2 commit8bff680Copy full SHA for 8bff680

File tree

+26

-2

lines changed

+26

-2

lines changed

Lines changed: 26 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -25,11 +25,11 @@`
`25`	`25`	`Solution: 1. Recursion.`
`26`	`26`	`2. Recursion + bit version. (fast)`
`27`	`27`	`The idea is from http://www.matrix67.com/blog/archives/266 (in chinese).`
	`28`	`+ 3. Iteration.`
`28`	`29`	`*/`
`29`		`-`
`30`	`30`	`publicclassSolution {`
`31`	`31`	`publicinttotalNQueens(intn) {`
`32`		`-returntotalNQueens_2(n);`
	`32`	`+returntotalNQueens_3(n);`
`33`	`33`	`}`
`34`	`34`	`publicinttotalNQueens_1(intn) {`
`35`	`35`	`int[]board =newint[n];`
`@@ -76,4 +76,28 @@ public void totalNQueensRe2(int n, int row, int ld, int rd, int[] res) {`
`76`	`76`	`}`
`77`	`77`	`}`
`78`	`78`	`}`
	`79`	`+publicinttotalNQueens_3(intn) {`
	`80`	`+int[]a =newint[n];`
	`81`	`+Arrays.fill(a,-1);`
	`82`	`+intres =0;`
	`83`	`+introw =0;`
	`84`	`+while (row >=0) {`
	`85`	`+if (row ==n) {`
	`86`	`+res++;row--;`
	`87`	`+ }`
	`88`	`+inti =a[row] == -1 ?0 :a[row] +1;`
	`89`	`+for ( ;i <n; ++i) {`
	`90`	`+if (isValid(a,row,i)) {`
	`91`	`+a[row] =i;`
	`92`	`+row++;`
	`93`	`+break;`
	`94`	`+ }`
	`95`	`+ }`
	`96`	`+if (i ==n) {`
	`97`	`+a[row] = -1;`
	`98`	`+row--;`
	`99`	`+ }`
	`100`	`+ }`
	`101`	`+returnres;`
	`102`	`+ }`
`79`	`103`	`}`

Comments

(0)