LeetCode(113) -- 238,

P238. Product of Array Except Self (Medium)

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solution

方法一：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] ans = new int[length];
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }
        for (int i = 0; i < length; i++) {
            ans[i] = L[i] * R[i];
        }
        return ans;
    }
}

100%

方法二：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] ans = new int[length];
        ans[0] = 1;
        for (int i = 1; i < length; i++) {
            ans[i] = nums[i - 1] * ans[i - 1];
        }
        int r = 1;
        for (int i = length - 1; i >= 0; i--) {
            ans[i] = ans[i] * r;
            r *= nums[i];
        }
        return ans;
    }
}

100% 这种方法更好。

P241. Different Ways to Add Parentheses (Medium)

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Discuss

public class P241_DifferentWaystoAddParentheses {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();
        if (input == null || input.length() == 0) {
            return result;
        }
        List<String> ops = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            int j = i;
            while (j < input.length() && Character.isDigit(input.charAt(j))) {
                j++;
            }
            ops.add(input.substring(i, j));
            if (j != input.length()) {
                ops.add(input.substring(j, j + 1));
            }
            i = j;
        }
        int N = (ops.size() + 1) / 2;
        ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[N][N];
        for (int d = 0; d < N; d++) {
            if (d == 0) {
                for (int i = 0; i < N; i++) {
                    dp[i][i] = new ArrayList<>();
                    dp[i][i].add(Integer.valueOf(ops.get(i * 2)));
                }
                continue;
            }
            for (int i = 0; i < N - d; i++) {
                dp[i][i + d] = new ArrayList<>();
                for (int j = i; j < i + d; j++) {
                    ArrayList<Integer> left = dp[i][j];
                    ArrayList<Integer> right = dp[j + 1][i + d];
                    String operator = ops.get(j * 2 + 1);
                    for (Integer leftNum : left) {
                        for (Integer rightNum : right) {
                            if (operator.equals("+")) {
                                dp[i][i + d].add(leftNum + rightNum);
                            } else if (operator.equals("-")) {
                                dp[i][i + d].add(leftNum - rightNum);
                            } else {
                                dp[i][i + d].add(leftNum * rightNum);
                            }
                        }
                    }
                }
            }
        }
        return dp[0][N - 1];
    }
}

99%

The Best Solution

class Solution {
    
    HashMap<String, List<Integer>> map = new HashMap<String, List<Integer>>(); // For Memoization
    
    public List<Integer> diffWaysToCompute(String input) {
        
        if (map.containsKey(input)) // Optimization (Memoization)
            return map.get(input);
        
        List<Integer> res = new ArrayList<Integer>();
        
        if (input == null || input.length() == 0)
            return res;
        
        if (!input.contains("+") && !input.contains("-") && !input.contains("*")) {
            res.add(Integer.parseInt(input));
            //return res; // We are already returning it at the end
        } else {
            for (int i=0; i<input.length(); i++) {
                
                char c = input.charAt(i);
                if (!Character.isDigit(c)) {

                    String s1 = input.substring(0, i);
                    String s2 = input.substring(i+1);
                    
                    List<Integer> l1 = diffWaysToCompute(s1);
                    List<Integer> l2 = diffWaysToCompute(s2);
                         
                    for (int i1: l1) {
                        for (int i2 : l2) {
                            if (c == '+') 
                                res.add(i1+i2);
                            else if (c == '-')
                                res.add(i1-i2);
                            else if (c == '*')
                                res.add(i1*i2);
                            else
                                throw new IllegalArgumentException("The parent path cannot be null!");
                        }
                    }
                    
                }
            }
        }
        map.put(input, res);  // For Memoization
        return res;    
    }
}

99%