Formatted question description: https://leetcode.ca/all/679.html

679. 24 Game

Level

Hard

Description

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]

Output: True

Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]

Output: False

Note:

  1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
  3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Solution

Simply consider all possible postfix expressions using the given 4 numbers and the 4 operators. In postfix expressions, brankets do not exist.

Obtain all possible permutations of the given 4 numbers. Since there are 3 operators used when there are 4 numbers, obtain all possible permutations that contains 3 operators.

Given 4 numbers and 3 operators, there are 4 possible postfix expressions, which are listed as follows, where n represents a number and o represents an operator.

n n n n o o o
n n n o n o o
n n o n o n o
n n o n n o o

For each permutation of numbers, each permutation of operators and each possible postfix expression, calculate the value. If there exists a postfix expression that has value 24, return true. Otherwise, return false.

Since the division operator represents real division, maintain a rational number for the result of calculation, which contains a numerator and a denominator.

  • class Solution {
        public boolean judgePoint24(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> permutations = permuteUnique(nums);
            char[] operators = {'+', '-', '*', '/'};
            for (List<Integer> permutation : permutations) {
                for (int i = 0; i < 64; i++) {
                    int[] base4 = toBase4(i);
                    char[] curOperators = new char[3];
                    for (int j = 0; j < 3; j++)
                        curOperators[j] = operators[base4[j]];
                    char[][] postfixes = new char[4][7];
                    for (int j = 0; j < 4; j++) {
                        for (int k = 0; k < 4; k++)
                            postfixes[j][k] = (char) (permutation.get(k) + '0');
                        for (int k = 4; k < 7; k++)
                            postfixes[j][k] = curOperators[k - 4];
                    }
                    char temp2 = postfixes[1][3];
                    postfixes[1][3] = postfixes[1][4];
                    postfixes[1][4] = temp2;
                    char temp3 = postfixes[2][5];
                    postfixes[2][5] = postfixes[2][3];
                    postfixes[2][3] = postfixes[2][2];
                    postfixes[2][2] = postfixes[2][4];
                    postfixes[2][4] = temp3;
                    char temp4 = postfixes[3][4];
                    postfixes[3][4] = postfixes[3][3];
                    postfixes[3][3] = postfixes[3][2];
                    postfixes[3][2] = temp4;
                    for (int j = 0; j < 4; j++) {
                        if (equals24(postfixes[j]))
                            return true;
                    }
                }
            }
            return false;
        }
    
        public List<List<Integer>> permuteUnique(int[] nums) {
            int length = nums.length;
            List<List<Integer>> permutations = new ArrayList<List<Integer>>();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < length; i++)
                list.add(nums[i]);
            permutations.add(list);
            int[] array = new int[length];
            for (int i = 0; i < length; i++)
                array[i] = nums[i];
            nextPermutation(array);
            while (!Arrays.equals(nums, array)) {
                List<Integer> permutation = new ArrayList<Integer>();
                for (int i = 0; i < length; i++)
                    permutation.add(array[i]);
                permutations.add(permutation);
                nextPermutation(array);
            }
            return permutations;
        }
    
        public void nextPermutation(int[] array) {
            int length = array.length;
            int index = -1;
            int curNum = -1;
            for (int i = length - 1; i > 0; i--) {
                int difference = array[i] - array[i - 1];
                if (difference > 0) {
                    index = i - 1;
                    curNum = array[i - 1];
                    break;
                }
            }
            if (index < 0) {
                Arrays.sort(array);
                return;
            }
            int nextIndex = -1;
            int nextNum = Integer.MAX_VALUE;
            for (int i = index + 1; i < length; i++) {
                if (array[i] > curNum && array[i] < nextNum) {
                    nextIndex = i;
                    nextNum = array[i];
                }
            }
            array[index] = nextNum;
            array[nextIndex] = curNum;
            Arrays.sort(array, index + 1, length);
        }
    
        public int[] toBase4(int num) {
            int[] base4 = new int[3];
            for (int i = 2; i >= 0; i--) {
                int remainder = num % 4;
                base4[i] = remainder;
                num /= 4;
            }
            return base4;
        }
    
        public boolean equals24(char[] postfix) {
            int length = postfix.length;
            Stack<int[]> stack = new Stack<int[]>();
            for (int i = 0; i < length; i++) {
                char c = postfix[i];
                if (Character.isDigit(c)) {
                    int num = c - '0';
                    stack.push(new int[]{num, 1});
                } else {
                    int[] num2 = stack.pop();
                    int[] num1 = stack.pop();
                    int[] newNum = new int[2];
                    switch (c) {
                        case '+':
                            newNum[0] = num1[0] * num2[1] + num2[0] * num1[1];
                            newNum[1] = num1[1] * num2[1];
                            break;
                        case '-':
                            newNum[0] = num1[0] * num2[1] - num2[0] * num1[1];
                            newNum[1] = num1[1] * num2[1];
                            break;
                        case '*':
                            newNum[0] = num1[0] * num2[0];
                            newNum[1] = num1[1] * num2[1];
                            break;
                        case '/':
                            newNum[0] = num1[0] * num2[1];
                            newNum[1] = num1[1] * num2[0];
                            break;
                        default:
                    }
                    int gcd = gcd(newNum[0], newNum[1]);
                    newNum[0] /= gcd;
                    newNum[1] /= gcd;
                    if (newNum[1] < 0) {
                        newNum[0] = -newNum[0];
                        newNum[1] = -newNum[1];
                    }
                    stack.push(newNum);
                }
            }
            int[] result = stack.pop();
            return result[0] == 24 && result[1] == 1;
        }
    
        public int gcd(int a, int b) {
            a = Math.abs(a);
            b = Math.abs(b);
            if (a == 0 && b == 0)
                return 1;
            while (a != 0 && b != 0) {
                if (a > b) {
                    int temp = a;
                    a = b;
                    b = temp;
                }
                b %= a;
            }
            return a == 0 ? b : a;
        }
    }
    
  • // OJ: https://leetcode.com/problems/24-game/
    // Time: O(?)
    // Space: O(?)
    class Solution {
        bool judge(vector<int> &A) {
            unordered_set<double> dp[4][4] = {};
            for (int i = 0; i < 4; ++i) dp[i][i].insert(A[i]);
            for (int i = 2; i >= 0; --i) {
                for (int j = i + 1; j < 4; ++j) {
                    for (int k = i; k < j; ++k) {
                        for (double a : dp[i][k]) {
                            for (double b : dp[k + 1][j]) {
                                dp[i][j].insert(a + b);
                                dp[i][j].insert(a - b);
                                dp[i][j].insert(a * b);
                                if (b) dp[i][j].insert(a / b);
                            }
                        }
                    }
                }
            }
            for (double n : dp[0][3]) {
                if (abs(n - 24) < 1e-6) return true;
            }
            return false;
        }
    public:
        bool judgePoint24(vector<int>& A) {
            sort(begin(A), end(A));
            do {
                if (judge(A)) return true;
            } while (next_permutation(begin(A), end(A)));
            return false;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions