LWC 50：679. 24 Game
Problem:
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:
- The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
- 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.
- You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 12.
观察可以发现状态数非常少，所以完全可以采用暴力构造，暴力计算，暴力搜索。4个数字有24中情况，运算符有4种，3个位置有64种情况，所以只需要枚举出64 * 24中算数表达式的值即可。
我的代码：
代码语言：javascript复制 char[] op = new char[] { ' ', '-', '*', '/' };
public boolean judgePoint24(int[] nums) {
ops = new HashSet<>();
permutation(nums, 0, new boolean[4], "");
for (String oo : ops) {
Set<Double> ans = cal(oo);
for (double d : ans) {
if (Math.abs(d - 24) <= 0.0000000001) return true;
}
}
return false;
}
Set<Double> cal(String oo) {
int cnt = 0;
Set<Double> ans = new HashSet<>();
for (int i = 0; i < oo.length(); i) {
if (oo.charAt(i) == ' ') {
Set<Double> left = cal(oo.substring(0, i));
Set<Double> right = cal(oo.substring(i 1, oo.length()));
cnt ;
for (double a1 : left) {
for (double a2 : right) {
ans.add(a1 a2);
}
}
}
if (oo.charAt(i) == '-') {
Set<Double> left = cal(oo.substring(0, i));
Set<Double> right = cal(oo.substring(i 1, oo.length()));
cnt ;
for (double a1 : left) {
for (double a2 : right) {
ans.add(a1 - a2);
}
}
}
if (oo.charAt(i) == '*') {
Set<Double> left = cal(oo.substring(0, i));
Set<Double> right = cal(oo.substring(i 1, oo.length()));
cnt ;
for (double a1 : left) {
for (double a2 : right) {
ans.add(a1 * a2);
}
}
}
if (oo.charAt(i) == '/') {
Set<Double> left = cal(oo.substring(0, i));
Set<Double> right = cal(oo.substring(i 1, oo.length()));
cnt ;
for (double a1 : left) {
for (double a2 : right) {
ans.add(a1 / a2);
}
}
}
}
if (cnt == 0) {
ans.add(Double.parseDouble(oo));
return ans;
}
return ans;
}
Set<String> ops;
void permutation(int[] nums, int i, boolean[] vis, String ans) {
if (i >= nums.length) {
ops.add(ans.substring(0, ans.length() - 1));
return;
}
for (int j = 0; j < nums.length; j) {
if (!vis[j]) {
vis[j] = true;
for (int c = 0; c < 4; c) {
permutation(nums, i 1, vis, ans nums[j] op[c]);
}
vis[j] = false;
}
}
}精简版本：
代码语言：javascript复制 public boolean judgePoint24(int[] nums) {
ops = new int[24][4];
permutation(nums, 0, new boolean[4], new int[4]);
for (int i = 0; i < 24; i) {
Set<Double> ans = cal(ops[i], 0, 3);
for (double d : ans) {
if (Math.abs(d - 24) <= 0.0000000001) return true;
}
}
return false;
}
int[][] ops;
int tot = 0;
void permutation(int[] nums, int i, boolean[] vis, int[] tmp) {
if (i == 4) {
for (int j = 0; j < 4; j) {
ops[tot][j] = tmp[j];
}
tot ;
return;
}
for (int j = 0; j < nums.length; j) {
if (!vis[j]) {
tmp[i] = nums[j];
vis[j] = true;
permutation(nums, i 1, vis, tmp);
vis[j] = false;
}
}
}
Set<Double> cal(int[] nums, int start, int end){
Set<Double> ans = new HashSet<>();
if (start == end) {
return Collections.singleton(new Double(nums[start]));
}
else {
for (int i = start; i < end; i) {
Set<Double> left = cal(nums, start, i);
Set<Double> right = cal(nums, i 1, end);
for (double a1 : left) {
for (double a2 : right) {
ans.add(a1 a2);
ans.add(a1 - a2);
ans.add(a1 * a2);
ans.add(a1 / a2);
}
}
}
return ans;
}
}
