Welcome to Subscribe On Youtube
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:
- The division operator
/represents real division, not integer division. For example, 4 / (1 - 2/3) = 12. - 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 - 1is not allowed. - 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; } };