题解 | #24点运算#
24点运算
https://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d
使用DFS + 牌随机排序尝试计算50次
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String inputData = in.nextLine();
if(inputData.contains("joker") || inputData.contains("JOKER")) {
System.out.println("ERROR");
return;
}
String[] paiArray = inputData.split(" ");
int tryCalNum = 0;
boolean opResult = false;
while(!opResult && tryCalNum < 50) {//暂时猜测计算50次一定得出结果，超出50次说明不能计算出24
String[] paiRandomArray = new String[paiArray.length];//保存牌的随机顺序值
int[] randomArray = getRandom();
for(int i = 0; i < paiRandomArray.length; i ++) {
paiRandomArray[i] = paiArray[randomArray[i]];
}
int lastCalResult = getPaiRealVal(paiRandomArray[0]);
StringBuilder opeSb = new StringBuilder();
opResult = dfs(paiRandomArray, 0, lastCalResult, opeSb);
opeSb.insert(0, paiRandomArray[0]);
if(opResult) {
//计算成功24
System.out.println(opeSb.toString());
break;
}
tryCalNum ++;
}
if(!opResult) {
System.out.println("NONE");
}
}
}
//深度优先搜索算法
private static boolean dfs(String[] paiArray, int index, int lastCalResult, StringBuilder opeSb) {
if(index == paiArray.length - 1 && lastCalResult == 24) {
return true;
}
if(index + 1 <= paiArray.length - 1) {
//加
boolean result = dfs(paiArray, index + 1, lastCalResult + getPaiRealVal(paiArray[index + 1]), opeSb);
if(result) {
opeSb.insert(0, "+" + paiArray[index + 1]);
//opeSb.append(getPaiRealVal(paiArray[index + 1]));
return result;
}
//减
result = dfs(paiArray, index + 1, lastCalResult - getPaiRealVal(paiArray[index + 1]), opeSb);
if(result) {
opeSb.insert(0, "-" + paiArray[index + 1]);
//opeSb.append(getPaiRealVal(paiArray[index + 1]));
return result;
}
//乘
result = dfs(paiArray, index + 1, lastCalResult * getPaiRealVal(paiArray[index + 1]), opeSb);
if(result) {
opeSb.insert(0, "*" + paiArray[index + 1]);
//opeSb.append(getPaiRealVal(paiArray[index + 1]));
return result;
}
//除
int divResult = lastCalResult / getPaiRealVal(paiArray[index + 1]);
int ysResult = lastCalResult % getPaiRealVal(paiArray[index + 1]);
if(ysResult == 0) {
//能被整除
result = dfs(paiArray, index + 1, divResult, opeSb);
} else {
result = false;
}
if(result) {
opeSb.insert(0, "/" + paiArray[index + 1]);
//opeSb.append(getPaiRealVal(paiArray[index + 1]));
return result;
}
}
return false;
}
//获取牌的实际值
public static int getPaiRealVal(String pai) {
int result = 0;
switch(pai) {
case "2":
case "3":
case "4":
case "5":
case "6":
case "7":
case "8":
case "9":
case "10": result = Integer.valueOf(pai); break;
case "J": result = 11; break;
case "Q": result = 12; break;
case "K": result = 13; break;
case "A": result = 1; break;
}
return result;
}
//随机生成4个0到3不同的数
public static int[] getRandom() {
int[] resultData = new int[4];
boolean[] findFlag = new boolean[4];
int calData = (int)(Math.random() * (3 - 0 + 1) + 0);
for(int i = 0; i < resultData.length; i ++) {
while(findFlag[calData]) {
calData = (int)(Math.random() * (3 - 0 + 1) + 0);
}
findFlag[calData] = true;
resultData[i] = calData;
}
return resultData;
}
}
