LeetCode-679. 24 点游戏
2020-08-22
问题地址
LeetCode679. 24 点游戏
问题描述
规则
你有 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 。
解析
解题思路
根据题目要求，需要计算除法，需要用浮点数，故首先需要将int类型转为double类型；
1. 从转换好的数字中取出两个不同的数分别做四则运算得到结果a；
2. 使用上一步的计算结果a与第三个数做四则运算得到结果b；
3. 使用上一步的计算结果b与第四个数做四则运算得到结果c；
4. 判断结果c是否符合要求；
5. 每次从剩余数中取两个数，进行四则运算，将结果放回原有数字集合中，再次进行递归处理，直到最后剩余一个数字。
复杂度分析
- 时间复杂度，O(1)
- 第一次从四个数中取出2个不同的数，共有A(4,2)=\frac{4!}{(4-2)!}=4×3=12种方法；
- 第二次从三个数种取出2个不同的数，共有A(3,2)=\frac{3!}{(3-2)!}=3×2=6种方法；
- 第三次从两个数种取出2个不同的数，共有A(2,2)=\frac{2!}{(2-2)!}=2×1=2种方法；
- 以上每两个数需做四则运算，故共有n=12×4×6×4×2×4种计算方法。
- 空间复杂度，O(1)，一共有四个数，递归调用的层数最多为 4，存储中间状态的列表中最多包含 4 个元素，因此空间复杂度为常数。
定位问题
- 只需要找出2个数，四则运算结果为24即可；
- 需要主要浮点运算的精度问题；
- $+或×$，符合交换定律，可做判断避免重复计算；
数据操作分析
- 将int类型转为double类型；
- 从四个数中取出两个数做四则运算将得到的结果替换这两个数；
- 从三个数中取出两个数做四则运算将得到的结果替换这两个数；
- 将这两个数做四则运算并查验是等于24；
编码实现
/**
* LeetCode679
*/
public class LeetCode0679_24Game {
static final int TARGET_NUM = 24;
static final double ERROR = 1e-6;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<>();
for (int num : nums
) {
list.add((double) num);
}
return travelsAll(list);
}
private boolean travelsAll(List<Double> list) {
int size = list.size();
if (size == 0) return false;
if (size == 1) return (Math.abs(TARGET_NUM - Math.abs(list.get(0))) < ERROR);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) continue;
List<Double> list2 = new ArrayList<>();
for (int k = 0; k < size; k++) {
if (k == i || k == j) continue;
list2.add(list.get(k));
}
//群举所有运算方式
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) continue;//交换法则
if (k == 0) list2.add(list.get(i) + list.get(j));//+
if (k == 1) list2.add(list.get(i) * list.get(j));//*
if (k == 2) list2.add(list.get(i) - list.get(j));//-
if (k == 3) {
if (Math.abs(list.get(j)) < ERROR) {//0不能做被除数
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (travelsAll(list2)) return true;
list2.remove(list2.size() - 1);
}
}
}
return false;
}
}
官方解法
- 回溯
- 思路：
一共有 4 个数和 4 个运算操作，因此可能性非常有限。一共有多少种可能性呢？- 首先从 4 个数字中有序地选出 2 个数字，共有 4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 3 个数字。
- 然后在剩下的 3 个数字中有序地选出 2 个数字，共有 3×2=6 种选法，并选择 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 2 个数字。
- 最后剩下 2 个数字，有 2 种不同的顺序，并选择 4 种运算操作之一。
- 因此，一共有 12×4×6×4×2×4=9216 种不同的可能性。
- 可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 2 个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，这个数字就是一种可能性的结果，如果结果等于 24，则说明可以通过运算得到 24。如果所有的可能性的结果都不等于 24，则说明无法通过运算得到 24。
- 实现时，有一些细节需要注意。
- 除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10^{−6} 可以认为是相等。
- 进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{−6} 时，可以认为该数字等于 0。
- 还有一个可以优化的点。加法和乘法都满足交换律，因此如果选择的运算操作是加法或乘法，则对于选出的 2 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。
- 复杂度分析：
-
时间复杂度：O(1)。一共有 9216 种可能性，对于每种可能性，各项操作的时间复杂度都是 O(1)，因此总时间复杂度是 O(1)。
-
空间复杂度：O(1)。空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 4 个数，所以递归调用的层数最多为 4，存储中间状态的列表最多包含 4 个元素，因此空间复杂度为常数。
-
class Solution {
static final int TARGET = 24;
static final double EPSILON = 1e-6;
static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return solve(list);
}
public boolean solve(List<Double> list) {
if (list.size() == 0) {
return false;
}
if (list.size() == 1) {
return Math.abs(list.get(0) - TARGET) < EPSILON;
}
int size = list.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
List<Double> list2 = new ArrayList<Double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.add(list.get(k));
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.add(list.get(i) + list.get(j));
} else if (k == MULTIPLY) {
list2.add(list.get(i) * list.get(j));
} else if (k == SUBTRACT) {
list2.add(list.get(i) - list.get(j));
} else if (k == DIVIDE) {
if (Math.abs(list.get(j)) < EPSILON) {
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (solve(list2)) {
return true;
}
list2.remove(list2.size() - 1);
}
}
}
}
return false;
}
}