JZ51

思路

考察动态规划，使用dp数组保存已计算的结果

Code

简洁写法：

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int n = A.length;
        int[] B = new int[n];
        for(int i = 0 , product = 1; i < n; product *= A[i] ,i++)    //从左往右类乘
            B[i] = product;
        for(int i = n-1, product = 1; i >= 0; product *= A[i] , i--)
            B[i] *= product;
        return B;
    }
}

稍多：

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] a) {
        if(a.length == 0) return new int[0];
        int[] b = new int[a.length];
        b[0] = 1;
        int tmp = 1;
        for(int i = 1; i < a.length ; i++)
        {
            b[i] = b[i-1] * a[i-1];
        }
        for(int i = a.length - 2; i >= 0; i--)
        {
            tmp *= a[i+1];
            b[i] *= tmp;
        }
        return b;
    }
}

最常见：

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if(A == null || A.length == 0)
            return A;
        int len = A.length;
        //维护2个DP数组
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = right[len-1] = 1;
        for(int i = 1 ; i< len; i++)
        {
            left[i] = left[i-1] * A[i-1];
        }
        for(int i = len - 2; i >= 0; i--)
            right[i] = right[i+1] * A[i+1];
        int[] ret = new int[len];
        for(int i = 0; i < len; i++)
            ret[i] = left[i] * right[i];
        return ret;
    }
}