題目526：優(yōu)美的排列

假設(shè)有從 1 到 N 的 N 個(gè)整數(shù)，如果從這 N 個(gè)數(shù)字中成功構(gòu)造出一個(gè)數(shù)組，使得數(shù)組的第 i 位 (1 <= i <= N) 滿足如下兩個(gè)條件中的一個(gè)，我們就稱這個(gè)數(shù)組為一個(gè)優(yōu)美的排列。條件：

• 第 i 位的數(shù)字能被 i 整除

• i 能被第 i 位上的數(shù)字整除

現(xiàn)在給定一個(gè)整數(shù) N，請(qǐng)問可以構(gòu)造多少個(gè)優(yōu)美的排列？

示例1：

輸入: 2
輸出: 2
解釋:

第 1 個(gè)優(yōu)美的排列是 [1, 2]:
  第 1 個(gè)位置（i=1）上的數(shù)字是1，1能被 i（i=1）整除
  第 2 個(gè)位置（i=2）上的數(shù)字是2，2能被 i（i=2）整除

第 2 個(gè)優(yōu)美的排列是 [2, 1]:
  第 1 個(gè)位置（i=1）上的數(shù)字是2，2能被 i（i=1）整除
  第 2 個(gè)位置（i=2）上的數(shù)字是1，i（i=2）能被 1 整除

說明:

1. N 是一個(gè)正整數(shù)，并且不會(huì)超過15。

分析

回溯思想，題目明確說明N不會(huì)超過15，類似于暴力解法，但是帶有剪枝策略，在第1-N個(gè)位置，依次放置數(shù)字，每個(gè)位置都嘗試1-N，看是否合適，同時(shí)記錄下這個(gè)數(shù)字使用的情況。如果不合適在當(dāng)前位置直接換下一個(gè)數(shù)字，如果合適則有兩種選擇，第一在當(dāng)前位置換一個(gè)數(shù)字嘗試，第二繼續(xù)回溯，當(dāng)前位置使用這個(gè)數(shù)字，下一位置繼續(xù)嘗試1-N。

代碼

class Solution {public:   int countArrangement(int N) {       used.resize(N + 1, false);       BackTrace(N, 1);       return ret;  }
   int ret = 0;   vector<bool> used;   void BackTrace(int N, int idx) {       if (idx > N) { // 所有位置都已經(jīng)有合適的數(shù)字，結(jié)果加1           ret += 1;           return;      }       for (int i = 1; i <= N; ++i) {           // 過濾掉不合適的數(shù)字和已經(jīng)使用過的數(shù)字           if (!used[i] && ((idx % i == 0) || (i % idx == 0))) {               used[i] = true;               BackTrace(N, idx + 1);               used[i] = false;          }      }  }};

C++線程池的實(shí)現(xiàn)之格式修訂版

每日一題：N皇后問題

點(diǎn)此留言