题目描述

解题思路

本题最难的点就是不能使用除法，所以不能一次性得出所有的结果。
此时可以使用矩阵巧妙的求出所有结果，我直呼nb！！！
https://leetcode.cn/leetbook/read/illustration-of-algorithm/570i11/
根据表格的主对角线（全为 11 ），可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果。

巧妙的通过矩阵来计算除开自己的所有乘积，此时可以先计算左下部分（从上往下计算），在计算右上部分（从下往上计算）。

计算巧妙使用上一层的乘积，而不是重新相乘。

class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        if (len == 0) return new int[0];
        int[] b = new int[len];
        int tmp = 1;
        // 乘积数组
        b[0] = 1;
        // 先计算左下半三角形，直接对b[]数组操作
        for (int i = 1; i < len; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        // 计算右上三角形，使用一个变量重新表示乘积
        for (int i = len - 2; i >= 0; i--) {
            tmp *= a[i + 1];
            b[i] *= tmp;
        }
        return b;
    }
}