当前位置: 首页 > article >正文

【C++算法】28.前缀和_除自身以外数组的乘积

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:
    • 图解


题目链接:

238. 除自身以外数组的乘积


题目描述:

c237094360044e05077992913566c528


解法

暴力枚举:O(n2)

边枚举位置,边算乘积。

前缀和思想:

  1. 预处理前缀积和后缀积

f:前缀数组 这里面f[i]表示:[0,i-1]区间所有元素的积

g:后缀数组 这里面g[i]表示:[i+1,n-1]区间所有元素的积

f9276e056314b6db8f60a0577dd6aafd

f[i]=f[i-1]*nums[i-1]

g[i]=g[i+1]*nums[i+1]

  1. 使用ret数组存储i,使得i=f[i]*g[i]

  2. 注意细节问题,比如i=0的时候i-1不存在

    以及f[0]要设置为1g[n-1]设置为1

    因为如果f[0]=0,那么f[1]=0*nums[0]=0,后面就全0


C++ 算法代码:

class Solution 
{
    public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        // lprod 表示:[0, i - 1] 区间内所有元素的乘积
        // rprod 表示:[i + 1, n - 1] 区间内所有元素的乘积
        int n = nums.size();
        vector<int> lprod(n + 1), rprod(n + 1);
        lprod[0] = 1, rprod[n - 1] = 1;

        // 预处理前缀积以及后缀积
        for(int i = 1; i < n; i++)
            lprod[i] = lprod[i - 1] * nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            rprod[i] = rprod[i + 1] * nums[i + 1];

        // 处理结果数组
        vector<int> ret(n);
        for(int i = 0; i < n; i++)
            ret[i] = lprod[i] * rprod[i];
        return ret;
    }
};

图解

例如:nums = [1,2,3,4]

c7a7173f79648e3856195a14d57b5b97


http://www.kler.cn/a/420968.html

相关文章:

  • 千益畅行,旅游卡有些什么优势?
  • 百度木木浆测试
  • 点云3DHarris角点检测算法推导
  • 电子电气架构 --- 车载网关GW连接外部IP Tester
  • PostgreSQL17.x创建数据库及数据库信息查看命令
  • hint: Updates were rejected because the tip of your current branch is behind!
  • 【C++高级开发应用篇】探索C++20中的协程:异步编程的强大工具
  • GDPU Android移动应用 使用多媒体
  • 使用 Vite 快速搭建 Vue 2开发环境
  • 001-SpringBoot整合日志
  • 神经网络入门实战:(十一)池化层搭建,以及填充层的说明
  • 解读 77页2024 集团企业IT技术架构规划方案
  • k8s使用的nfs作为sc。
  • 传统客服中心和呼叫中心客服系统的区别
  • 时间序列模型在LSTM中的特征输入
  • AlmaLinux8.10安装samba实现与Windows文件共享
  • 获取联通光猫的管理员密码
  • 【AI日记】24.12.03 kaggle 比赛 Titanic-6
  • SVN客户端及语言包免费下载 无需积分
  • 计算机网络八股整理(四)
  • 【SpringBoot】SpringBoot优雅停机机制
  • Springboot(五十)SpringBoot3集成sentinel并连接sentinel-dashboard
  • 【大数据学习 | 面经】Spark3.x对比2.x有哪些优点
  • 通过搭建安消一体化管理体系,高校实现应急中心数字化转型升级新动能
  • 树和二叉树(概念 结构)
  • 手机租赁系统开发全攻略 创新服务助力企业智能转型