You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

24点游戏。

题目就是题意，给你4个数字，请你判断这4个数字是否能算出24。思路是DFS，但是实现起来不是特别直观。同时注意到，因为四则运算里面有除法，会涉及到精度的关系，所以我做的时候先直接把所有的数字变成double。然后我创建了一个helper函数来处理具体的计算问题。首先需要两个for loop来找出前两个数字，然后对第三个数字x和第四个数字y的组合做四则运算，包括

• x + y
• x - y
• y - x
• x * y
• x / y
• y / x

这六种结果再返回给helper函数的上一层，看看不同组合的计算结果是否能算出24。

时间O(1) - 有限种计算结果

空间O(n)

Java实现

 1 class Solution {
 2     public boolean judgePoint24(int[] nums) {
 3         double[] input = new double[] { nums[0], nums[1], nums[2], nums[3] };
 4         return helper(input);
 5     }
 6 
 7     private boolean helper(double[] a) {
 8         // base case
 9         if (a.length == 1) {
10             return Math.abs(24 - a[0]) < 0.001;
11         }
12         // normal case
13         for (int i = 0; i < a.length; i++) {
14             for (int j = i + 1; j < a.length; j++) {
15                 // 一开始是4个数字，for loop是在循环遍历前两个
16                 // d数组的长度是3，是需要拿出来后两个，同时需要一个位置记录前两个数字运算的结果
17                 double[] d = new double[a.length - 1];
18                 int index = 0;
19                 for (int k = 0; k < a.length; k++) {
20                     if (k != i && k != j) {
21                         d[index++] = a[k];
22                     }
23                 }
24                 for (double num : compute(a[i], a[j])) {
25                     d[d.length - 1] = num;
26                     if (helper(d)) {
27                         return true;
28                     }
29                 }
30             }
31         }
32         return false;
33     }
34 
35     private double[] compute(double x, double y) {
36         return new double[] { x + y, x - y, y - x, x * y, x / y, y / x };
37     }
38 }

 

LeetCode 题目总结