原題網(wǎng)址：https://www.lintcode.com/zh-cn/old/problem/n-queens-ii/

34. N皇后問題 II?

• • ?描述
  • ?筆記
  • ?數(shù)據(jù)
  • ?評測

討論區(qū)?

根據(jù)n皇后問題，現(xiàn)在返回n皇后不同的解決方案的數(shù)量而不是具體的放置布局。

您在真實(shí)的面試中是否遇到過這個題？? Yes 樣例

比如n=4，存在2種解決方案

標(biāo)簽? Zenefits?遞歸 方法同N皇后問題，只不過不生成解決方案而是返回解決方法的個數(shù)。 1.遞歸 AC代碼： class Solution { public:/*** @param n: The number of queens.* @return: The total number of distinct solutions.*/bool canPlaceQ(int row,int col, int * position,int n) {for (int i=0;i<row;i++){if (position[i]==col||abs(row-i)==abs(col-position[i])){return false;}}return true; }void placeQ(int &count,int row,int *position,int n) {if (row==n){++count;}else{for (int j=0;j<n;j++){if (canPlaceQ(row,j,position,n)){position[row]=j;placeQ(count,row+1,position,n);}}} }int totalNQueens(int n) {int count=0;if (n<=0){return 0;}int *position=new int[n];for (int i=0;i<n;i++){position[i]=-1;}int row=0;placeQ(count,row,position,n);return count; } };

2.非遞歸

AC代碼：

class Solution { public:/*** @param n: The number of queens.* @return: The total number of distinct solutions.*/bool canPlaceQ(int row,int col, int * position,int n) {for (int i=0;i<row;i++){if (position[i]==col||abs(row-i)==abs(col-position[i])){return false;}}return true; }void placeQ(int &count,int row,int *position,int n) {int i=0,j=0;while(i<n){while(j<n){if (canPlaceQ(i,j,position,n)){position[i]=j;j=0;break;}else{++j;}}if (position[i]==-1){if (i==0){break;}--i;j=position[i]+1;position[i]=-1;//注意清空上一行的位置！！;continue;}if (i==n-1){++count;j=position[i]+1;//不能用++j，因?yàn)閷ふ业絥-1行的列位置后j被重置為0;position[i]=-1;continue;}++i;}}int totalNQueens(int n) {int count=0;if (n<=0){return 0;}int *position=new int[n];for (int i=0;i<n;i++){position[i]=-1;}int row=0;placeQ(count,row,position,n);return count; }};

?

轉(zhuǎn)載于:https://www.cnblogs.com/Tang-tangt/p/9061556.html

總結(jié)

以上是生活随笔為你收集整理的34 N皇后问题Ⅱ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。