网站建设的技术支持,武夷山网站定制,网站备案帐号是什么情况,企业二级域名自助建站平台一:题目 二:上码
class Solution {/**思路:1.先说我们选用的数据结构;我们是选取的是ListListstring ans 来存每次的结果;我们在创建这个二维矩阵的时候用的是char的二维数组,那么的话等到我们得到一种可行解的时候 将char的二维数组每一行转换成 String 并存…一:题目 二:上码
class Solution {/**思路:1.先说我们选用的数据结构;我们是选取的是ListListstring ans 来存每次的结果;我们在创建这个二维矩阵的时候用的是char的二维数组,那么的话等到我们得到一种可行解的时候 将char的二维数组每一行转换成 String 并存入 ans 中2:判断可行性1:不能在同一行2:不能在同一列3:不能在同一对角线这里就是给出我们的一个坐标 然后在char[][]数组 遍历上方三个条件那么的话 判断是否合法3.递归三步曲1:确定递归函数和递归参数void getAns(int rows,int n)2:确定回溯终止条件if (rows n) 行数也就是我们的n rows是从0开始的 那么达到n也就是比正常的范围大一个3:确定回溯体 这里的for循环其实就是我们的不同的列那么我们根据参数中的行 那么我们就组成了(行,列)那么的话 我们就可以确定出一个坐标 并根据该坐标是否合法来判断是否给该坐标进行赋值*/private ListListString ans new ArrayList();private char[][] arr;public void fillArr() {for (char[] chA: arr) {Arrays.fill(chA,.);}}public ListString getString() {ListString list new ArrayList();for (char[] chA: arr) {//将二维char数组中的每一行转换成一个字符串 存放在list中list.add(String.copyValueOf(chA));}return list;}//判断坐标(row,col)这个坐标是否合法public boolean isLegal(int row,int col,int n) { //是否在同一列for (int i 0; i row; i) {if (arr[i][col] Q) return false;}//45°角for (int i row-1,j col-1; i 0 j 0; i--,j--) {if (arr[i][j] Q) return false;}//135°for (int i row-1,j col1; i 0 j n; i--,j) {if (arr[i][j] Q) return false;}return true;}public void getAns(int rows,int n) {if (rows n) {ans.add(getString());}for (int col 0; col n; col) {if (isLegal(rows,col,n)) {arr[rows][col] Q;getAns(rows1,n);arr[rows][col] .;}}}public ListListString solveNQueens(int n) {arr new char[n][n];fillArr();getAns(0,n);return ans; }
}
