• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode52.N皇后II|N-QueensII

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/9910438.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回 n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

8ms
 1 class Solution {
 2     func totalNQueens(_ n: Int) -> Int {
 3         if n == 0 {
 4             return 0
 5         }
 6         var answer = 0
 7         var limit = (1<<n) - 1
 8         dfs(h: 0, r: 0, l: 0, answer: &answer, limit: &limit)
 9         return answer
10     }
11     private func dfs(h: Int, r: Int, l: Int, answer: inout Int, limit: inout Int) {
12         if h == limit {
13             answer += 1
14             return
15         }
16         var position = limit & (~(h|r|l))
17         while position > 0 {
18             let p = position & (-position)
19             position -= p
20             dfs(h: h+p, r: (r+p)<<1, l: (l+p)>>1, answer: &answer, limit: &limit)
21         }
22     }
23 }

20ms

 1 class Solution {
 2     var placeArr : [Int]!
 3     var totalN : Int = 0
 4     func canPlace(_ row:Int , _ col:Int) -> Bool{
 5 
 6         var colInRow : Int = 0
 7         var offset : Int = 0
 8         for idx in 0 ..< row {
 9             colInRow = placeArr[idx]
10            
11             if colInRow == col {
12                 return false
13             }
14             offset = row - idx
15             if colInRow == col - offset{
16                 return false
17             }
18             if colInRow == col + offset{
19                 return false
20             }
21         }
22         return true
23     }
24     
25     var count : Int = 0
26     func place(_ row:Int) -> (){
27         if row == totalN {
28             count += 1
29         }else{
30             for col in 0..<totalN {
31                 if canPlace(row,col) {
32                     placeArr[row] = col
33                     place(row + 1)
34                 }
35             }
36         }
37     }
38     
39     func totalNQueens(_ n: Int) -> Int {
40         totalN = n
41         placeArr = Array(repeating : 0 , count : totalN)
42         
43         place(0)
44         return count
45     }
46 }

28ms

 1 class Solution {
 2     func totalNQueens(_ n: Int) -> Int {
 3         var board = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
 4         var result = 0
 5         backtrack(&board, 0, &result)
 6         return result
 7     }
 8     
 9     private func backtrack(_ board: inout [[Bool]], _ row: Int, _ result: inout Int) {
10         if row == board.count {
11             result += 1
12         } else {
13             for col in 0..<board.count where canPlaceQueen(board, row, col) {
14                 board[row][col] = true
15                 backtrack(&board, row + 1, &result)
16                 board[row][col] = false
17             }
18         }
19     }
20     
21     private func canPlaceQueen(_ board: [[Bool]], _ row: Int, _ col: Int) -> Bool {
22         let n = board.count
23         
24         for i in 0..<row where board[i][col] {
25             return false
26         }
27         
28         var i = row - 1
29         var j = col - 1
30         while i >= 0 && j >= 0 {
31             if board[i][j] {
32                 return false
33             }
34             i -= 1
35             j -= 1
36         }
37         
38         i = row - 1
39         j = col + 1
40         while i >= 0 && j < n {
41             if board[i][j] {
42                 return false
43             }
44             i -= 1
45             j += 1
46         }
47         
48         return true
49     }
50 }

32ms

 1 class Solution {
 2     var placeArr : [Int]!
 3     var totalN : Int = 0
 4     func canPlace(_ row:Int , _ col:Int) -> Bool{
 5 
 6         var colInRow : Int = 0
 7         var offset : Int = 0
 8         for idx in 0 ..< row {
 9             colInRow = placeArr[idx]
10            
11             if colInRow == col {
12                 return false
13             }
14             offset = row - idx
15             if colInRow == col - offset{
16                 return false
17             }
18             if colInRow == col + offset{
19                 return false
20             }
21         }
22         return true
23     }
24     
25     var count : Int = 0
26     func place(_ row:Int) -> (){
27         if row == totalN {
28             count += 1
29         }else{
30             for col in 0..<totalN {
31                 if canPlace(row,col) {
32                     placeArr[row] = col
33                     place(row + 1)
34                 }
35             }
36         }
37     }
38     
39     func totalNQueens(_ n: Int) -> Int {
40         totalN = n
41         placeArr = Array(repeating : 0 , count : totalN)
42         
43         place(0)
44         return count
45     }
46 }

44ms

 1 class Solution {
 2     
 3     func totalNQueens(_ n: Int) -> Int {
 4         var result = 0
 5         var cols = [Int]()
 6         cols.reserveCapacity(n)
 7         queensDFS(n, &cols, &result)
 8         return result
 9     }
10     
11     fileprivate func queensDFS(_ n: Int, _ cols: inout [Int], _ counter: inout Int) {
12         if cols.count == n {
13             counter += 1
14             return 
15         }
16         
17         for colIndex in 0..<n {
18             guard isValid(cols, colIndex) else {
19                 continue
20             }
21             cols.append(colIndex)
22             queensDFS(n, &cols, &counter)
23             cols.removeLast()
24         }
25     }
26     
27     fileprivate func isValid(_ cols: [Int], _ colIndex: Int) -> Bool {
28         for rowIndex in 0..<cols.count {
29             if colIndex == cols[rowIndex] {
30                 return false
31             }
32             if abs(colIndex - cols[rowIndex]) == abs(cols.count - rowIndex) {
33                 return false
34             }
35         }
36         return true
37     }
38 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swiftNSdata转换nsstring发布时间:2022-07-13
下一篇:
[Swift]LeetCode269.外星人词典$AlienDictionary发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap