Leetcode Offer66题 JAVA动态规划去解决

Leetcode Offer66题 JAVA动态规划去解决

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：51.1 MB, 在所有 Java 提交中击败了98.32%的用户

思路

​ 首先要进行一些特殊情况判断，比如数组没有元素，或者数组的元素只有一个

        //当数组没有元素
        if (a.length == 0){
            return a;
        }

        //当元素只有一个的情况
        if (a.length == 1){
            return a;
        }

接下来我们创建two DP arrays，一个DP数组用来存储从左到右的乘积，另一个数组用来存储从右到左的的乘积。

在设置2个DP数组的默认值。

        int[] ldp   = new int[a.length];
        int[] rdp   = new int[a.length];
        ldp[0] = a[0];
        rdp[a.length-1] = a[a.length-1];

当我们记录乘积完成之后，就可以设置res的数据。但是设置数据的时候我们要判断2种特殊情况，如i == 0的时候和i == res.length-1的时候

            if (i == 0){
                res[i] = rdp[i+1];
                continue;
            }
            if (i == res.length-1){
                res[i] = ldp[i-1];
                continue;
            }

其他正常情况都遵守

res[i] = ldp[i-1] * rdp[i+1];

code

class Solution {
    public int[] constructArr(int[] a) {
        //当数组没有元素
        if (a.length == 0){
            return a;
        }

        //当元素只有一个的情况
        if (a.length == 1){
            return a;
        }


        int[] res = new int[a.length];
        int[] ldp   = new int[a.length];
        int[] rdp   = new int[a.length];
        ldp[0] = a[0];
        rdp[a.length-1] = a[a.length-1];

        /**
         * 记录从左到又的dp数据
         */
        for (int i = 1; i < a.length; i++) {
            ldp[i] = ldp[i-1] * a[i];
        }

        /**
         * 记录从又到左的dp数据
         */
        for (int i = a.length-2; i >=0 ; i--) {

            rdp[i] = rdp[i+1] * a[i];
        }

        for (int i = 0; i < res.length; i++) {
            if (i == 0){
                res[i] = rdp[i+1];
                continue;
            }
            if (i == res.length-1){
                res[i] = ldp[i-1];
                continue;
            }
            res[i] = ldp[i-1] * rdp[i+1];
        }

        return res;
    }
}