基于JS實(shí)現(xiàn)計(jì)算24點(diǎn)算法代碼實(shí)例解析
前言
休息的時(shí)候無(wú)意間看到群里有人發(fā)出了華為的校招題，一開(kāi)始看題目的時(shí)候覺(jué)得很簡(jiǎn)單，于是晚上就試著寫(xiě)了一下，結(jié)果寫(xiě)的過(guò)程中打臉，不斷的整理邏輯不斷的重寫(xiě)，但我的性格又是不做出來(lái)晚上睡不好的那種，于是在做出來(lái)的時(shí)候就分享給大家(快凌晨三點(diǎn)了有木有，這校招題難度都達(dá)到這級(jí)別了？o(???)o)
題目描述
審題要注意：1+2+3*4是前面三個(gè)已經(jīng)相加為6再乘4，沒(méi)有括號(hào)！！
代碼：
<!DOCTYPE html><html lang='en'><head> <meta charset='UTF-8'> <meta name='viewport' content='width=device-width, initial-scale=1.0'> <title>21點(diǎn)</title> <script> // 牌和對(duì)應(yīng)的權(quán)重 const pokerBox = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K'];//下標(biāo)+1剛好就是對(duì)應(yīng)的分值 let calcSym = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];//0,1,2 3,4 5,6,7 8,9分別對(duì)應(yīng)+-*/ function Calculate(a, b, c) { if (c <= 2) return a + b; if (c <= 4) return a - b; if (c <= 7) return a * b; if (c <= 9) return a / b; return -1; } function filter(c) { if (c <= 2) return '+'; if (c <= 4) return '-'; if (c <= 7) return '*'; if (c <= 9) return '/'; return; } let answer = 'NONE';//回復(fù)的字符串 默認(rèn)回復(fù)NONE，表示無(wú)解 function Calculate24(a, b, c, d, C1, C2, C3) { let sum = Calculate(Calculate(Calculate(a, b, C1), c, C2), d, C3); if (sum === 24) answer = `公式為：${a} ${filter(C1)} ${b} ${filter(C2)} ${c} ${filter(C3)} $is2tiay = ${sum}`; return sum; } // 全排列 //這里的全排序就是把原先的數(shù)組復(fù)制一個(gè)出來(lái)，然后新數(shù)組代替原先數(shù)組刪除該值，temp數(shù)組添加該值，當(dāng)新數(shù)組的長(zhǎng)度為0，說(shuō)明轉(zhuǎn)移完成，就把temp數(shù)組放入matrix數(shù)組中 function permutation(pokers) { let matrix = []; const subFunc = (arr, temp) => { if (temp.length > 4) temp.length = 4;//為了避免過(guò)長(zhǎng) if (arr.length === 0) matrix.push(temp); arr.forEach((elem, i) => { subFunc([...arr.slice(0, i), ...arr.slice(i + 1)], [...temp, elem]); }); } subFunc(pokers, []); return matrix; }; // 計(jì)算總數(shù)為24 function Count24(a, b, c, d) { calcSym.sort((x, y) => x - y);//升序排序 if (Calculate24(a, b, c, d, calcSym[0], calcSym[1], calcSym[2]) === 24) return true;//第一次判斷如果符合就不需要執(zhí)行下面的循環(huán)了 let i = 1;//上面判斷了一次，因此這里從1開(kāi)始 if (calcSym.length <= 10) calcSym = [...new Set(permutation(calcSym).flatMap(item=>item.join()))].map(item=>item.split(','));//二維數(shù)組去重,并獲取全排的數(shù)組(即每一種可能性) while (true) { if (Calculate24(a, b, c, d, calcSym[i][0], calcSym[i][1], calcSym[i][2]) === 24) return true; if (i < calcSym.length - 1) i++; else return false;//如果數(shù)組遍歷完都沒(méi) }; return false; } function init() { if (calcSym.length === 12) calcSym = permutation(calcSym);//獲取全排的數(shù)組(即每一種可能性) } init();//初始化就立即執(zhí)行 // 對(duì)輸入的數(shù)字進(jìn)行一次全排 function calcNumber(arr) { if (Count24(arr[0], arr[1], arr[2], arr[3])) return true;//這一步滿(mǎn)足那么下面就不用執(zhí)行permutation了，因?yàn)榈讓邮沁f歸，很消耗性能 let i = 1; if (arr.length <= 4) arr = [...new Set(permutation(arr).flatMap(item=>item.join()))].map(item=>item.split(','));//二維數(shù)組去重 if (arr.length > 1) { while (true) { if (Count24(arr[i][0], arr[i][1], arr[i][2], arr[i][3])) return true; if (i < arr.length - 1) i++; else return answer = 'NONE'; } }; return answer = 'NONE'; } // 當(dāng)我輸入完光標(biāo)離開(kāi)的時(shí)候就開(kāi)始判斷并計(jì)算 function pokers(event) { let arr = event.value.trim().split(' '); if (arr.length > 4) { arr.length = 4; document.getElementById('poker').value = arr.join(’ ’); alert('您輸入的牌數(shù)大于4張，這邊自動(dòng)幫您刪除'); } if (arr.some(item => !pokerBox.includes(item))) alert('ERROR'); else { let arrNew = arr.map(item => { return pokerBox.indexOf(item) + 1 });//計(jì)算權(quán)重 calcNumber(arrNew);//執(zhí)行計(jì)算 } } function dialog() { alert(answer) }; </script></head><body> <!-- 這里設(shè)置為失去焦點(diǎn)就開(kāi)始計(jì)算是為了盡量減少用戶(hù)等待的時(shí)間，但注意不要設(shè)置為輸入就開(kāi)始計(jì)算，否則瀏覽器會(huì)卡到崩潰 --> <!-- 由于是遍歷數(shù)組獲取結(jié)果，如果用戶(hù)輸入的值不為24，那么系統(tǒng)會(huì)查詢(xún)的很慢，這個(gè)時(shí)候的優(yōu)化方案有： 一、每次用戶(hù)輸入的值和對(duì)應(yīng)的回復(fù)保存在一個(gè)數(shù)組內(nèi)，下次用戶(hù)輸入時(shí)先判斷是否在該數(shù)組內(nèi)，不在的時(shí)候再執(zhí)行計(jì)算 二、我們可以先排除一部分不可能的值放入數(shù)組，比如用戶(hù)輸入2 2 2 2或A A A A,這種怎么算都不可能為24，如果用戶(hù)輸入的為這一類(lèi)就直接Pass 三、先把最耗時(shí)的calcSym數(shù)組的全排改為用戶(hù)一進(jìn)入頁(yè)面就先異步加載計(jì)算 --> <input type='text' onblur='pokers(this)' name='21' id='poker'> <input type='button' onclick='dialog()' value='confirm' /></body></html>
實(shí)現(xiàn)的效果：
總結(jié)思路：
題目第一眼看到就應(yīng)該想到遞歸，之前我是把加減乘除都設(shè)為一個(gè)方法，想采用面向切面的方式進(jìn)行計(jì)算，但是這種方式邏輯復(fù)雜且無(wú)法計(jì)算復(fù)雜一點(diǎn)的公式，因此就改為直接把所有可能出現(xiàn)的結(jié)果都拿出來(lái)一一比對(duì)，只要其中一個(gè)為24就終止循環(huán)，否則循環(huán)結(jié)束之后返回NONE;
calcSym=[0,1,2,3,4,5,6,7,8,9];//0,1,23,45,6,78,9分別對(duì)應(yīng)+-*/,這里為三個(gè)+，兩個(gè)-，三個(gè)*，兩個(gè)除，大家可以推理得出，6+6+6+6，1*2*3*4，2*13-1-1，13*13/13+11等等，除號(hào)和減號(hào)最多只可能有兩個(gè)，而加號(hào)和乘號(hào)最多可以為三個(gè)；
至于全排列方法permutation，是借鑒了STL的next_permutation函數(shù)(C++)，之所以二維數(shù)組去重也是封裝的方法可能出現(xiàn)多個(gè)數(shù)組重復(fù)的情況，要知道每多一個(gè)數(shù)組，底層是用遞歸查詢(xún)一遍，瀏覽器會(huì)非常卡；
最后就是我在代碼中提到的優(yōu)化方法，有興趣的小伙伴可以去試一下，代碼還有優(yōu)化的空間。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。
相關(guān)文章：
1. PHP循環(huán)與分支知識(shí)點(diǎn)梳理2. ASP基礎(chǔ)入門(mén)第三篇(ASP腳本基礎(chǔ))3. 解析原生JS getComputedStyle4. 無(wú)線(xiàn)標(biāo)記語(yǔ)言(WML)基礎(chǔ)之WMLScript 基礎(chǔ)第1/2頁(yè)5. ASP刪除img標(biāo)簽的style屬性只保留src的正則函數(shù)6. ASP實(shí)現(xiàn)加法驗(yàn)證碼7. 讀大數(shù)據(jù)量的XML文件的讀取問(wèn)題8. css代碼優(yōu)化的12個(gè)技巧9. 利用CSS3新特性創(chuàng)建透明邊框三角10. 前端從瀏覽器的渲染到性能優(yōu)化
網(wǎng)公網(wǎng)安備