1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 66 题] “构建乘积数组”做题记录

[剑指 Offer 第 2 版第 66 题] “构建乘积数组”做题记录

第 66 题:构建乘积数组

传送门:构建乘积数组牛客网 online judge 地址

给定一个数组A[0, 1, …, n-1],请构建一个数组B[0, 1, …, n-1],其中 B 中的元素B[i] = A[0] × A[1] × … × A[i - 1] × A[i + 1] × … × A[n - 1]

不能使用除法。

样例:

输入:[1, 2, 3, 4, 5]

输出:[120, 60, 40, 30, 24]

思考题

  • 能不能只使用常数空间?(除了输出的数组之外)

liwei20191011112_1.png

思路:使用矩阵法求解,将矩阵分为上三角矩阵和下三角矩阵,分别求乘积。

liwei201910118_2.png

Python 代码:

  class Solution(object):
        def multiply(self, A):
            """
            :type A: List[int]
            :rtype: List[int]
            """

            l = len(A)
            if l == 0:
                return []
            b = [None for _ in range(l)]

            b[0] = 1
            # 计算下三角连乘的结果
            for i in range(1, l):
                b[i] = b[i - 1] * A[i - 1]

            temp = 1
            for i in range(l - 2, -1, -1):
                temp *= A[i + 1]
                b[i] *= temp
            return b

Python 代码:

  # 66、构建乘积数组

    class Solution(object):
        def multiply(self, A):
            """
            :type A: List[int]
            :rtype: List[int]
            """

            l = len(A)
            if l == 0:
                return []
            b = [1 for _ in range(l)]
            temp = 1
            for index in range(l):
                b[index] *= temp
                temp *= A[index]
            temp = 1
            for index in range(l - 1, -1, -1):
                b[index] *= temp
                temp *= A[index]
            return b

Java 代码:

liwei201910112_3.png

C++ 代码:

  class Solution {
    public:
        vector<int> multiply(const vector<int>& A) {
            vector<int>left(A.size(),1);
            vector<int>right(A.size(),1);
            for(int i = 1;i<A.size();i++){
                left[i] = A[i-1]*left[i-1];
            }
            for(int i = A.size()-2;i>=0;i--){
                right[i] = A[i+1]*right[i+1];
            }
            vector<int>B(A.size(),0);
            for(int i = 0;i<A.size();i++){
                B[i] = left[i]*right[i];
            }
            return B;
        }
    };

作者:cornerCao 链接:https://www.acwing.com/solution/AcWing/content/759/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 66 题] “构建乘积数组”做题记录

链接:https://www.javajike.com/article/3305.html

« [剑指 Offer 第 2 版第 65 题] “不用加减乘除做加法”做题记录
[剑指 Offer 第 2 版第 67 题] “把字符串转换成整数”做题记录»

相关推荐

QR code