-
Notifications
You must be signed in to change notification settings - Fork 133
/
Code01_24Game.java
97 lines (85 loc) · 2.39 KB
/
Code01_24Game.java
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package class_2022_02_2_week;
// 测试链接 : https://leetcode.com/problems/24-game/
public class Code01_24Game {
public static boolean judgePoint24(int[] cards) {
if (cards == null || cards.length == 0) {
return false;
}
int n = cards.length;
Number[] arr = new Number[n];
for (int i = 0; i < n; i++) {
arr[i] = new Number(cards[i], 1);
}
return judge(arr, cards.length);
}
// arr中,有效的范围arr[0...size-1] ... 再往右,都无效了,不用看了!
public static boolean judge(Number[] arr, int size) {
if (size == 1) {
return arr[0].numerator == 24 && arr[0].denominator == 1;
}
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
Number inum = arr[i];
Number jnum = arr[j];
arr[j] = arr[size - 1];
arr[i] = add(inum, jnum);
if (judge(arr, size - 1)) {
return true;
}
arr[i] = minus(inum, jnum);
if (judge(arr, size - 1)) {
return true;
}
arr[i] = minus(jnum, inum);
if (judge(arr, size - 1)) {
return true;
}
arr[i] = multiply(inum, jnum);
if (judge(arr, size - 1)) {
return true;
}
arr[i] = divide(inum, jnum);
if (arr[i] != null && judge(arr, size - 1)) {
return true;
}
arr[i] = divide(jnum, inum);
if (arr[i] != null && judge(arr, size - 1)) {
return true;
}
arr[i] = inum;
arr[j] = jnum;
}
}
return false;
}
public static class Number {
public int numerator;
public int denominator;
public Number(int n, int d) {
numerator = n;
denominator = d;
}
}
public static Number add(Number a, Number b) {
return simple(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
}
public static Number minus(Number a, Number b) {
return simple(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
}
public static Number multiply(Number a, Number b) {
return simple(a.numerator * b.numerator, a.denominator * b.denominator);
}
public static Number divide(Number a, Number b) {
return b.numerator == 0 ? null : simple(a.numerator * b.denominator, a.denominator * b.numerator);
}
public static Number simple(int up, int down) {
if (up == 0) {
return new Number(0, 1);
}
int gcd = Math.abs(gcd(up, down));
return new Number(up / gcd, down / gcd);
}
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}