• 首页

  • 文章归档

  • 文章分类

  • 日志

  • 图库

  • 友链

  • 留言板

  • 关于我
H i , m e g u m i
H i , m e g u m i

无名高

获取中...

09
16
算法题

剑指Offer 66.构建乘积数组

发表于 2020-09-16 • 剑指Offer • 被 460 人看爆

给定一个数组 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]
     

提示:

  • 所有元素乘积之和不会溢出 32 位整数
  • a.length <= 100000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路:
由于不能使用除法,只能在计算B[i]前,分别得到A[0] * A[1] * ... * A[i-1]和A[i+1] * A[i+2] * ... * A[n-1]的值
使用一个dp数组,可以很容易的一趟遍历得到leftSum[i]的值,其中leftSum[i] = a[0] * a[1] * a[2] * ... * a[i-1]
然后进行第二趟逆序遍历,这次遍历可以使用一个临时变量temp存储A[i+1] * A[i+2] * ... * A[n-1]的值,然后将temp * leftSum[i]即可得到B[i]的值

代码:

class Solution {
private:
    // leftSum[i] 存储了a[0]*a[1]*...*a[i-1]的积
    vector<int> ans;
public:
    vector<int> constructArr(vector<int>& a) {
        ans.resize(a.size());
        if (a.size() == 0) {
            return vector<int>();
        }
        // ans[i]一开始存放leftSum[i]的结果 leftSum[i] = a[0]*a[1]*a[2]*...*a[i-1]
        ans[0] = 1;
        for (int k = 1; k < a.size(); ++k) {
            ans[k] = a[k-1]*ans[k-1];
        }
        // 计算rightSum[i]
        int tmp = 1;
        for (int k = (int)a.size()-2; k >= 0; --k) {
            tmp *= a[k+1];
            ans[k] *= tmp;
        }
        return ans;
    }
                    
    
};
分享到:
LeetCode 685. 冗余连接 II
LeetCode 226.翻转二叉树
  • 文章目录
  • 站点概览
无名高

帅哥无名高

我们是如何走到这一步

Github QQ Email RSS
看爆 Top5
  • SpringBoot学习笔记 2,395次看爆
  • 解决在IDEA编写Java代码时,向数据库中插入中文字符后显示?乱码问题 2,324次看爆
  • JDBC核心技术笔记 2,203次看爆
  • SpringMVC学习笔记 1,906次看爆
  • MySQL基础学习笔记 1,859次看爆
粤公网安备 44030702003128号 黔ICP备20006240号

Copyright © 2022 无名高 ·

Proudly published with Halo · Theme by fyang · 站点地图