题解 | #24点游戏算法#
24点游戏算法
https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
先对四个数进行排列 得到4!种排列方式
然后深度遍历 第一个数 加减乘除 第二个数 或者不选择第一个数
point2方法可以打印结果 这里提交用的point1方法
用的double存储是因为题目要求实数除法 这里没有考虑 除0异常 ac了 显然用例中不存在这种情况 懒得再改了
import java.util.*;
public class Main {
static final int POINT = 24;
static final int N = 4;
static LinkedList<Integer> indexStack = new LinkedList<>();
static double[] array;
static boolean success = false;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
array = new double[N];
int[] indexes = new int[N];
for (int i = 0; i < N; i++) {
array[i] = in.nextDouble();
indexes[i] = i;
}
dfs(indexes, 0);
if (success) {
System.out.println(true);
} else {
System.out.println(false);
}
}
static void dfs(int[] arr, int cur) {
if (cur == N) {
double[] newArr = new double[N];
for (int i = 0; i < N; i++) {
newArr[i] = array[indexStack.get(i)];
}
success = point2(newArr) || success;
} else {
for (int i : arr) {
if (!indexStack.contains(i)) {
indexStack.push(i);
dfs(arr, cur + 1);
indexStack.pop();
}
}
}
}
static boolean point1(double[] arr, int cur) {
if (cur == N - 1) {
if (Math.abs(arr[cur] - POINT) < 1E-6) {
System.out.println(Arrays.toString(arr));
return true;
} else {
return false;
}
}
double[] copy1 = Arrays.copyOf(arr, N);
double[] copy2 = Arrays.copyOf(arr, N);
double[] copy3 = Arrays.copyOf(arr, N);
double[] copy4 = Arrays.copyOf(arr, N);
double[] copy5 = Arrays.copyOf(arr, N);
copy1[cur + 1] = arr[cur] + arr[cur + 1];
copy2[cur + 1] = arr[cur] - arr[cur + 1];
copy3[cur + 1] = arr[cur] * arr[cur + 1];
copy4[cur + 1] = arr[cur] / arr[cur + 1];
return point1(copy1, cur + 1) || point1(copy2, cur + 1)
|| point1(copy3, cur + 1) || point1(copy4, cur + 1) || point1(copy5, cur + 1);
}
static boolean point2(double[] arr) {
if (arr.length == 1) {
if (Math.abs(arr[0] - POINT) < 1E-6) {
return true;
} else {
return false;
}
}
double[] copy1 = Arrays.copyOfRange(arr, 1, arr.length);
double[] copy2 = Arrays.copyOfRange(arr, 1, arr.length);
double[] copy3 = Arrays.copyOfRange(arr, 1, arr.length);
double[] copy4 = Arrays.copyOfRange(arr, 1, arr.length);
double[] copy5 = Arrays.copyOfRange(arr, 1, arr.length);
copy1[0] = arr[0] + arr[1];
copy2[0] = arr[0] - arr[1];
copy3[0] = arr[0] * arr[1];
copy4[0] = arr[0] / arr[1];
return point2(copy1) || point2(copy2)
|| point2(copy3) || point2(copy4) || point2(copy5);
}
}
