题解 | #24点运算#

递归算法+穷举解决问题

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    private static final String NONE = "NONE";
    private static final String ERROR = "ERROR";

    private static final String joker = "joker";
    private static final String JOKER = "JOKER";

    private static final String KEYS = "JQKA23456789";
    private static final int[] VALUES = new int[]{11,12,13,1,2,3,4,5,6,7,8,9};

    private static final String ADD = "+";
    private static final String SUB = "-";
    private static final String MOD = "*";
    private static final String DIV = "/";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            System.out.println(solve(in.nextLine()));
        }
    }

    private static String solve(String line) {
        if(line==null || line.contains(joker) || line.contains(JOKER)){
            return ERROR;
        }
        // 转换成数字
        List<Integer> arr = Arrays.stream(line.split(" ")).map((str)->{
            if(str.equals("10")){
                return 10;
            }else{
                return VALUES[KEYS.indexOf(str)];
            }
        }).collect(Collectors.toList());
        // 目标24
        int target = 24;
        return getExtFormList(arr,target,0);
    }
    /**
     * 递归运算 运算从左到右执行，倒推需要从右到左，逐步缩减集合，转化为两个数字运算，再采用穷举法
     * @param arr 运算数字集合
     * @param target 目标值
     * @param round 可上浮值
     * @return ext 运算表达式，无法计算返回NONE
     */
    private static String getExtFormList(List<Integer> arr, int target,int round) {
        // 倒推除法时，可以有波动空间
        if(round>0){
            for(int i=0;i<round;i++){
                String ext = getExtFormList(arr,target+i,0);
                if(!ext.equals(NONE)){
                    return ext;
                }
            }
        }
        // 只剩下两个数字时，可以穷举法判断
        if(arr.size()==2){
            int a = arr.get(0);
            int b = arr.get(1);
            if(a+b==target){
                return transfer(a) + ADD + transfer(b);
            }else if(a-b == target){
                return transfer(a) + SUB + transfer(b);
            }else if(b-a == target){
                return transfer(b) + SUB + transfer(a);
            }else if(a*b == target){
                return transfer(a) + MOD + transfer(b);
            }else if(a/b == target){
                return transfer(a) + DIV + transfer(b);
            }else if(b/a == target){
                return transfer(b) + DIV + transfer(a);
            }else{
                return NONE;
            }
        }
        // 逐个数字倒推判断
        for(int i=0;i<arr.size();i++){
            Integer a = arr.get(i);
            // 取出一个数字，判断剩余数字是否能计算出倒推出的目标值
            ArrayList<Integer> tmp1 = new ArrayList<>(arr);
            tmp1.remove(i);
            // 倒推加法
            String ext1 = getExtFormList(tmp1,target-a,0);
            if(!ext1.equals(NONE)){
                return ext1 + ADD + transfer(a);
            }
            // 倒推减法
            String ext2 = getExtFormList(tmp1,target+a,0);
            if(!ext2.equals(NONE)){
                return ext2 + SUB + transfer(a);
            }
            // 倒推乘法，需要整除
            if(target%a == 0){
                String ext3 = getExtFormList(tmp1,target/a,0);
                if(!ext3.equals(NONE)){
                    return ext3 + MOD + transfer(a);
                }
            }
            // 倒推除法
            String ext4 = getExtFormList(tmp1,target * a, a);
            if(!ext4.equals(NONE)){
                return ext4 + DIV + transfer(a);
            }
        }
        return NONE;
    }
    //结果转化 
    private static String transfer(int num){
        if(num==1){
            return "A";
        }
        if(num==11){
            return "J";
        }
        if(num==12){
            return "Q";
        }
        if(num==13){
            return "K";
        }
        return String.valueOf(num);
    }
}