[LeetCode] 679. 24 Game

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 题目总结

上一篇:【渝粤题库】国家开放大学2021春1050金融理论前沿课题题目


下一篇:SpringBoot集成邮件发送