原题链接:http://oj.leetcode.com/problems/n-queens/N皇后问题是非常经典的问题了,记得当时搞竞赛第一道递归的题目就是N皇后。因为这个问题是典型的NP问题,所以在时间复杂度上就不用纠结了,肯定是指数量级的。下面我们来介绍这个题的基本思路。主要思想就是一句话:用一个循环递归处理子问题。这个问题中,在每一层递归函数中,我们用一个循环把一个皇后填入对应行的某一列中,如果当前棋盘合法,我们就递归处理先一行,找到正确的棋盘我们就存储到结果集里面。这种题目都是使用这个套路,就是用一个循环去枚举当前所有情况,然后把元素加入,递归,再把元素移除,这道题目中不用移除的原因是我们用一个一维数组去存皇后在对应行的哪一列,因为一行只能有一个皇后,如果二维数组,那么就需要把那一行那一列在递归结束后设回没有皇后,所以道理是一样的。这道题最后一个细节就是怎么实现检查当前棋盘合法性的问题,因为除了刚加进来的那个皇后,前面都是合法的,我们只需要检查当前行和前面行是否冲突即可。检查是否同列很简单,检查对角线就是行的差和列的差的绝对值不要相等就可以。代码如下:
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> res = new ArrayList<String[]>();
helper(n,0,new int[n], res);
return res;
}
private void helper(int n, int row, int[] columnForRow, ArrayList<String[]> res)
{
if(row == n)
{
String[] item = new String[n];
for(int i=0;i<n;i++)
{
StringBuilder strRow = new StringBuilder();
for(int j=0;j<n;j++)
{
if(columnForRow[i]==j)
strRow.append('Q');
else
strRow.append('.');
}
item[i] = strRow.toString();
}
res.add(item);
return;
}
for(int i=0;i<n;i++)
{
columnForRow[row] = i;
if(check(row,columnForRow))
{
helper(n,row+1,columnForRow,res);
}
}
}
private boolean check(int row, int[] columnForRow)
{
for(int i=0;i<row;i++)
{
if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==row-i)
return false;
}
return true;
}
这道题实现的方法是一个非常典型的套路,有许多题都会用到,基本上大部分NP问题的求解都是用这个方式,比如Sudoku
Solver,Combination
Sum,Combinations,
Permutations,Word
Break II,Palindrome
Partitioning等,所以大家只要把这个套路掌握熟练,那些题就都不在话下哈。
分享到:
相关推荐
leetcode 71 Python用 Python 编写 Leetcode (数据科学家的解决方案) - 易于理解的最佳解决方案,可以通过所有 Leetcode 测试用例,对于非 ...leetcode ...leetcode ...N-Queens (HARD) Leetcode 52. N-
LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034 Find First and ...
LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的时候,需要注意该如何处理!) 模板...
Leetcode-May-Challenge-2021 它包含 Leetcode May Challenge 2021 的解决方案 比赛链接: 问题 问题名称 点击打开问题 无向图中的连通分量数 前缀和后缀搜索 课程表三 一维数组的运行总和 非递减数组 跳跃游戏二 将...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码写的很飘逸,果然是有LISP...N-Queens N-Queens II Balanced Binary Tree Binar
leetcode 530 力码练习 前 250 个问题 1 二和 :check_mark: 3 无重复字符的最长子串 :check_mark: 4 两个有序数组的中位数 5 最长回文子串 7 反转整数 8 字符串到整数 (atoi) 10 正则表达式匹配 11 盛水的容器 12 ...
比如n-queens-ii对应链接为: 题目 url add-two-numbers find-peak-element longest-common-subsequence longest-consecutive-sequence max-area-of-island next-greater-element-ii serialize-and-deserialize-...
leetcode ...NQueens * 回溯法- 网易2017算法工程师笔试题3 * 贪心法- Dijkstra算法 ShortestDistanceAlgorithm * 动态规划- Floyd最短路径算法 ShortestDistanceAlgorithm * 动态规划- 最长公共子序列 ...
leetcode中国力码 我的 Leetcode 生活经历! 我创建了这个存储库来分享我对 leetcode 问题的解决方案。 另外,我会补充一下我在解决问题时的想法,也会补充一些简单的测试用例以供...N-Queens(硬) 56. 合并间隔(中)
leetcode ...N-Queens II 最大子阵列 螺旋矩阵 跳跃游戏 合并间隔 插入间隔 螺旋矩阵 II 排列顺序(无法访问文章) 61-70 轮换名单 独特的路径 独特的路径 II 最小路径和(无法访问文章) 有效号码 加一
leetcode-oo 用 Java 编写的 Leetcode 解决方案 介绍 此存储库包含解决方案列表。 问题解决表 # 标题 解决方案 困难 1 二和 简单的 3 无重复字符的最长子串 中等的 5 最长回文子串 中等的 11 盛水最多的容器 中等的 ...
leetcode 530 leetcode 我对 leetcode 的解决方案。 使用c++解决问题。 # 标题 解决方案 标签 方法 1185 一周中的天 大批 5499 检测长度模式重复 k 次或多次 大批 ...n-queens-ii DFS,搜索 1003 替
leetcode-按类别 看了一些leetcode刷题指南,总结一下两个重点,一是最好按照类别刷题,总结思路;二是由易到难,不要产生太大挫败感。 另外最好集中时间强度大一点来刷;还可以每个题只预留固定的思考时间,做不出...
N-Queens II 平衡二叉树 二叉树中序遍历 二叉树最大路径和 将排序数组转换为二叉搜索树 将排序列表转换为二叉搜索树 将二叉树展平到链表 二叉树的最大深度 二叉树的最小深度 路径和 排列 排列二 在每个节点中填充下...
最大公共字符串leetcode 这本书的在线版本可以在 [gitbook.com] 上查看 进步写作 104 二叉树的最大深度 111 二叉树的最小深度 174 地牢游戏 84 直方图中最大的矩形 85 最大矩形 198 强盗 第213话 第42章 截留雨水 11...
N-Queens II 59.44% 97 交错串 TLE 146 LRU缓存 83.44% 174 地牢游戏 100% 的 Go 提交 354 俄罗斯娃娃信封 23.99% 中等评价 数量 问题 殴打 2 添加两个数字 35.18% 3 无重复字符的最长子串 79.27% 5 最长回文子串 87...
lru缓存leetcode leetcode 版权所有 (C) 2015-2016 Cloudzfy。 版权所有。 ================================================== ====== 二和 两个数字相加 ...N ...n) N-皇后 N-Queens II 最大子阵列 螺旋矩阵
N-Queens 572 另一棵树的子树98 验证二叉搜索树1048 最长的字符串链101 对称树第151话第177话218 天际线问题242 有效字谜378 排序矩阵中的第 K 个最小元素第489章 扫地机器人406按高度重构队列592 分数加减法920 ...
49组Anagrams视频讲解50 Pow(x,n)视频讲解51 N-Queens视频讲解52 N-Queens II视频讲解53最大子数组视频讲解54螺旋矩阵视频讲解55跳转游戏视频讲解56合并间隔视频讲解57插入间隔视频讲解59螺旋矩
java lru leetcode Java实践 算法 ...N-Queens, N-Queens II 组合 子集 词搜索 格雷码 子集二 恢复 IP 地址 回文分区 添加和搜索词 - 数据结构设计 组合和III 加号 正则表达式匹配 断字二 两个整数相除