前言
持续更新了
正文
问题来源
本问题来自leetcode上的679题。
问题描述
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 * ，/，+，-，(，) 的运算得到 24。
示例 1:
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:
输入: [1, 2, 1, 2]
输出: False
分析：
第一步：先对数组进行全排列，得到数组[a, b, c, d]，一共有24种可能（当然如果有重复数，排列数会变少）； 第二步：处理四个数，此时 a、b、c、d 都可以代表原先数组中的任意数，称之为 a、b、c、d 等价。所以选出 a、b 相当于选出任意两数，对这两数采用四种运算后得到三个数 a（由原先的 a、b 计算得出）、b、c，其中 a 与 b、c 不等价； 第三步：处理三个数，由于 a 和 b(c) 不等价，有两种情况：a 和 b(c) 运算；b 和 c 运算； 第四步：处理两个数，a 和 b 不等价。 具体的，如果运算两个数，a 和 b 等价，则只需要考虑四种情况：
a - b a + b a * b a / b 如果 a 和 b 不等价，还需要多考虑两种情况： b - a b / a
func judgePoint24(nums []int) bool {
return backtrack(nums, 0)
}
// 第一步：求出所有排列，一一验证
func backtrack(nums []int, t int) bool {
if t == 4 {
return judge4(float64(nums[0]), float64(nums[1]), float64(nums[2]), float64(nums[3]))
}
for i := t; i < 4; i++ {
nums[i], nums[t] = nums[t], nums[i]
if backtrack(nums, t+1) {
return true
}
nums[i], nums[t] = nums[t], nums[i]
}
return false
}
// 第二步：由于已经全排列，a、b、c、d 都是等价的，利用四种运算符选出三个数继续
func judge4(a, b, c, d float64) bool {
return judge3(a+b, c, d) ||
judge3(a-b, c, d) ||
judge3(a*b, c, d) ||
judge3(a/b, c, d)
}
// 第三步：a 是有两个数组成的，b、c 只表示一个数，等价
func judge3(a, b, c float64) bool {
// 第三步：a 是有两个数组成的，b、c 只表示一个数，等价
return judge2(a+b, c) ||
judge2(a-b, c) ||
judge2(a*b, c) ||
judge2(a/b, c) ||
judge2(b/a, c) ||
judge2(b-a, c) ||
// 情况二：b 和 c 组合
judge2(a, b+c) ||
judge2(a, b-c) ||
judge2(a, b*c) ||
judge2(a, b/c)
}
// 第四步：a 和 b 不等价
func judge2(a, b float64) bool {
return math.Abs(a + b - 24) < 0.001 ||
math.Abs(a - b - 24) < 0.001 ||
math.Abs(a * b - 24) < 0.001 ||
math.Abs(a / b - 24) < 0.001 ||
math.Abs(b - a - 24) < 0.001 ||
math.Abs(b / a - 24) < 0.001
}
作者：lil-q 链接：https://leetcode-cn.com/problems/24-game/solution/java-li-yong-quan-pai-lie-by-lil-q/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结：
勤思考。
结语
不管怎么样好好加油。
