专栏首页小浩算法漫画:骚操作系列(一文让你学会如何用代码判断"24"点)

漫画:骚操作系列(一文让你学会如何用代码判断"24"点)

24点”是一种数学游戏,正如象棋、围棋一样是一种人们喜闻乐见的娱乐活动。它始于何年何月已无从考究,但它以自己独具的数学魅力和丰富的内涵正逐渐被越来越多的人们所接受。今天就为大家分享一道关于“24点”的算法题目。

话不多说,直接看题。

01 第679题:24点(困难题目)

第679题:你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到 24。

示例 1:

输入: [4, 1, 8, 7]

输出: True

解释: (8-4) * (7-1) = 24

示例 2:

输入: [1, 2, 1, 2]

输出: False

注意:

除法运算符 / 表示实数除法,而不是整数除法。例如 4 / (1 - 2/3) = 12 。

每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如,[1, 1, 1, 1] 作为输入时,表达式 -1 - 1 - 1 - 1 是不允许的。

你不能将数字连接在一起。例如,输入为 [1, 2, 1, 2] 时,不能写成 12 + 12 。

02 题目分析

拿到题目,第一反应就可以想到暴力求解如果我们要判断给出的4张牌是否可以通过组合得到24,那我们只需找出所有的可组合的方式进行遍历。

4个数字,3个操作符,外加括号,基本目测就能想到组合数不会大到超出边界。所以,我们只要把他们统统列出来,不就可以进行求解了吗?说干就干!

我们首先定义个方法,用来判断两个数的的所有操作符组合是否可以得到24

func judgePoint24_2(a, b float64) bool {
    return a+b == 24 || a*b == 24 || a-b == 24 || b-a == 24 || a/b == 24 || b/a == 24 
}

但是这个方法写的正确吗?其实不对!因为在计算机中,实数在计算和存储过程中会有一些微小的误差,对于一些与零作比较的语句来说,有时会因误差而导致原本是等于零但结果却小于或大于零之类的情况发生,所以常用一个很小的数 1e-6 代替 0,进行判读!

(1e-6:表示1乘以10的负6次方。Math.abs(x)<1e-6 其实相当于x==0。1e-6(也就是0.000001)叫做epslon,用来抵消浮点运算中因为误差造成的相等无法判断的情况。这个知识点需要掌握!)

举个例子:

func main() {
    var a float64
    var b float64
    b = 2.0
    //math.Sqrt:开平方根
    c := math.Sqrt(2)
    a = b - c*c
    fmt.Println(a == 0)                  //false
    fmt.Println(a < 1e-6 && a > -(1e-6)) //true
}

这里直接用 a==0 就会得到false,但是通过 a < 1e-6 && a > -(1e-6) 却可以进行准确的判断。

所以我们将上面的方法改写:

//go语言
//judgePoint24_2:判断两个数的所有操作符组合是否可以得到24
func judgePoint24_2(a, b float64) bool {
    return (a+b < 24+1e-6 && a+b > 24-1e-6) ||
        (a*b < 24+1e-6 && a*b > 24-1e-6) ||
        (a-b < 24+1e-6 && a-b > 24-1e-6) ||
        (b-a < 24+1e-6 && b-a > 24-1e-6) ||
        (a/b < 24+1e-6 && a/b > 24-1e-6) ||
        (b/a < 24+1e-6 && b/a > 24-1e-6) 
}

完善了通过两个数来判断是否可以得到24的方法,现在我们加一个判断三个数是否可以得到24的方法。

//硬核代码,不服来辩!
func judgePoint24_3(a, b, c float64) bool {
    return judgePoint24_2(a+b, c) ||
        judgePoint24_2(a-b, c) ||
        judgePoint24_2(a*b, c) ||
        judgePoint24_2(a/b, c) ||
        judgePoint24_2(b-a, c) ||
        judgePoint24_2(b/a, c) ||

        judgePoint24_2(a+c, b) ||
        judgePoint24_2(a-c, b) ||
        judgePoint24_2(a*c, b) ||
        judgePoint24_2(a/c, b) ||
        judgePoint24_2(c-a, b) ||
        judgePoint24_2(c/a, b) ||

        judgePoint24_2(c+b, a) ||
        judgePoint24_2(c-b, a) ||
        judgePoint24_2(c*b, a) ||
        judgePoint24_2(c/b, a) ||
        judgePoint24_2(b-c, a) ||
        judgePoint24_2(b/c, a)
}

好了。三个数的也出来了,我们再加一个判断4个数为24点的方法:(排列组合,我想大家都会....)

前方高能!!!

前方高能!!!

前方高能!!!

//硬核代码,不服来辩!
func judgePoint24(nums []int) bool {
    return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0]))
}

03

Go语言示例

搞定收工,我们整合全部代码如下:

//硬核编程...
func judgePoint24(nums []int) bool {
    return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0]))
}

func judgePoint24_3(a, b, c float64) bool {
    return judgePoint24_2(a+b, c) ||
        judgePoint24_2(a-b, c) ||
        judgePoint24_2(a*b, c) ||
        judgePoint24_2(a/b, c) ||
        judgePoint24_2(b-a, c) ||
        judgePoint24_2(b/a, c) ||

        judgePoint24_2(a+c, b) ||
        judgePoint24_2(a-c, b) ||
        judgePoint24_2(a*c, b) ||
        judgePoint24_2(a/c, b) ||
        judgePoint24_2(c-a, b) ||
        judgePoint24_2(c/a, b) ||

        judgePoint24_2(c+b, a) ||
        judgePoint24_2(c-b, a) ||
        judgePoint24_2(c*b, a) ||
        judgePoint24_2(c/b, a) ||
        judgePoint24_2(b-c, a) ||
        judgePoint24_2(b/c, a)
}

func judgePoint24_2(a, b float64) bool {
    return (a+b < 24+1e-6 && a+b > 24-1e-6) ||
        (a*b < 24+1e-6 && a*b > 24-1e-6) ||
        (a-b < 24+1e-6 && a-b > 24-1e-6) ||
        (b-a < 24+1e-6 && b-a > 24-1e-6) ||
        (a/b < 24+1e-6 && a/b > 24-1e-6) ||
        (b/a < 24+1e-6 && b/a > 24-1e-6)
}

由于代码过于硬核

我们直接击败100%的对手:

(没想到吧!代码还可以这么写~)

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过相关语法。算法思想最重要,使用各语言纯属本人爱好。同时,所有代码均在leetcode上进行过测试运行,保证其严谨性!

今天的题目应该都能看懂吧....这可是困难题目哦~

大家还有其他的方法来得到答案吗?

评论区留下你的想法吧!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:原地删除类题型详解(二次修订版)

    题目27:给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

    程序员小浩
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • 一道魔性的贪心题目(随意吐槽)

    假设你是一位很棒(多棒???)的家长,想要给你的孩子们一些小饼干(不能给大饼干吗???)但是,每个孩子最多只能给一块饼干(有毒吧。。。)

    程序员小浩
  • 小浩算法|一文让你学会如何用代码判断"24"点

    “24点”是一种数学游戏,正如象棋、围棋一样是一种人们喜闻乐见的娱乐活动。它始于何年何月已无从考究,但它以自己独具的数学魅力和丰富的内涵正逐渐被越来越多的人们所...

    宜信技术学院
  • 【leetcode刷题】T125-求根到叶子节点数字之和

    https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

    木又AI帮
  • 深度学习——优化器算法Optimizer详解(BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam)

    在机器学习、深度学习中使用的优化算法除了常见的梯度下降,还有 Adadelta,Adagrad,RMSProp 等几种优化器,都是什么呢,又该怎么选择呢? 在 ...

    郭耀华
  • 《Monkey Java》课程4.2之面向对象基础3

    GitOPEN
  • Mrkdown教程

    Markdown是一种轻量级标记语言,它以纯文本形式(易读、易写、易更改)编写文档,并最终以HTML格式发布。 Markdown也可以理解为将以MARKD...

    HcodeBlogger
  • D11-Android自定义控件之动画篇3-插值器与估值器

    张风捷特烈
  • 如何选择优化器 optimizer

    在很多机器学习和深度学习的应用中,我们发现用的最多的优化器是 Adam,为什么呢? 下面是 TensorFlow 中的优化器, https://www.ten...

    杨熹

扫码关注云+社区

领取腾讯云代金券