快捷導(dǎo)航

基于JS實(shí)現(xiàn)計(jì)算24點(diǎn)算法代碼實(shí)例解析

更新時(shí)間：2020年07月23日 10:28:44 作者：Tom最好的朋友是Jerry

這篇文章主要介紹了基于JS實(shí)現(xiàn)計(jì)算24點(diǎn)算法代碼實(shí)例解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

前言

　　休息的時(shí)候無(wú)意間看到群里有人發(fā)出了華為的校招題，一開始看題目的時(shí)候覺(jué)得很簡(jiǎn)單，于是晚上就試著寫了一下，結(jié)果寫的過(guò)程中打臉，不斷的整理邏輯不斷的重寫，但我的性格又是不做出來(lái)晚上睡不好的那種，于是在做出來(lái)的時(shí)候就分享給大家(快凌晨三點(diǎn)了有木有，這校招題難度都達(dá)到這級(jí)別了？o(╥﹏╥)o)

題目描述

審題要注意：1+2+3*4是前面三個(gè)已經(jīng)相加為6再乘4，沒(méi)有括號(hào)?。?/p>

代碼：

<!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)} $ ${filter(C2)} ${c} ${filter(C3)} $vvxyksv9kd = ${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開始
    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;//這一步滿足那么下面就不用執(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)離開的時(shí)候就開始判斷并計(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)就開始計(jì)算是為了盡量減少用戶等待的時(shí)間，但注意不要設(shè)置為輸入就開始計(jì)算，否則瀏覽器會(huì)卡到崩潰 -->
 <!-- 由于是遍歷數(shù)組獲取結(jié)果，如果用戶輸入的值不為24，那么系統(tǒng)會(huì)查詢的很慢，這個(gè)時(shí)候的優(yōu)化方案有：
 一、每次用戶輸入的值和對(duì)應(yīng)的回復(fù)保存在一個(gè)數(shù)組內(nèi)，下次用戶輸入時(shí)先判斷是否在該數(shù)組內(nèi)，不在的時(shí)候再執(zhí)行計(jì)算
 二、我們可以先排除一部分不可能的值放入數(shù)組，比如用戶輸入2 2 2 2或A A A A,這種怎么算都不可能為24，如果用戶輸入的為這一類就直接Pass
 三、先把最耗時(shí)的calcSym數(shù)組的全排改為用戶一進(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ù)組，底層是用遞歸查詢一遍，瀏覽器會(huì)非常卡；

　　最后就是我在代碼中提到的優(yōu)化方法，有興趣的小伙伴可以去試一下，代碼還有優(yōu)化的空間。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: