[LeetCode] 52. N-Queens II

Binguner 发布于2019-08-14 15:40 / 3371人阅读

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;
        }
    }
}

专线服务 idc机房托管 LeetCode LeetCode_String leetcode_35_SearchIn 52vps

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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