Li Kou today's question -241 Design priorities for operational expressions

241. Design priorities for operation expressions

This should be regarded as divide and conquer , Dynamic programming usually has an optimal substructure , Dichotomy is the decomposition of big problems into small problems , Divide and rule ！ Then combine the solutions of small problems into the solutions of large problems .

class Solution {
    

    HashMap<String, List<Integer>> memo = new HashMap<>();

    public List<Integer> diffWaysToCompute(String input) {
    
        //  Avoid double counting 
        if (memo.containsKey(input)) {
    
            return memo.get(input);
        }
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < input.length(); i++) {
    
            char c = input.charAt(i);
            //  Scanning formula  input  Operator in 
            if (c == '-' || c == '*' || c == '+') {
    
                /****** branch ******/
                //  Operator centric , Split into two strings , Recursive calculation respectively 
                List<Integer>
                        left = diffWaysToCompute(input.substring(0, i));
                List<Integer>
                        right = diffWaysToCompute(input.substring(i + 1));
                /****** cure ******/
                //  Through the result of the subproblem , Synthesize the result of the original problem 
                for (int a : left)
                    for (int b : right)
                        if (c == '+')
                            res.add(a + b);
                        else if (c == '-')
                            res.add(a - b);
                        else if (c == '*')
                            res.add(a * b);
            }
        }
        // base case
        //  If  res  It's empty , Explain that the formula is a number , There are no operators 
        if (res.isEmpty()) {
    
            res.add(Integer.parseInt(input));
        }
        //  Add results to memo 
        memo.put(input, res);
        return res;
    }
}

The point is not to think about how to do the whole problem , But do it from a sub problem , The rest of recursion , Just traverse , The computer must be fast and good .

Fill in yesterday's question .

1175. Permutation of prime numbers

This solution .. It's called dictionary lookup , The answer has been written in advance .

class Solution {
    
    public int numPrimeArrangements(int n) {
    
        int[] ans = new int[]{
    1, 1, 1, 2, 4, 12, 36, 144, 576, 2880, 17280, 86400, 604800, 3628800, 29030400, 261273600, 612735986, 289151874, 180670593, 445364737, 344376809, 476898489, 676578804, 89209194, 338137903, 410206413, 973508979, 523161503, 940068494, 400684877, 13697484, 150672324, 164118783, 610613205, 44103617, 58486801, 462170018, 546040181, 197044608, 320204381, 965722612, 554393872, 77422176, 83910457, 517313696, 36724464, 175182841, 627742601, 715505693, 327193394, 451768713, 263673556, 755921509, 94744060, 600274259, 410695940, 427837488, 541336889, 736149184, 514536044, 125049738, 250895270, 39391803, 772631128, 541031643, 428487046, 567378068, 780183222, 228977612, 448880523, 892906519, 858130261, 622773264, 78238453, 146637981, 918450925, 514800525, 828829204, 243264299, 351814543, 405243354, 909357725, 561463122, 913651722, 732754657, 430788419, 139670208, 938893256, 28061213, 673469112, 448961084, 80392418, 466684389, 201222617, 85583092, 76399490, 500763245, 519081041, 892915734, 75763854, 682289015};
        return ans[n];
    }
}

This question really belongs to opportunism .