建站
咨詢
售后
建站咨詢
新聞中心
前言
給定一個含有8個數(shù)字的數(shù)組，判斷有沒有可能把這8個數(shù)字分別放到正方體的8個頂點上，使得正方體上三組相對面上的4個頂點的和都相等。
成都創(chuàng)新互聯(lián)擁有一支富有激情的企業(yè)網(wǎng)站制作團(tuán)隊，在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)深耕十多年，專業(yè)且經(jīng)驗豐富。十多年網(wǎng)站優(yōu)化營銷經(jīng)驗，我們已為超過千家中小企業(yè)提供了成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計解決方案，按需網(wǎng)站建設(shè)，設(shè)計滿意，售后服務(wù)無憂。所有客戶皆提供一年免費網(wǎng)站維護(hù)!
本文就跟大家分享下這個問題的解決方案，歡迎各位感興趣的開發(fā)者閱讀本文。
正方體的組成
初次看到這個問題，很多開發(fā)者可能會比較蒙，一時間無法找到切入點。那我們就先畫個正方體出來，給每個頂點標(biāo)記a1, a2 ,a3 ,...., a8。如下圖所示：
iShot_2023-06-26_07.36.45
實現(xiàn)思路
有了圖之后，我們在做進(jìn)一步的分析，這個正方體有6個面，3組相對的面（上下、前后、左右）：
- a1, a2, a4, a3 | a5, a6, a8, a7
- a1, a5, a6, a2 | a3, a4, a8, a7
- a1, a3, a7, a5 | a2, a4, a8, a6
有了這些條件后，再次結(jié)合題意，我們可知：只需要將8個數(shù)字分別放入正方體的8個頂點中，判斷三組相對面的頂點和是否都相等，這個問題就解決了。
8個數(shù)字分別放到8個頂點上，所有數(shù)字都有可能放入任意一個頂點。換言之就是求這8個數(shù)字的所有排列，我的另一篇文章實現(xiàn)字符串的排列算法詳細(xì)講解了這個算法的實現(xiàn)思路，此處不過多贅述。
分析到這里，我們就得出了一個完整的實現(xiàn)思路：
- 求出給定數(shù)組中8個數(shù)字的所有排列
- 遍歷所有排列，將每個排列中的元素映射到變量中(a1, a2, ..., a8)
- 判斷8個點組成的三組相對面的頂點和是否相等
實現(xiàn)代碼
分析出思路后，我們就可以將上述思路轉(zhuǎn)換成代碼了，如下所示：
/**
* 能否構(gòu)成正方體
* @param nums
*/
public isCubePossible(nums: Array): boolean {
if (nums.length !== 8) {
return false;
}
// 獲取8個點的所有排列
const list = this.permute(nums.join(""));
for (let i = 0; i < list.length; i++) {
// 將當(dāng)前組合中的點轉(zhuǎn)為number類型放入item
const item: Array = [];
for (let j = 0; j < list[i].length; j++) {
item.push(+list[i][j]);
}
// 從當(dāng)前組合中獲取正方體的8個點
const [a1, a2, a3, a4, a5, a6, a7, a8] = item;
// 判斷正方體三組相對面上的點相加是否相等
if (
a1 + a2 + a4 + a3 === a5 + a6 + a8 + a7 &&
a1 + a5 + a6 + a2 === a3 + a4 + a8 + a7 &&
a1 + a3 + a7 + a5 === a2 + a4 + a8 + a6
) {
return true;
}
}
return false;
} 上述代碼中沒有列舉permute方法的具體實現(xiàn)，對此感興趣的開發(fā)者請移步：ArrayOfStrings.ts
八皇后問題
在一個8*8的棋盤上放置八個皇后，使得它們彼此之間不會互相攻擊（即不在同一行、同一列或同一對角線上），總共有多少種擺法？如下圖所示列舉了其中一種擺法：
iShot_2023-06-26_11.40.41
實現(xiàn)思路
分析題目后 ，我們知道了兩個皇后不能處在同一行，那么肯定是每個皇后獨占一行。那我們就先把皇后定義出來，用一個數(shù)組來表示皇后在棋盤上的列號，分別用0～7（棋盤上有8個皇后）對這個數(shù)組進(jìn)行初始化。
棋盤上每一行所放置的皇后，它都可以放在這一行的任意位置。很顯然，這也需要用到全排列求出它的所有放置組合。因為我們用的不同數(shù)字對數(shù)組進(jìn)行的初始化，所以任意兩個皇后肯定不同列。
因此，我們只需要判斷每一組排列對應(yīng)的8個皇后是不是在同一條對角線上，即：對于數(shù)組的兩個下標(biāo)i和j，是否有i-j === queens[i] - queens[j] || j-i === queens[j] - queens[i]，這個問題就得到了解決。
我們來寫一下實現(xiàn)思路：
- 定義皇后數(shù)組，分別用0～7對這個數(shù)組進(jìn)行初始化
- 求出這個數(shù)組的所有排列
- 遍歷所有排列，判斷每一個排列是否滿足不在同一對角線的條件
- 遍歷滿足條件的排列，對棋盤進(jìn)行填充（將皇后放置在棋盤上）
實現(xiàn)代碼
我們將上述思路轉(zhuǎn)換為代碼，如下所示：
public eightQueens(): Array>> {
const queens = [0, 1, 2, 3, 4, 5, 6, 7];
const solutions: Array>> = [];
// 獲取所有組合
const list = this.permute(queens.join(""));
for (let i = 0; i < list.length; i++) {
// 求出的組合中元素值為string類型的，這里需要將其轉(zhuǎn)為number類型
const item: Array = [];
for (let j = 0; j < list[i].length; j++) {
item.push(+list[i][j]);
}
// 不在對角線上
if (this.isValidPlacement(item)) {
const solution: Array> = [];
// 遍歷此組合，取出皇后的擺放位置
for (let j = 0; j < item.length; j++) {
const col = item[j];
const row: Array = Array(8).fill(0);
row[col] = 1;
solution.push(row);
}
solutions.push(solution);
}
}
return solutions;
}
/**
* 判斷當(dāng)前組合是否滿足排列要求（不在對角線上）
* @param queens
* @private
*/
private isValidPlacement(queens: Array) {
for (let i = 0; i < queens.length; i++) {
for (let j = i + 1; j < queens.length; j++) {
if (Math.abs(queens[i] - queens[j]) === Math.abs(i - j)) {
// 在對角線上
return false;
}
}
}
return true;
} 測試用例
我們用一個例子來校驗下上述代碼能否正常執(zhí)行。
const arrayOfStrings = new ArrayOfStrings();
console.log(
"能否構(gòu)成正方體",
arrayOfStrings.isCubePossible([1, 2, 3, 4, 5, 6, 7, 8])
);
console.log("八皇后問題有", arrayOfStrings.eightQueens().length, "種擺法");
示例代碼
本文用到的代碼完整版請移步：
- ArrayOfStrings.ts
- ArrayOfStrings-test.ts
當(dāng)前名稱：全排列的應(yīng)用：正方體的組成與八皇后
分享網(wǎng)址：http://www.5511xx.com/article/cccijcs.html
