[Leetcode][第679题][JAVA][24点游戏][回溯][暴力]

迈不过友情╰ 2022-11-30 00:21 150阅读 0赞

#### 【问题描述】\[困难\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 回溯 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

**时间复杂度：O(1) 空间复杂度：O(1)**

class Solution { 
            static final int TARGET = 24;
            static final double EPSILON = 1e-6;
            static final int ADD= 0,MULTIPLY=1,SUBTRACT = 2,DIVIDE= 3;
        public boolean judgePoint24(int[] nums) { 
            List<Double> list = new ArrayList<Double>();
            for(int num:nums){ 
                list.add((double) num);
            }
            return solve(list);
        }
        public boolean solve(List<Double> list) { 
             // list空，没有可计算的，证明无解
            if (list.size() == 0) { 
                return false;
            }
            if(list.size() == 1){ 
                // le-6是浮点计算的精度误差，这里判断误差小于1e-6，这样就是正确结果
                return Math.abs(list.get(0) - TARGET)< EPSILON;
            }
        // k的四种计算情况
            int size = list.size();
            // 性能优化，当k<2时，对于+ or *不考虑顺序，
            // 所以k<2 时，j > i与i > j的结果相同，所以有部分不用考虑
    
            for(int i=0;i<size;i++){ 
                for(int j=0;j<size;j++){ 
                    if(i!=j){ 
                        List<Double> list2 = new ArrayList<Double>();
                        for(int k =0;k<size;k++){ 
                            if(k!=i && k!=j){ 
                                list2.add(list.get(k));
                            }
                        }
                        for(int k=0;k<4 ;k++){ 
                            if(k<2 && i>j){ 
                                continue;
                            }
                            if(k==ADD){ 
                                list2.add(list.get(i)+list.get(j));
                            } else if (k == MULTIPLY) { 
                                list2.add(list.get(i) * list.get(j));
                            } else if (k == SUBTRACT) { 
                                list2.add(list.get(i) - list.get(j));
                            } else if (k == DIVIDE) { 
                                // 避免除数为0
                                if(Math.abs(list.get(j))<EPSILON){ 
                                    continue;
                                }else{ 
                                    list2.add(list.get(i) /list.get(j));
                                }
                            }
                            // 在这次计算后，判断剩下的元素是否符合要求
                            // 每次缩小计算范围
                            if(solve(list2)){ 
                                return true;
                            }
                             // 移除最后一个计算结果，因为最后的记过不满足要求
                            // 就是一种回溯方法，将前面添加的结果删除
                            list2.remove(list2.size()-1);
                        }
                    }
                }
            }
            return false;
        }
    }

#### 【总结】 ####

###### 1. 24点 回溯暴力解决 套娃 回溯 9216种可能 ######

###### 2.细节 ######

static final double EPSILON = 1e-6; // 1x10^(-6) 用来抵消浮点运算中因为误差造成的相等无法判断的情况。

转载：https://leetcode-cn.com/problems/24-game/solution/24-dian-you-xi-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/8f3a714ded164bb2bd81d5defa20f67f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/5376878cf6f24933a498dbb4d91591d3.png