题目大意：
24 点游戏
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
示例 1:
输入: [4, 1, 8, 7] 输出: True 解释: (8-4) * (7-1) = 24
示例 2:
输入: [1, 2, 1, 2] 输出: False
注意:
- 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 – 2/3) = 12 。
- 每个运算符对两个数进行运算。特别是我们不能用 – 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 – 1 – 1 – 1 是不允许的。
- 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=679
解题思路分析：
本题的难点在于除法，比如2除以3，应该等于三分之二，在java中要是按照整数除法的话会等于0，这样会影响到最后的计算结果。我在解题时想到了一个比较笨的办法，即将每一个数（整数或者小数）都看作是一个分数，由分子和分母组成，我们用一个数组来表示该分数，int[] num。num[0]是分子，num[1]是分母，该数值应该是 num[0] / num[1]。比如三分之二，我们可以表示为[2,3]，同理整数5可以表示为[5,1]。
有了上面的解决除法的思路，本题难度就大幅下降了。我们采用递归方式来解题，先将所有数字（总共4个数字，分别由分数数组形式表示）组成一个集合(ArrayList)传入递归方法，递归方法中，循环取出任意2个数字，对其进行加减乘除四种分数运算，分别将计算结果与剩余没有用到的数字，组成新的集合传入递归方法。递归结束条件为当前集合只有1个元素时，查看其分子与分母的商是否正好等于24，如果是返回true，反之返回false即可。循环遍历的所有情况中，只要有一种结果为true，最终的返回结果即是true。
实现代码：
boolean res; // 返回结果
public boolean judgePoint24(int[] nums) {
// 将所有整数变为分数集合
List<int[]> list = new ArrayList<>();
for(int num : nums) list.add(new int[]{num, 1});
help(list); // 递归求解
return res;
}
void help(List<int[]> nums){
// 如果集合中只有一个元素，或者已经找到合理的24点计算方法时，结束递归
if(nums.size()==1 || res){
int[] num = nums.get(0); // 取得集合中唯一的元素
// 如果该数分母不为0，并且分子除以分母正好等于24
if(num[1]!=0&&num[0]/num[1]==24&&num[0]%num[1]==0){
res = true; // 返回结果为true。
}
return; // 结束递归
}
// 循环取出集合中的2个数字。
for(int i=0;i<nums.size();i++){
int nu1=nums.get(i)[0]; // 第一个数的分子
int de1=nums.get(i)[1]; // 第一个数的分母
for(int j=0;j<nums.size();j++){
// 取出一个与第一个数不同的第二个数字
if(i!=j){
int nu2=nums.get(j)[0]; // 第二个数的分子
int de2=nums.get(j)[1]; // 第二个数的分母
// 新建一个集合，存储剩下没用到的数字
List<int[]> list = new ArrayList<>();
for(int k=0;k<nums.size();k++){
if(k!=i&&k!=j) list.add(nums.get(k));
}
// 两个数进行加法运算，并将结果加入新的集合
list.add(new int[]{nu1*de2+nu2*de1, de1*de2});
// 利用新的集合递归求解
help(list);
// 从新的集合中删除加法运算结果
list.remove(list.size()-1);
// 两个数进行减法运算，并将结果加入新的集合
list.add(new int[]{nu1*de2-nu2*de1, de1*de2});
// 利用新的集合递归求解
help(list);
// 从新的集合中删除减法运算结果
list.remove(list.size()-1);
// 两个数进行乘法运算，并将结果加入新的集合
list.add(new int[]{nu1*nu2,de1*de2});
// 利用新的集合递归求解
help(list);
// 从新的集合中删除乘法运算结果
list.remove(list.size()-1);
// 两个数进行除法运算，并将结果加入新的集合
list.add(new int[]{nu1*de2,de1*nu2});
// 利用新的集合递归求解
help(list);
// 从新的集合中删除除法运算结果
list.remove(list.size()-1);
}
}
}
} 本题解法执行时间为9ms。
Runtime: 9 ms, faster than 76.81% of Java online submissions for 24 Game.
Memory Usage: 37.7 MB, less than 93.75% of Java online submissions for 24 Game.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-679-24-game-解题思路分析/