英文原文
You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.
You are restricted with the following rules:
- The division operator
'/'represents real division, not integer division.<ul> <li>For example, <code>4 / (1 - 2 / 3) = 4 / (1 / 3) = 12</code>.</li> </ul> </li> <li>Every operation done is between two numbers. In particular, we cannot use <code>'-'</code> as a unary operator. <ul> <li>For example, if <code>cards = [1, 1, 1, 1]</code>, the expression <code>"-1 - 1 - 1 - 1"</code> is <strong>not allowed</strong>.</li> </ul> </li> <li>You cannot concatenate numbers together <ul> <li>For example, if <code>cards = [1, 2, 1, 2]</code>, the expression <code>"12 + 12"</code> is not valid.</li> </ul> </li>
Return true if you can get such expression that evaluates to 24, and false otherwise.
Example 1:
Input: cards = [4,1,8,7] Output: true Explanation: (8-4) * (7-1) = 24
Example 2:
Input: cards = [1,2,1,2] Output: false
Constraints:
cards.length == 41 <= cards[i] <= 9
中文题目
你有 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 。
通过代码
高赞题解
思路
游戏的第一步是挑出两个数，算出一个新数替代这两个数。
然后，在三个数中玩 24 点，再挑出两个数，算出一个数替代它们。
然后，在两个数中玩 24 点……
很明显的递归思路。每次递归都会挑出两个数，我们尝试挑出不同的两数组合：
- 挑 1、2，基于它，继续递归。
- 挑 1、3，基于它，继续递归。
- 挑 ……
即通过两层 for 循环，枚举所有的两数组合，展开出不同选择所对应的递归分支。
挑出的每一对数，我们…
- 枚举出所有可能的运算操作：加减乘除…——（对应不同的递归调用）
- 逐个尝试每一种运算——（选择进入一个递归分支）
- 传入长度变小的新数组继续递归——（递归计算子问题）
- 当递归到只剩一个数——（到达了递归树的底部），看看是不是 24 。
- 是就返回 true——结束当前递归，并且控制它不进入别的递归分支，整个结束掉。
- 否则返回 false，离开错误的分支，进入别的递归分支，尝试别的运算。
剪枝小技巧
当递归返回 true，代表游戏成功，不用继续探索了，剩下的搜索分支全部砍掉。怎么做到？
- 标识变量
isValid初始为 false，默认会执行||后面的递归。代码如下。 - 一旦某个递归返回真，
isValid就变为真，由于||的短路特性，后面的递归不会执行。 - 所有递归子调用都这么写，
isValid就像一个开关，避免写很多判断语句。isValid = isValid || judgePoint24([...newNums, n1 + n2]); isValid = isValid || judgePoint24([...newNums, n1 - n2]); isValid = isValid || judgePoint24([...newNums, n2 - n1]); isValid = isValid || judgePoint24([...newNums, n1 * n2]); // ...
代码
[]const judgePoint24 = (nums) => { const len = nums.length; if (len == 1) { // 递归的出口 return Math.abs(nums[0] - 24) < 1e-9; } let isValid = false; // 用于控制是否进入递归 for (let i = 0; i < len; i++) { // 两层循环，枚举出所有的两数组合 for (let j = i + 1; j < len; j++) { const n1 = nums[i]; const n2 = nums[j]; // 选出的两个数 n1 n2 const newNums = []; // 存放剩下的两个数 for (let k = 0; k < len; k++) { if (k != i && k != j) { // 剔除掉选出的两个数 newNums.push(nums[k]); } } // 加 isValid = isValid || judgePoint24([...newNums, n1 + n2]); // 减与被减 isValid = isValid || judgePoint24([...newNums, n1 - n2]); isValid = isValid || judgePoint24([...newNums, n2 - n1]); // 乘 isValid = isValid || judgePoint24([...newNums, n1 * n2]); if (n2 !== 0) { // 除 isValid = isValid || judgePoint24([...newNums, n1 / n2]); } if (n1 !== 0) { // 被除 isValid = isValid || judgePoint24([...newNums, n2 / n1]); } if (isValid) { return true; } } } return false; // 遍历结束，始终没有返回真，则返回false };
[]func judgePoint24(nums []int) bool { floatNums := make([]float64, len(nums)) for i := range floatNums { floatNums[i] = float64(nums[i]) } return dfs(floatNums) } func dfs(nums []float64) bool { if len(nums) == 1 { return math.Abs(nums[0]-24) < 1e-9 } flag := false for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { n1, n2 := nums[i], nums[j] newNums := make([]float64, 0, len(nums)) for k := 0; k < len(nums); k++ { if k != i && k != j { newNums = append(newNums, nums[k]) } } flag = flag || dfs(append(newNums, n1+n2)) flag = flag || dfs(append(newNums, n1-n2)) flag = flag || dfs(append(newNums, n2-n1)) flag = flag || dfs(append(newNums, n1*n2)) if n1 != 0 { flag = flag || dfs(append(newNums, n2/n1)) } if n2 != 0 { flag = flag || dfs(append(newNums, n1/n2)) } if flag { return true } } } return false }
执行情况
Runtime: 68 ms, faster than 100.00% of JavaScript online submissions for 24 Game.
Runtime: 0 ms, faster than 100.00% of Go online submissions for 24 Game.
感谢阅读，文字经过反复修改打磨，希望你能感受到这份真诚。欢迎提出建议。
最后修改于：2021-08-30
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 26859 | 49680 | 54.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
