[LeetCode] 52. N-Queens II

Binguner 發布于2019-08-14 15:40 / 3592人閱讀

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.

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.."]
]

Solution

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        boolean[] col = new boolean[n];  // columns   |
        boolean[] d1 = new boolean[2*n]; // diagonals 
        boolean[] d2 = new boolean[2*n]; // diagonals /
        helper(0, col, d1, d2, n);
        return count;
    }
    private void helper(int r, boolean[] col, boolean[] d1, boolean[] d2, int n) {
        if (r == n) count++;
        for (int c = 0; c < n; c++) {
            int id1 = c+n-r;
            int id2 = c+r;
            if (col[c] || d1[id1] || d2[id2]) continue;
            col[c] = true; d1[id1] = true; d2[id2] = true;
            helper(r+1, col, d1, d2, n);
            col[c] = false; d1[id1] = false; d2[id2] = false;
        }
    }
}

云服務器 GPU云服務器 LeetCode LeetCode_String leetcode_35_SearchIn 52vps

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65936.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] N-Queens N皇后

摘要：暴力法復雜度時間空間思路因為皇后問題中，同一列不可能有兩個皇后，所以我們可以用一個一維數組來表示二維棋盤上皇后的位置。一維數組中每一個值的下標代表著對應棋盤的列，每一個值則是那一列中皇后所在的行。 N-Queens I The n-queens puzzle is the problem of placing n queens on an n×n chessboard such th...

YanceyOfficial 2019-08-14 12:31 評論0 收藏0
6-9月技術文章匯總

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

miya 2019-07-30 18:03 評論0 收藏0
LeetCode - 013 - 羅馬數字轉整數（roman-to-integer）

摘要：字符數值例如，羅馬數字寫做，即為兩個并列的。通常情況下，羅馬數字中小的數字在大的數字的右邊。給定一個羅馬數字，將其轉換成整數。 Create by jsliang on 2019-05-23 13:24:24 Recently revised in 2019-05-23 14:55:20 一目錄不折騰的前端，和咸魚有什么區別目錄一目錄二前言三解題 ...

v1 2019-05-27 17:41 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0