[Leetcode] N-Queens N皇后

YanceyOfficial 發布于2019-08-14 12:31 / 1270人閱讀

摘要：暴力法復雜度時間空間思路因為皇后問題中，同一列不可能有兩個皇后，所以我們可以用一個一維數組來表示二維棋盤上皇后的位置。一維數組中每一個值的下標代表著對應棋盤的列，每一個值則是那一列中皇后所在的行。

N-Queens I

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 all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens" placement, where "Q" and "." both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

暴力法 復雜度

時間 O(N^3) 空間 O(N)

思路

因為n皇后問題中，同一列不可能有兩個皇后，所以我們可以用一個一維數組來表示二維棋盤上皇后的位置。一維數組中每一個值的下標代表著對應棋盤的列，每一個值則是那一列中皇后所在的行。這樣我們可以只對一個一維數組進行深度優先搜索，來找出對于每一列，我們的皇后應該放在哪一行。在下一輪搜索之前，我們先檢查一下新構成的數組是否是有效的，這樣可以剪掉不必要的分支。檢查的方法則是看之前排好的每一個皇后是否沖突。

代碼

public class Solution {
    
    List> res;
    
    public List> solveNQueens(int n) {
        res = new LinkedList>();
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return res;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            List one = new LinkedList();
            // 構成表示整個棋盤的字符串
            for(int num : nqueens){
                // 構成一個形如....Q....的字符串
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j = num + 1; j < n; j++){
                    sb.append(".");
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            //選擇下一列的數字
            // 比如之前已經選了13xxxxxx，下一列可以選6，形成136xxxxx
            for(int num = 0; num < n; num++){
                nqueens[i] = num;
                // 如果是有效的，繼續搜索
                if(isValid(nqueens, i)){
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            // 檢查對角線只要判斷他們差的絕對值和坐標的差是否相等就行了
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
}

集合法 復雜度

時間 O(N^2) 空間 O(N)

思路

該方法的思路和暴力法一樣，區別在于，之前我們判斷一個皇后是否沖突，是遍歷一遍當前皇后排列的列表，看每一個皇后是否沖突。這里，我們用三個集合來保存之前皇后的信息，就可以O(1)時間判斷出皇后是否沖突。三個集合分別是行集合，用于存放有哪些行被占了，主對角線集合，用于存放哪個右上到左下的對角線被占了，副對角線集合，用于存放哪個左上到右下的對角線被占了。如何唯一的判斷某個點所在的主對角線和副對角線呢？我們發現，兩個點的行號加列號的和相同，則兩個點在同一條主對角線上。兩個點的行號減列號的差相同，則兩個點再同一條副對角線上。

注意

主對角線row + col，副對角線row - col

代碼

public class Solution {
    
    List> res = new LinkedList>();;
    Set rowSet = new HashSet();
    Set diag1Set = new HashSet();
    Set diag2Set = new HashSet();
    
    public List> solveNQueens(int n) {
        helper(new LinkedList(), n, 0);
        return res;
    }
    
    public void helper(LinkedList tmp, int n, int col){
        if(col == n){
            List one = new LinkedList();
            for(Integer num : tmp){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j = num + 1; j < n; j++){
                    sb.append(".");
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            // 對于列col，看皇后應該放在第幾行
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                // 如果三條線上已經有占據的皇后了，則跳過該種擺法
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                // 用回溯法遞歸求解
                tmp.add(row);
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(tmp, n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
                tmp.removeLast();
            }
        }
    }
}

N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

暴力法 復雜度

時間 O(N^3) 空間 O(N)

思路

跟I的解法一樣，只不過把原本構造字符串的地方換成了計數器加一。

代碼

public class Solution {
    
    List> res;
    int cnt = 0;
    
    public int totalNQueens(int n) {
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return cnt;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            cnt++;
        } else {
            for(int num = 0; num < n; num++){
                nqueens[i] = num;
                if(isValid(nqueens, i)){
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
}

集合法 復雜度

時間 O(N^2) 空間 O(N)

思路

跟I的解法一樣，只不過把原本構造字符串的地方換成了計數器加一。

代碼

public class Solution {
    
    Set rowSet = new HashSet();
    Set diag1Set = new HashSet();
    Set diag2Set = new HashSet();
    int cnt = 0;
    
    public int totalNQueens(int n) {
        helper(n, 0);
        return cnt;
    }
    
    public void helper(int n, int col){
        if(col == n){
            cnt++;
        } else {
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
            }
        }
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64535.html

leetcode51. N-Queens 【更新加上leetcode52 N-Queens II

摘要：題目要求這里的王后相當于國際圍棋的王后，該王后一共有三種移動方式水平垂直，對角線。并將當前的臨時結果作為下一輪的輸入進行下一輪的預判。這里我們進行了進一步的優化，將轉化為，其中數組用來記錄該列是否被占領，數組用來記錄該行占領了那一列。題目要求 The n-queens puzzle is the problem of placing n queens on an n×n chessb...

BingqiChen 2019-08-15 10:42 評論0 收藏0
[LeetCode] 52. N-Queens II

Problem The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. showImg(https://segmentfault.com/img/bVQrOx?w=258&h=276); Given an intege...

Binguner 2019-08-14 15:40 評論0 收藏0
6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態碼詳解無狀態協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
數據結構與算法之精講「遞歸系列」

摘要：終止條件遞推公式遞歸的分類通過做大量的題，根據遞歸解決不同的問題，引申出來的幾種解決和思考的方式。我們通過層與層之間的計算關系用遞推公式表達出來做計算，經過層層的遞歸，最終得到結果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言幾個月之前就想寫這樣一篇文章分享給大家，由于自己有心而力不足，沒有把真...

zhichangterry 2019-08-26 13:50 評論0 收藏0
八皇后問題的JavaScript解法

摘要：關于八皇后問題的解法，總覺得是需要學習一下算法的，哪天要用到的時候發現真不會就尷尬了背景八皇后問題是一個以國際象棋為背景的問題如何能夠在的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后為了達到此目的，任兩個皇后都不能處關于八皇后問題的 JavaScript 解法，總覺得是需要學習一下算法的，哪天要用到的時候發現真不會就尷尬了背景八皇后問題是一個以國際象棋為背...

derek_334892 2019-08-19 18:18 評論0 收藏0