摘要:题目要求这里的王后相当于国际围棋的王后,该王后一共有三种移动方式水平垂直,对角线。并将当前的临时结果作为下一轮的输入进行下一轮的预判。这里我们进行了进一步的优化,将转化为,其中数组用来记录该列是否被占领,数组用来记录该行占领了那一列。
题目要求
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 all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens" placement, where "Q" and "." both indicate a queen and an empty space respectively. For example, There exist two distinct solutions to the 4-queens puzzle: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
这里的王后相当于国际围棋的王后,该王后一共有三种移动方式:水平、垂直,对角线。问要如何将n个王后布局在n*n的棋盘中保证她们不会互相伤害捏?
思路一:利用Set和Map利用动态编程的思想。只要当前列,以及左对角线和右对角线都没有被占用的话,就可以在当前位置上暂时填上一个值。并将当前的临时结果作为下一轮的输入进行下一轮的预判。
在这里我们用Map
public List> solveNQueens(int n) { List
> result = new ArrayList
>(); if(n==0){ return result; } //记录左右对角线情况 Set
leftCordinal = new HashSet (), rightCordinal = new HashSet (); Map current = new HashMap (); solveNQueens(result, current, leftCordinal, rightCordinal, n); return result; } public void solveNQueens(List > result, Map
current, Set leftCordinal, Set rightCordinal, int n){ if(current.size() == n){ List currentResult = new ArrayList (); StringBuilder s = new StringBuilder(); for(int i = 0 ; i 在这里其实可以用boolean[]代替Set,用简单值类型的数组代替复杂的数据结构往往可以提高性能。
public List> solveNQueens2(int n) { List
> result = new ArrayList
>(); if(n==0){ return result; } //记录左右对角线情况 boolean[] leftCordinal = new boolean[n*2-1], rightCordinal = new boolean[n*2-1]; Map
current = new HashMap (); solveNQueens2(result, current, leftCordinal, rightCordinal, n); return result; } public void solveNQueens2(List > result, Map
current, boolean[] leftCordinal, boolean[] rightCordinal, int n){ if(current.size() == n){ List currentResult = new ArrayList (); StringBuilder s = new StringBuilder(); for(int i = 0 ; i 将Map类型也转化一下? 我们发现,每一次得到一个结果时,都需要将相应的值转化为String然后添加的数组再添加到结果集中。但是其实这些String 的值都是重复利用的。毕竟Q可能位于0~n-1的任何位置上,也就是说有n个固定的互异字符串,但是一个结果上一定会包含所有这些字符串。这里我们进行了进一步的优化,将Map转化为boolean[]+int[],其中bool数组用来记录该列是否被占领,int数组用来记录该行占领了那一列。
public class NQueens_51 { //将map数据结构int[]+boolean[]+lines[]+ ListN-Queens II 题目和实现> res; boolean[] col, lslash, rslash; int[] p; int n; String[] lines; private void dfs(int i) { if(i == n) { List
board = new ArrayList (); for(int j = 0; j < n; j++) { board.add(lines[p[j]]); } res.add(board); return; } for(int j = 0; j < n; j++) { if(!col[j] && !lslash[i+j] && !rslash[j-i+n-1]) { col[j] = true; lslash[i+j] = true; rslash[j-i+n-1] = true; p[i] = j; dfs(i+1); col[j] = false; lslash[i+j] = false; rslash[j-i+n-1] = false; } } } public List > solveNQueens3(int n) { this.n = n; res = new ArrayList
>(); col = new boolean[n]; lslash = new boolean[2*n-1]; rslash = new boolean[2*n-1]; p = new int[n]; char[] line = new char[n]; lines = new String[n]; for(int i = 0; i < n; i++) { line[i] = "."; } for(int i = 0; i < n; i++) { line[i] = "Q"; lines[i] = String.copyValueOf(line); line[i] = "."; } dfs(0); return res; } }
Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions.相比于I,这里不要去获得具体的答案,只需要返回解答的数量即可。其实比I要简单。思路还是相同的,利用迭代实现自顶向下的动态编程
代码如下:public int totalNQueens(int n) { boolean[] leftCordinal = new boolean[n*2-1], rightCordinal= new boolean[n*2-1], vertical = new boolean[n]; int result = 0; return totalNQueens(0, n, result, vertical, leftCordinal, rightCordinal); } public int totalNQueens(int current, int n, int result, boolean[] vertical, boolean[] leftCordinal, boolean[] rightCordinal){ if(current == n){ return ++result; } for(int i = 0 ; i
想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/67292.html
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. showImg(https://segmentfault.com/img/bVQrOx?w=258&h=276); Given an intege...
摘要:暴力法复杂度时间空间思路因为皇后问题中,同一列不可能有两个皇后,所以我们可以用一个一维数组来表示二维棋盘上皇后的位置。一维数组中每一个值的下标代表着对应棋盘的列,每一个值则是那一列中皇后所在的行。 N-Queens I The n-queens puzzle is the problem of placing n queens on an n×n chessboard such th...
摘要:分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥?...
摘要:题目链接这道题找是否有赢的方法和相似,稍微简化了。统计行列和两个对角线的情况,两个分别用和来记。然后判断是否有一个人赢只需要的复杂度。当然这么做的前提是假设所有的都是的,棋盘一个地方已经被占用了,就不能走那个地方了。 348. Design Tic-Tac-Toe 题目链接:https://leetcode.com/problems... 这道题找是否有player赢的方法和N-Que...
摘要:自己没事刷的一些的题目,若有更好的解法,希望能够一起探讨项目地址 自己没事刷的一些LeetCode的题目,若有更好的解法,希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
阅读 733·2021-11-23 09:51
阅读 2430·2021-10-11 11:10
阅读 1299·2021-09-23 11:21
阅读 1090·2021-09-10 10:50
阅读 882·2019-08-30 15:54
阅读 3326·2019-08-30 15:53
阅读 3287·2019-08-30 15:53
阅读 3186·2019-08-29 17:23