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 - 1
is not allowed. - You cannot concatenate numbers together. For example, if the input is
[1, 2, 1, 2]
, we cannot write this as 12 + 12.
排列组合。任取2个数,对它们进行四则运算,然后放回数组。直到数组大小为1
注意:这种方法可以处理掉括号
follow up
#1 打印出所有答案:开一个额外的数组作为参数记录(见下)
#2 如果括号不让用:应该是更简单。把所有排列组合写出来,然后写一个evaluate方法来计算。
class Solution { public boolean judgePoint24(int[] nums) { List<Double> l = new ArrayList<>(); for (int i : nums) { l.add((double) i); } return helper(l); } private boolean helper(List<Double> nums) { if (nums.size() == 1) { if (Math.abs(nums.get(0) - 24.0) < 1e-6) { return true; } return false; } for (int i = 0; i < nums.size(); i++) { for (int j = 0; j < nums.size(); j++) { if (i == j || nums.get(i) == nums.get(j)) continue; List<Double> tmp = new ArrayList<>(); for (int k = 0; k < nums.size(); k++) { if (k != i && k != j) tmp.add(nums.get(k)); } double n1 = nums.get(i); double n2 = nums.get(j); for (int k = 0; k < 4; k++) { double val = 0; if (k < 2 && j < i) continue; if (k == 0) val = n1 + n2; if (k == 1) val = n1 * n2; if (k == 2) val = n1 - n2; if (k == 3) { if (n2 != 0) val = n1 / n2; else continue; } tmp.add(val); if (helper(tmp)) return true; tmp.remove(tmp.size() - 1); } } } return false; } }
Follow #1 打印出所有答案
额外的数组里存的是为被计算前的值,如 “(1+3)”。对应原来的数组存的是4.
public static boolean judgePoint24(int[] nums) { List<Double> l = new ArrayList<>(); List<String> s = new ArrayList<>(); for (int i : nums) { l.add((double) i); s.add(Integer.toString(i)); } List<String> rt = new ArrayList<>(); helper(l, s, rt); for (String ss : rt) { System.out.println(ss); } return true; } private static void helper(List<Double> nums, List<String> s, List<String> rt) { if (nums.size() == 1) { if (Math.abs(nums.get(0) - 24.0) < 1e-6) { rt.add(s.get(0)); } return; } for (int i = 0; i < nums.size(); i++) { for (int j = 0; j < nums.size(); j++) { if (i == j || nums.get(i) == nums.get(j)) continue; List<Double> tmp = new ArrayList<>(); List<String> tmpS = new ArrayList<>(); for (int k = 0; k < nums.size(); k++) { if (k != i && k != j) { tmp.add(nums.get(k)); tmpS.add(s.get(k)); } } double n1 = nums.get(i); double n2 = nums.get(j); for (int k = 0; k < 4; k++) { double val = 0; String ss = ""; if (k < 2 && j < i) continue; if (k == 0) { val = n1 + n2; ss = "(" + s.get(i) + "+" + s.get(j) + ")"; } if (k == 1) { val = n1 * n2; ss = "(" + s.get(i) + "*" + s.get(j) + ")"; } if (k == 2) { val = n1 - n2; ss = "(" + s.get(i) + "-" + s.get(j) + ")"; } if (k == 3) { if (n2 != 0) { val = n1 / n2; ss = "(" + s.get(i) + "/" + s.get(j) + ")"; } else continue; } tmp.add(val); tmpS.add(ss); helper(tmp, tmpS, rt); tmp.remove(tmp.size() - 1); tmpS.remove(tmpS.size() - 1); } } } return; }
No comments:
Post a Comment