基于JS实现计算24点算法代码实例解析
更新时间：2020年7月23日 12:58 点击：2251
前言
休息的时候无意间看到群里有人发出了华为的校招题，一开始看题目的时候觉得很简单，于是晚上就试着写了一下，结果写的过程中打脸，不断的整理逻辑不断的重写，但我的性格又是不做出来晚上睡不好的那种，于是在做出来的时候就分享给大家(快凌晨三点了有木有，这校招题难度都达到这级别了？o(╥﹏╥)o)
题目描述
审题要注意：1+2+3*4是前面三个已经相加为6再乘4，没有括号！！
代码：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>21点</title>
<script>
// 牌和对应的权重
const pokerBox = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"];//下标+1刚好就是对应的分值
let calcSym = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];//0,1,2 3,4 5,6,7 8,9分别对应+-*/
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";//回复的字符串 默认回复NONE，表示无解
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)} ${d} = ${sum}`;
return sum;
}
// 全排列
//这里的全排序就是把原先的数组复制一个出来，然后新数组代替原先数组删除该值，temp数组添加该值，当新数组的长度为0，说明转移完成，就把temp数组放入matrix数组中
function permutation(pokers) {
let matrix = [];
const subFunc = (arr, temp) => {
if (temp.length > 4) temp.length = 4;//为了避免过长
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;
};
// 计算总数为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;//第一次判断如果符合就不需要执行下面的循环了
let i = 1;//上面判断了一次，因此这里从1开始
if (calcSym.length <= 10) calcSym = [...new Set(permutation(calcSym).flatMap(item=>item.join()))].map(item=>item.split(","));//二维数组去重,并获取全排的数组(即每一种可能性)
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;//如果数组遍历完都没
};
return false;
}
function init() {
if (calcSym.length === 12) calcSym = permutation(calcSym);//获取全排的数组(即每一种可能性)
}
init();//初始化就立即执行
// 对输入的数字进行一次全排
function calcNumber(arr) {
if (Count24(arr[0], arr[1], arr[2], arr[3])) return true;//这一步满足那么下面就不用执行permutation了，因为底层是递归，很消耗性能
let i = 1;
if (arr.length <= 4) arr = [...new Set(permutation(arr).flatMap(item=>item.join()))].map(item=>item.split(","));//二维数组去重
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";
}
// 当我输入完光标离开的时候就开始判断并计算
function pokers(event) {
let arr = event.value.trim().split(" ");
if (arr.length > 4) {
arr.length = 4;
document.getElementById("poker").value = arr.join(' ');
alert("您输入的牌数大于4张，这边自动帮您删除");
}
if (arr.some(item => !pokerBox.includes(item))) alert("ERROR");
else {
let arrNew = arr.map(item => { return pokerBox.indexOf(item) + 1 });//计算权重
calcNumber(arrNew);//执行计算
}
}
function dialog() { alert(answer) };
</script>
</head>
<body>
<!-- 这里设置为失去焦点就开始计算是为了尽量减少用户等待的时间，但注意不要设置为输入就开始计算，否则浏览器会卡到崩溃 -->
<!-- 由于是遍历数组获取结果，如果用户输入的值不为24，那么系统会查询的很慢，这个时候的优化方案有：
一、每次用户输入的值和对应的回复保存在一个数组内，下次用户输入时先判断是否在该数组内，不在的时候再执行计算
二、我们可以先排除一部分不可能的值放入数组，比如用户输入2 2 2 2或A A A A,这种怎么算都不可能为24，如果用户输入的为这一类就直接Pass
三、先把最耗时的calcSym数组的全排改为用户一进入页面就先异步加载计算 -->
<input type="text" onblur="pokers(this)" name="21" id="poker">
<input type="button" onclick="dialog()" value="confirm" />
</body>
</html>
实现的效果：
总结思路：
题目第一眼看到就应该想到递归，之前我是把加减乘除都设为一个方法，想采用面向切面的方式进行计算，但是这种方式逻辑复杂且无法计算复杂一点的公式，因此就改为直接把所有可能出现的结果都拿出来一一比对，只要其中一个为24就终止循环，否则循环结束之后返回NONE;
calcSym=[0,1,2,3,4,5,6,7,8,9];//0,1,23,45,6,78,9分别对应+-*/,这里为三个+，两个-，三个*，两个除，大家可以推理得出，6+6+6+6，1*2*3*4，2*13-1-1，13*13/13+11等等，除号和减号最多只可能有两个，而加号和乘号最多可以为三个；
至于全排列方法permutation，是借鉴了STL的next_permutation函数(C++)，之所以二维数组去重也是封装的方法可能出现多个数组重复的情况，要知道每多一个数组，底层是用递归查询一遍，浏览器会非常卡；
最后就是我在代码中提到的优化方法，有兴趣的小伙伴可以去试一下，代码还有优化的空间。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持猪先飞。
相关文章
- 作者：Sabine 【导读】本文介绍了C#的四种排序算法：冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System； namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法，文中代码非常详细，帮助大家更好的参考和学习，感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了js如何实现浏览器打印功能，文中示例代码非常详细，帮助大家更好的理解和学习，感兴趣的朋友可以了解下...2020-07-15
- 本篇文章主要分享了通过window.navigator来判断浏览器及其版本信息的实例代码。具有一定的参考价值，下面跟着小编一起来看下吧...2017-01-23
- 这篇文章主要给大家介绍了关于Nest.js参数校验和自定义返回数据格式的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-03-28
- 这篇文章主要介绍了js实现调用网络摄像头及常见错误处理，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-03-07
- 下面小编就为大家带来一篇利用JS实现点击按钮后图片自动切换的简单方法。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2016-10-25
- 这篇文章主要为大家详细介绍了JS实现随机生成验证码，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2021-09-06
- 作为前端，一直以来都知道HTTP劫持与XSS跨站脚本、CSRF跨站请求伪造。防御这些劫持最好的方法是从后端入手，前端能做的太少。而且由于源码的暴露，攻击者很容易绕过防御手段。但这不代表我们去了解这块的相关知识是没意义的，本文的许多方法，用在其他方面也是大有作用。...2021-05-24
- 这篇文章主要介绍了js组件SlotMachine实现图片切换效果制作抽奖系统的相关资料,需要的朋友可以参考下...2016-04-19
- 这篇文章主要介绍了基于JavaScript实现文字超出部分隐藏 的相关资料,需要的朋友可以参考下...2016-03-01
- 这篇文章主要为大家详细介绍了js实现列表按字母排序，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-08-11
- 本文给大家介绍的是nodejs实现使用阿里大鱼短信API发送消息的方法和代码，有需要的小伙伴可以参考下。...2016-01-20
- 这篇文章主要介绍了JS实现响应鼠标点击动画渐变弹出层效果代码,具有非常自然流畅的动画过度效果,涉及JavaScript针对鼠标事件的响应及页面元素样式的动态操作相关技巧,需要的朋友可以参考下...2016-03-28
- Vue.js通过简洁的API提供高效的数据绑定和灵活的组件系统.这篇文章主要介绍了vue.js 表格分页ajax 异步加载数据的相关资料,需要的朋友可以参考下...2016-10-20
- 这次文章要给大家介绍的是node.JS md5加密中文与php结果不一致怎么办，不知道具体解决办法的下面跟小编一起来看看。 因项目需要，需要Node.js与PHP做接口调用，发现nod...2017-07-06
- 系统的学习了一下angularjs，发现angularjs的有些思想根php的模块smarty很像，例如数据绑定，filter。如果对smarty比较熟悉的话，学习angularjs会比较容易一点,这篇文章给大家介绍angularjs filter用法详解，感兴趣的朋友一起学习吧...2015-12-29
- 使用require('crypto')调用加密模块。加密模块需要底层系统提供OpenSSL的支持。它提供了一种安全凭证的封装方式，可以用于HTTPS安全网络以及普通HTTP连接。该模块还提供了一套针对OpenSSL的hash（哈希），hmac（密钥哈希），cipher...2014-06-07
- 这篇文章主要教大家如何利用Bootstrap3制作图片轮播效果，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2016-05-14
- 这篇文章主要介绍了Nodejs回调加超时限制两种实现方法的相关资料,需要的朋友可以参考下...2017-06-15