题解 | #24点运算#
利用dfs计算全排列
1)计算四种运算符的可重复取(4取3)的全排列
2)计算4个数字的全排列,注意有可能四张牌相同
3)遍历每一种运算符排列和数字排列,有符合的情况则立即输出
import java.util.*; public class Main { public static void main(String[] args) { // 此题不同于24点游戏,此题只按照从左到右计算,不按照运算级运算 // + - * /,四个符号里面选择三个,放在4个数字之间 Scanner sc = new Scanner(System.in); String[] str = sc.nextLine().trim().split(" "); int[] pai = new int[4]; for (int i = 0; i < 4; i++) { int len = str[i].length(); if (len > 2) { System.out.println("ERROR"); return; } else if (str[i].length() == 2) { pai[i] = 10; } else { char ch = str[i].charAt(0); if (Character.isDigit(ch)) { pai[i] = ch - '0'; } else { if (ch == 'J') pai[i] = 11; if (ch == 'Q') pai[i] = 12; if (ch == 'K') pai[i] = 13; if (ch == 'A') pai[i] = 1; } } } // 运算符全排列(可重复选的,4选3的) List<List<Character>> operationsList = new ArrayList<>(); List<Character> opList = new ArrayList<>(); Character[] operations = {'+', '-', '*', '/'}; dfsOp(operationsList, opList, operations); // 计算牌的全排列 List<List<Integer>> paisList = new ArrayList<>(); List<Integer> pList = new ArrayList<>(); boolean[] visited = new boolean[4]; dfsPai(paisList, pList, pai, visited); for(List<Integer> p : paisList) { for (List<Character> op : operationsList) { if (compute(p,op)) { printPai(p.get(0)); for (int i = 0; i < 3; i++) { System.out.print(op.get(i)); printPai(p.get(i + 1)); } return; } } } System.out.println("NONE"); } public static void printPai(int num) { if (num == 1) System.out.print('A'); if (num == 11) System.out.print('J'); if (num == 12) System.out.print('Q'); if (num == 13) System.out.print('K'); if (num >= 2 && num <= 10) System.out.print(num); } /** * 计算运算符的全排列 * 计算可重复选,4选3的全排列 */ public static void dfsOp(List<List<Character>> operationsList, List<Character> list, Character[] operations) { if (list.size() == 3) { operationsList.add(new ArrayList<>(list)); return; } for (char c : operations) { list.add(c); dfsOp(operationsList, list, operations); list.remove(list.size() - 1); // 回溯 } } /** * 计算牌的全排列,不可重复的全排列 */ public static void dfsPai(List<List<Integer>> paisList, List<Integer> list, int[] pai, boolean[] visited) { if (list.size() == 4) { paisList.add(new ArrayList<>(list)); return; } for (int i = 0; i < 4; i++) { if (!visited[i]) { list.add(pai[i]); visited[i] = true; dfsPai(paisList, list, pai, visited); list.remove(list.size() - 1); // 回溯 visited[i] = false; } } } /** * 判断表达式是否为24 * 运算顺序从左至右,不包含括号,且整数除法属于整除 */ public static boolean compute(List<Integer> pList, List<Character> opList) { int result = pList.get(0); // 剩余三个数字和三个运算符 for (int i = 0; i < 3; i++) { char op = opList.get(i); int sub = pList.get(i + 1); if (op == '+') { result = result + sub; } else if (op == '-') { result = result - sub; } else if (op == '*') { result = result * sub; } else { result = result / sub; } } return result == 24; } }