Java, brute force


  • 0
    F

    Java,

    1. To avoid processing arrays of mixing type(int and string/character), using -1 to -4 to represent +-*/
    2. Generate all 64 possible operator combinations, append to the tail of operands array
    3. Generate all permutations of array generated in step 2
    4. Evaluate every permutation in step 3
        double eval(int[] nums) {
            Stack<Double>st=new Stack<>();
            for (int n:nums){
                if (n>=0)st.push((double)n);
                else {
                    if (st.size()<2)return -1;
                    double right=st.pop();
                    double left=st.pop();
                    switch(n){
                        case -1:
                            st.push(left+right);
                            break;
                        case -2:
                            st.push(left-right);
                            break;
                        case -3:
                            st.push(left*right);
                            break;
                        case -4:
                            if (right==0)return -1;
                            st.push(left/right);
                            break;
                        default:
                            return -1;
                    }
                }
            }
            return st.pop();
    
        }
        public boolean judgePoint24(int[] nums) {
            for (int i = 0; i < 64; ++i) {
                int[] nums2 = Arrays.copyOf(nums, 7);
                int n = i;
                nums2[4] = -(n%4+1);
                n/=4;
                nums2[5]=-(n%4+1);
                n/=4;
                nums2[6]=-(n%4+1);
                List<int[]> perms =new ArrayList<>();
                genNums(perms,nums2,0);
                for (int[] perm: perms) {
                    double v = eval(perm);
    
                    if (Math.abs(v - 24) <= 0.00000001) return true;
                }
            }
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.