LeetCode--051--N皇后(java)-star
2024-08-23 13:08:42
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."], ["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。 思路:
按上述解法1queens数组为[1,3,0,2] 因为没以行就一个queens所以不用考虑行了,只纪录该行哪一列放了Q
先建立queens数组(建立好后用addSolution填好Q和point),用回溯的方法,把所有满足题意的方式都穷举出来.
TIME:O(N^N)?
SPACE:O(N)
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
if(n <= 0)return res; helper(res,new int[n],0);
return res;
}
public void helper(List<List<String>> res,int[] queens,int pos){
if(pos == queens.length){
addSolution(res,queens);
return;
} for(int i = 0;i < queens.length;i++){
queens[pos] = i;
if(isValid(queens,pos)){
helper(res,queens,pos+1);
}
}
}
public boolean isValid(int[] queens,int pos){
for(int i = 0;i < pos;i++){
if(queens[i] == queens[pos]){//在同一列
return false;
}else if(Math.abs(queens[pos] - queens[i]) == Math.abs(i - pos)){//在同一对角线上
return false;
}
}
return true;
}
public void addSolution(List<List<String>> res ,int[] queens){
List<String> list = new ArrayList<>();
for(int i = 0;i < queens.length;i++){
StringBuilder sb = new StringBuilder();
for(int j = 0;j < queens.length;j++){
if(queens[i] == j){
sb.append('Q');
}else{
sb.append('.');
}
}
list.add(sb.toString()); }
res.add(list);
}
}
2019-05-08 20:51:23
python版本,秒杀java
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def DFS(queens,xy_dif,xy_sum):
p = len(queens)
if p == n:
result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q],xy_dif+[p-q],xy_sum+[p+q])
result = []
DFS([],[],[])
return [["."*i + "Q" + "."*(n-i-1) for i in sol]for sol in result]
2020-01-13 16:38:14
最新文章
- 茂名石化BPM应用实践 ——业务协同及服务共享平台建设和应用
- Task异步编程
- ubuntu下mediawiki的使用
- 高大上的uGUI正式版发布了
- hibernate spring annotation setup
- CalParcess.php.
- Sqli-labs less 39
- java开发命名规范(转载)
- WebForm开发常用代码
- xcode UIButton创建、监听按钮点击、自定义按钮 、状态 、内边距
- 【LeetCode题解】链表Linked List
- form表单中get和post两种提交方式的区别
- oracle session数激增排查过程
- 使用jTessBoxEditorFX训练Tesseract-OCR教程
- 中间人攻击(MITM)之数据截获原理
- [UE4]世界坐标和相对坐标
- Linq 查询 List集合
- 「Android 开发」入门笔记
- openshift 持续集成与部署 -- 构建部署流水线
- android activity lifecycle
热门文章
- Java接口继承
- Delphi XE2 之 FireMonkey 入门(19) - TFmxObject 的子类们(表)
- 阶段1 语言基础+高级_1-3-Java语言高级_04-集合_08 Map集合_6_Map集合遍历键值对方式
- sudo: pip:找不到命令
- Fiddler抓百度请求
- es6 export及export default 的使用 及 区别
- How to increase timeout for your ASP.NET Application ?
- C++调用C#类库函数
- 关于toString()和valueOf()以及Object.prototype.toString.call()的结合理解
- String.indexOf()的使用方法