基于JS实现计算24点算法代码实例解析

前言

  休息的时候无意间看到群里有人发出了华为的校招题,一开始看题目的时候觉得很简单,于是晚上就试着写了一下,结果写的过程中打脸,不断的整理逻辑不断的重写,但我的性格又是不做出来晚上睡不好的那种,于是在做出来的时候就分享给大家(快凌晨三点了有木有,这校招题难度都达到这级别了?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++),之所以二维数组去重也是封装的方法可能出现多个数组重复的情况,要知道每多一个数组,底层是用递归查询一遍,浏览器会非常卡;

  最后就是我在代码中提到的优化方法,有兴趣的小伙伴可以去试一下,代码还有优化的空间。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • javascript将扁平的数据转为树形结构的高效率算法

    当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多个for循环嵌套,但是这样做有一些缺点,那就是效率太低.而且有多少层就需要嵌套几个for循环,不好用. 我实现了用O(n)级算法将 一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构. 一位数组中每一个元素必须要包含以下属性: 拥有一个唯一的id 拥有一个parent_id, 这个id指向它父级的id 其他则为每一个元素中的一些信息,我这里是菜单,就有菜单的名称和url信息. 注: 在层级结构中,第一层的par

  • JS中的算法与数据结构之集合(Set)实例详解

    本文实例讲述了JS中的算法与数据结构之集合(Set).分享给大家供大家参考,具体如下: 集合(Set) 同数学中所学的一样,集合(Set)是由一组无序但彼此之间又有一定关系性的成员构成,每个成员在集合中只能出现一次,不同于我们之前说的字典,链表之类的,它是一种包含了不同元素的数据结构(集合中的元素称为成员),从其定义中我们可以看出它具有两个很重要的特征:首先,集合中的成员是无序的,其次,集合中的成员是不相同的,即集合中不存在相同的成员. 实际上,很多编程语言中,集合并不是一种数据类型,但是如果你

  • JS求解两数之和算法详解

    本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法 利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num

  • JS中的算法与数据结构之字典(Dictionary)实例详解

    本文实例讲述了JS中的算法与数据结构之字典(Dictionary).分享给大家供大家参考,具体如下: 字典(Dictionary) 字典(Dictionary)是一种以 键-值对 形式存储数据的数据结构 ,就如同我们平时查看通讯录一样,要找一个电话,首先先找到该号码的机主名字,名字找到了,紧接着电话号码也就有了.这里的键就是你用来查找的东西,本例中指代的就是名字,值就是查找得到的结果,也就是对应的电话号码. 其实,JavaScript 中的 Object 类就是以字典的形式设计的,下面我们将会借

  • JS实现的冒泡排序,快速排序,插入排序算法示例

    本文实例讲述了JS实现的冒泡排序,快速排序,插入排序算法.分享给大家供大家参考,具体如下: 一.冒泡排序 大致分两步: 1.依次对比相邻2个数字,前者比后者大就调换位置 2.重复第一步操作,直到所有数字都按顺序排列 function bubbleSort(arr){ for(var i=1; i<arr.length; i++){ for(var j=0; j<arr.length-i; j++){ if(arr[j]>arr[j+1]){ arr[j]=[arr[j+1],arr[j+

  • js贪心算法 钱币找零问题代码实例

    给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量. 例如,美国硬币面额有1.5.10.25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分.1个10美分和1个10美分共三个硬币.这个算法要解决的就是诸如此类的问题.我们来看看如何用动态规划的方式来解决. 对于每一种面额,我们都分别计算所需要的硬币数量.具体算法如下: 如果全部用1美分的硬币,一共需要36个硬币 如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币 如果用10美

  • js实现无限层级树形数据结构(创新算法)

    由于做项目的需要,把一个线性数组转成树形数组,在网上查了很多文章,觉得他们写的太复杂了,于是自己写了一个,在折腾了一下午终于把它写出来啦(激动.gif),用两个filter过滤器就搞定了,代码简洁明了,数据结构小白都能看懂. js代码:把扁平数据转成树形数据 function setTreeData(source){ let cloneData = JSON.parse(JSON.stringify(source)) // 对源数据深度克隆 return cloneData.filter(fat

  • 基于JS实现计算24点算法代码实例解析

    前言 休息的时候无意间看到群里有人发出了华为的校招题,一开始看题目的时候觉得很简单,于是晚上就试着写了一下,结果写的过程中打脸,不断的整理逻辑不断的重写,但我的性格又是不做出来晚上睡不好的那种,于是在做出来的时候就分享给大家(快凌晨三点了有木有,这校招题难度都达到这级别了?o(╥﹏╥)o) 题目描述 审题要注意:1+2+3*4是前面三个已经相加为6再乘4,没有括号!! 代码: <!DOCTYPE html> <html lang="en"> <head&g

  • 基于js实现抽红包并分配代码实例

    这篇文章主要介绍了基于js实现抽红包并分配代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 将 50000元随机分给10个人,其中3个人必须分到百位数,4个人分到千位数,3个人分到万位数,每个人所得金额 <!DOCTYPE html> <html lang="zh"> <head> <meta charset="UTF-8" /> <meta name=&

  • 基于js实现逐步显示文字输出代码实例

    今天清理chrome书签,突然就点到了一个关于 知乎五周年的网页,这帮程序员的脑子真有趣,就算是保存一年后再看也还是觉得好有趣,下边是一个截图图片描述 这个网页展示了一个类似ide接口的小窗口,文字逐步输入,并且还伴随一些有点炫的css动画,为个人生成专属数据.当然这个展示还包括了其他一些数据的传输啦,特殊效果(类似触发一个标签的js回调啦),css那个一堆波浪的动画啦等等一些有意思的,这些暂时不管,我们今天就来看看这个逐步显示的文字是怎么做到的,我首先想到的就是做一个简单的demo 由于没有读

  • Python实现Canny及Hough算法代码实例解析

    任务说明:编写一个钱币定位系统,其不仅能够检测出输入图像中各个钱币的边缘,同时,还能给出各个钱币的圆心坐标与半径. 效果 代码实现 Canny边缘检测: # Author: Ji Qiu (BUPT) # filename: my_canny.py import cv2 import numpy as np class Canny: def __init__(self, Guassian_kernal_size, img, HT_high_threshold, HT_low_threshold)

  • Java编程实现基于用户的协同过滤推荐算法代码示例

    协同过滤简单来说是利用某兴趣相投.拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要. 协同过滤又可分为评比(rating)或者群体过滤(social filtering)协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热 UserCF的核心思想即为根据用户数据模拟向量相似度,我们根据这个相似度,来找出指定用户的相似用户,然后将相似用

  • js图数据结构处理 迪杰斯特拉算法代码实例

    这篇文章主要介绍了js图数据结构处理 迪杰斯特拉算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /*//1.确定数据结构, mapf[i][j] 为点i到点j的距离 [ Infinity 2 5 Infinity Infinity Infinity Infinity 2 6 Infinity Infinity Infinity Infinity 7 1 Infinity Infinity 2 Infinity 4 Infinity

  • 基于JS实现新闻列表无缝向上滚动实例代码

    当新闻较多,并且空前有限的时候,使用滚动是一个不错的选择,本章节就通过代码实例介绍一下如何实现此效果. 代码实例如下: <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <meta name="author" content="http://www.jb51.net/" /> <title>文字列表无缝向上滚动代码<

  • 基于JS实现无缝滚动思路及代码分享

    原理: 1.给ul一个绝对定位使其脱离文档流,left设置为0,把图片塞进ul里,编写一个"移动"函数,函数功能能够使ul的left以一个正速度向右跑动, 2.设置一个定时器,让"移动"函数每30(参数可变)毫秒执行一次 3.因为ul的长度会"跑"完,此时可以使ul的content也就是img增加一倍, oUl.innerHTML +=oUl.innerHTML; 4.此时因为ul的content增加,其width也会随着增大,根据实际项目展示图

  • 基于javascript实现获取最短路径算法代码实例

    这篇文章主要介绍了基于javascript实现获取最短路径算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 //A算法 自动寻路 路径 class GetAutoPath{ constructor(id, map, sPos, ePos, mapArr){ //this.type = id.type; this.id = id; this.map = map; this.sPos = sPos; this.ePos = eP

  • 基于JS实现父组件的请求服务过程解析

    这篇文章主要介绍了基于JS实现父组件的请求服务过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 <template> <div class = 'car_list' reft='scrollobx' @scroll='scrollready($event)'> </div> </template> <script> export default { data() { return { le

随机推荐