【算法三十七】51. N 皇后

张开发
• 2026/4/8 15:43:48 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法三十七】51. N 皇后
51. N 皇后回溯class Solution { public ListListString solveNQueens(int n) { ListListString ans new ArrayList(); //每一行的queen在哪一列 int[] queens new int[n]; //每一列有没有重复 boolean[] col new boolean[n]; //主对角线有没有重复 boolean[] dig1 new boolean[2*n-1]; //副对角线有没有重复 boolean[] dig2 new boolean[2*n-1]; dfs(0,queens,col,dig1,dig2,ans); return ans; } private void dfs(int r,int[] queens,boolean[] col,boolean[] dig1,boolean[] dig2,ListListString ans){ int n col.length; if(r n){ ListString partAns new ArrayList(); for(int i:queens){ char[] partAns1 new char[n]; Arrays.fill(partAns1,.); partAns1[i] Q; partAns.add(new String(partAns1)); } ans.add(partAns); return; } //对列遍历 for(int c 0;cn;c){ //对副对角线的规律加上n-1这样符合下标规律 int rc r-c n-1; if(!col[c] !dig1[rc] !dig2[rc]){ queens[r] c; col[c] dig1[rc] dig2[rc] true; //递归 dfs(r1,queens,col,dig1,dig2,ans); //恢复现场 col[c] dig1[rc] dig2[rc] false; } } } }时间复杂度O(N^2 * N!)空间复杂度O(N)

更多文章