[LeetCode] 52. N-Queens II

Binguner 發(fā)布于2019-08-14 15:40 / 3595人閱讀

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云服務(wù)器云服務(wù)器 LeetCode LeetCode_String leetcode_35_SearchIn 52vps

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65936.html

相關(guān)文章

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

摘要：題目要求這里的王后相當(dāng)于國際圍棋的王后，該王后一共有三種移動方式水平垂直，對角線。并將當(dāng)前的臨時結(jié)果作為下一輪的輸入進(jìn)行下一輪的預(yù)判。這里我們進(jìn)行了進(jìn)一步的優(yōu)化，將轉(zhuǎn)化為，其中數(shù)組用來記錄該列是否被占領(lǐng)，數(shù)組用來記錄該行占領(lǐng)了那一列。題目要求 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皇后

摘要：暴力法復(fù)雜度時間空間思路因為皇后問題中，同一列不可能有兩個皇后，所以我們可以用一個一維數(shù)組來表示二維棋盤上皇后的位置。一維數(shù)組中每一個值的下標(biāo)代表著對應(yīng)棋盤的列，每一個值則是那一列中皇后所在的行。 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月技術(shù)文章匯總

摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計工程在線診斷系統(tǒng)設(shè)計與實現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
LeetCode - 013 - 羅馬數(shù)字轉(zhuǎn)整數(shù)（roman-to-integer）

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

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

摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 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