Java solution using lookup table


  • 0

    There are 2 conditions to consider.

    1. (a op b) op (c op d) = 24.
    2. 24 op a op b = c op d.

    I built a special 9-9 table to record the result of i * j, i - j, j - i, i + j, i / j and j / i. The rest is just the search. The function named "pair" is used for the first case, function named "rest" and helper is for the 2nd one. There would be some overlaps between those 2 kinds of calculations. Of course, you can eliminate the extra computation by modifying some function. Because of the float computation, when the difference is less than 0.01 (not very strict), it is 24.
    ps: "printTable" is an extra function to print out the table.

    Map<Integer, Map<Integer, Set<Double>>> table;
    public boolean judgePoint24(int[] nums) {
        table = new HashMap<Integer, Map<Integer, Set<Double>>>();
        Arrays.sort(nums);
        for (int i = 1; i <= 9; i++) {
            for (int j = i; j <= 9; j++) {
                buildTable(i, j);
            }
        }
        if (checkPairs(nums)) return true;
        if (checkRest(nums)) return true;
        return false;
    }
    
    
    private boolean checkRest(int[] nums) {
        return calcuRest(nums[0], nums[1], nums[2], nums[3])
            || calcuRest(nums[0], nums[1], nums[3], nums[2])
            || calcuRest(nums[2], nums[3], nums[0], nums[1])
            || calcuRest(nums[2], nums[3], nums[1], nums[0])
            || calcuRest(nums[0], nums[2], nums[1], nums[3])
            || calcuRest(nums[0], nums[2], nums[3], nums[1])
            || calcuRest(nums[1], nums[3], nums[0], nums[2])
            || calcuRest(nums[1], nums[3], nums[2], nums[0])
            || calcuRest(nums[0], nums[3], nums[1], nums[2])
            || calcuRest(nums[0], nums[3], nums[2], nums[1])
            || calcuRest(nums[1], nums[2], nums[0], nums[3])
            || calcuRest(nums[1], nums[2], nums[3], nums[0]);
    }
    private boolean calcuRest(int a, int b, int c, int d) {
        Set<Double> s1 = table.get(a).get(b);
        Set<Double> s2 = helper((double)c, 24);
        Set<Double> s3 = helper((double)d, 24);
        Set<Double> s4 = new HashSet<>();
        for (double last: s2) {
            s4.addAll(helper(d, last));
        }
        for (double last: s3) {
            s4.addAll(helper(c, last));
        }
        for (Double pair1: s1) {
            for (Double pair2: s4) {
                if (Math.abs(pair1 - pair2) < 0.01) return true;
            }
        }
        return false;
    }
    private Set<Double> helper (double c, double rest) {
        Set<Double> res= new HashSet<>();
        res.add(rest * c);
        res.add(rest / c);
        res.add(rest + c);
        res.add(rest - c);
        res.add(c / rest);
        res.add(c - rest);
        return res;
    }
    private boolean checkPairs(int[] nums) {
        return calcuPair(nums[0], nums[1], nums[2], nums[3]) 
            || calcuPair(nums[0], nums[2], nums[1], nums[3]) 
            || calcuPair(nums[0], nums[3], nums[1], nums[2]);
    }
    
    
    private boolean calcuPair(int a, int b, int c, int d) {
        Set<Double> s1 = null;
        Set<Double> s2 = null;
        if (a <= b)  s1 = table.get(a).get(b);
        else  s1 = table.get(b).get(a);
        if (c <= d) s2 = table.get(c).get(d);
        else s2 = table.get(d).get(c);
        for (Double pair1: s1) {
            for (Double pair2: s2) {
                double res = pair1.doubleValue() + pair2.doubleValue();
                if (Math.abs(res - 24) < 0.01) return true;
                res = pair1.doubleValue() - pair2.doubleValue();
                if (Math.abs(res - 24) < 0.01) return true;
                res = pair2.doubleValue() - pair1.doubleValue();
                if (Math.abs(res - 24) < 0.01) return true;
                res = pair1.doubleValue() * pair2.doubleValue();
                if (Math.abs(res - 24) < 0.01) return true;
                res = pair1.doubleValue() / pair2.doubleValue();
                if (Math.abs(res - 24) < 0.01) return true;
                res = pair2.doubleValue() / pair1.doubleValue();
                if (Math.abs(res - 24) < 0.01) return true;
            }
        }
        return false;
    }
    
    private void buildTable (double a, double b) {
        if (!table.containsKey((int)a)) {
            table.put((int)a, new HashMap<Integer, Set<Double>>());
        }
        Set<Double> memo = new HashSet<>();
        memo.add(a + b); memo.add(a - b); memo.add(b - a);
        memo.add(a * b); memo.add(a / b); memo.add(b / a);
        Map<Integer, Set<Double>> temp = table.get((int) a);
        temp.put((int)b, memo);
        table.put((int)a, temp);
    }
    // used to print out the 9-9 table
    private void printTable() {
        for (int keyA: table.keySet()) {
            System.out.println("key a: " + keyA);
            Map<Integer, Set<Double>> map = table.get(keyA);
            for (Integer keyB: map.keySet()) {
                System.out.println("key b: " + keyB);
                Set<Double> set = map.get(keyB);
                for (double num: set) {
                    System.out.print(num + ", ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.