LintCode N皇后问题 II题目代码

题目

根据n皇后问题,现在返回n皇后不同的解决方案的数量而不是具体的放置布局。

样例 比如n=4,存在2种解决方案

代码

class Solution {
    /**
     * Calculate the total number of distinct N-Queen solutions.
     * @param n: The number of queens.
     * @return: The total number of distinct solutions.
     */
    public static int sum;
    public int totalNQueens(int n) {
        sum = 0;
        int[] usedColumns = new int[n];
        placeQueen(usedColumns, 0);
        return sum;
    }
    public void placeQueen(int[] usedColumns, int row) {
        int n = usedColumns.length;
        
        if (row == n) {
            sum ++;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(usedColumns, row, i)) {
                usedColumns[row] = i;
                placeQueen(usedColumns, row + 1);
            }
        }
    }
    public boolean isValid(int[] usedColumns, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (usedColumns[i] == col) {
                return false;
            }
            if ((row - i) == Math.abs(col-usedColumns[i])) {
                return false;
            }
        }
        return true;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

2975
来自专栏码匠的流水账

聊聊storm的CheckpointSpout

storm-2.0.0/storm-client/src/jvm/org/apache/storm/topology/TopologyBuilder.java

2666
来自专栏数据结构与算法

1003 电话连线

题目描述 Description 一个国家有n个城市。若干个城市之间有电话线连接,现在要增加m条电话线(电话线当然是双向的了),使得任意两个城市之间都直接或间接...

3415
来自专栏非典型技术宅

iOS实践:一步步实现星级评分1. 创建星星2. 优化3. 灵异事件

1814
来自专栏Java 技术分享

Ajax 案例之三级联动

3446

.NET中的密钥加密

本教程将演示如何通过System.Security.Cryptography在.NET Framework 1.1中实现对称加密/密钥加密。

6178
来自专栏大内老A

ASP.NET MVC的Model元数据与Model模板:将”ListControl”引入ASP.NET MVC

我们不仅可以创建相应的模板来根据Model元数据控制种类型的数据在UI界面上的呈现方法,还可以通过一些扩展来控制Model元数据本身。在某些情况下通过这两者的结...

3716
来自专栏函数式编程语言及工具

Akka(8): 分布式运算:Remoting-远程查找式

  Akka是一种消息驱动运算模式,它实现跨JVM程序运算的方式是通过能跨JVM的消息系统来调动分布在不同JVM上ActorSystem中的Actor进行运算,...

4369
来自专栏技术之路

WPF MVVM实现TreeView

今天有点时间,做个小例子WPF MVVM 实现TreeView 只是一个思路大家可以自由扩展 文章最后给出了源码下载地址 图1 ?    图2     ? 模...

2819
来自专栏恰童鞋骚年

Hadoop学习笔记—12.MapReduce中的常见算法

    "数据去重"主要是为了掌握和利用并行化思想来对数据进行有意义的筛选。统计大数据集上的数据种类个数、从网站日志中计算访问地等这些看似庞杂的任务都会涉及数据...

1462

扫码关注云+社区

领取腾讯云代金券