友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
679. 24 点游戏
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 ( 和 ) 将这些卡片上的数字排列成数学表达式，以获得值24。
你须遵守以下规则:
-
除法运算符
/表示实数除法，而不是整数除法。-
例如，
4 /(1 - 2 / 3)= 4 /(1 / 3)= 12。
-
-
每个运算都在两个数字之间。特别是，不能使用
-作为一元运算符。-
例如，如果
cards =[1,1,1,1]，则表达式-1 -1 -1 -1是 不允许 的。
-
-
你不能把数字串在一起
-
例如，如果
cards =[1,2,1,2]，则表达式12 + 12无效。
-
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true，否则返回 false。
示例 1:
输入: cards = [4, 1, 8, 7] 输出: true 解释: (8-4) * (7-1) = 24
示例 2:
输入: cards = [1, 2, 1, 2] 输出: false
提示:
-
cards.length == 4 -
1 <= cards[i] <= 9
思路分析
对于题目这种情况，显然就是要穷举所有可能，那么明显就要上回溯。可惜没想好怎么实现。
看题解，直接抽出两个数做计算，来规避了“加括号”的繁琐计算。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-09 22:57:44
*/
private static final double EPS = 1e-10;
public boolean judgePoint24(int[] cards) {
List<Double> cs = new ArrayList<>();
for (int i : cards) {
cs.add((double) i);
}
return dfs(cs);
}
private boolean dfs(List<Double> cards) {
int size = cards.size();
if (size == 1) {
return Math.abs(cards.getFirst() - 24) < EPS;
}
for (int i = 0; i < size; i++) {
double a = cards.get(i);
for (int j = i + 1; j < size; j++) {
double b = cards.get(j);
List<Double> cans = new ArrayList<>();
cans.add(a + b);
cans.add(a - b);
cans.add(b - a);
cans.add(a * b);
if (Math.abs(b) > EPS) {
cans.add(a / b);
}
if (Math.abs(a) > EPS) {
cans.add(b / a);
}
List<Double> next = new ArrayList<>(cards);
next.remove(j);
for (Double c : cans) {
next.set(i, c);
if (dfs(next)) {
return true;
}
}
}
}
return false;
}