福哥答案2021-02-16：
天然智慧即可。
1.一般递归。有代码。
须要判断同列和斜线。
2.位运算递归。有代码。
3.我的递归。有代码。
只须要判断斜线。
代码用golang编写，代码如下：
package mainimport ( "fmt" "time")func main() { n := 12 fmt.Println(n, "皇后问题") fmt.Println("------") now := time.Now() fmt.Println("1.一般递归：", num1(n)) fmt.Println("工夫：", time.Now().Sub(now)) fmt.Println("------") now = time.Now() fmt.Println("2.位运算递归：", num2(n)) fmt.Println("工夫：", time.Now().Sub(now)) fmt.Println("------") now = time.Now() fmt.Println("3.我的递归：", num3(n)) fmt.Println("工夫：", time.Now().Sub(now))}func num1(n int) int { if n < 1 { return 0 } record := make([]int, n) return process1(0, record, n)}func process1(i int, record []int, n int) int { if i == n { return 1 } res := 0 for j := 0; j < n; j++ { if isValid(record, i, j) { record[i] = j res += process1(i+1, record, n) } } return res}func isValid(record []int, i int, j int) bool { for k := 0; k < i; k++ { if j == record[k] || abs(record[k]-j) == abs(i-k) { return false } } return true}func abs(a int) int { if a < 0 { return -a } else { return a }}func num2(n int) int { if n < 1 || n > 32 { return 0 } limit := -1 if n != 32 { limit = (1 << n) - 1 } return process2(limit, 0, 0, 0)}func process2(limit int, colLim int, leftDiaLim int, rightDiaLim int) int { if colLim == limit { return 1 } pos := limit & (^(colLim | leftDiaLim | rightDiaLim)) mostRightOne := 0 res := 0 for pos != 0 { mostRightOne = pos & (^pos + 1) pos = pos - mostRightOne res += process2(limit, colLim|mostRightOne, (leftDiaLim|mostRightOne)<<1, (rightDiaLim|mostRightOne)>>1) } return res}func num3(n int) int { rest := make([]int, n) record := make([]int, n) for i := 0; i < n; i++ { rest[i] = i } ansval := 0 ans := &ansval process3(record, 0, rest, ans) return *ans}func process3(record []int, recordLen int, rest []int, ans *int) { restLen := len(rest) if restLen == 0 { *ans++ return } for i := 0; i < restLen; i++ { isValid := true for j := 0; j < recordLen; j++ { //不须要看同行和同列，只须要思考斜线 if abs(j-recordLen) == abs(record[j]-rest[i]) { isValid = false break } } if isValid { record[recordLen] = rest[i] restCopy := make([]int, restLen) copy(restCopy, rest) restCopy = append(restCopy[:i], restCopy[i+1:]...) process3(record, recordLen+1, restCopy, ans) } }}执行后果如下：
左神java代码
评论