算法练习：前缀和

目录

  • 1. 一维前缀和
  • 2. 二维前缀和
  • 3. 寻找数组中心下标
  • 4. 除自身以外数组的乘积
  • 5. !和为k的子数字
  • 6. !和可被k整除的子数组
  • 7. !连续数组
  • @8. 矩阵区域和

1. 一维前缀和

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    一维前缀和
  3. 思路：求前缀和数组，sum = dp[r] - dp[l - 1]
#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    int n = 0;
    int q = 0;
    cin >> n >> q;
    //先求前缀和数组
    int num = 0;
    //计算时可能溢出
    vector<long long> dp;
    dp.push_back(0);
    for(int i = 0; i < n; i++)
    {
        cin >> num;
        dp.push_back(num + dp[i]);
    }

    //求询问区间之和
    //dp[i] - dp[i - 1]
    //计算时可能溢出
    vector<long long> ret;
    int left = 0,right = 0;
    for(int i = 0; i < q; i++)
    {
        cin >> left >> right;
        ret.push_back(dp[right] - dp[left - 1]);
    }

    for(auto e : ret)
    {
        cout << e << endl;
    }

    return 0;    
}

优化：

int main() 
{
    int n = 0;
    int q = 0;
    cin >> n >> q;
    //先求前缀和数组
    int num = 0;
    //默认初始化为0
    vector<int> arr(n + 1);
    for(int i = 1; i < n + 1; i++)
    {
        cin >> num;
        arr[i] = num;
    }

    //防溢出
    vector<long long> dp(n + 1);
    for(int i = 1; i < n + 1; i++)
    {
        dp[i] = dp[i - 1] + arr[i];
    }

    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;    
}

2. 二维前缀和

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二维前缀和
  3. 思路：二维前缀和

在这里插入图片描述

int main()
{
    int n = 0, m = 0, q = 0;
    //先遍历，得值    
    cin >> n >> m >> q;
    vector<vector<long long>> arr;
    vector<long long> part(m + 1);
    for (int i = 0; i < n + 1; i++)
    {
        arr.push_back(part);
    }

    vector<vector<long long>> dp(arr);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }

    //求前缀和数组
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        }
    }

    //求区间值
    //x1,y1小，x2,y2大
    int x1, x2, y1, y2 = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;

    }

    return 0;
}

3. 寻找数组中心下标

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    寻找数组的中心下标
  3. 思路：正向与逆向前缀和数组，边界处理，特殊情况处理
class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp1(n);
        vector<int> dp2(n);
        //空
        if(nums.size() == 1)
        {
            return 0;
        }

        int left = 0, right = nums.size() - 1;
        //求前缀和数组
        //顺序
        while (left < nums.size())
        {
            if (left > 0)
            {
                dp1[left] = nums[left] + dp1[left - 1];
            }
            else
            {
                dp1[left] = nums[left];
            }
            left++;
        }
        //倒序
        while (right >= 0)
        {
            if (right < nums.size() - 1)
            {
                dp2[right] = nums[right] + dp2[right + 1];
            }
            else
            {
                dp2[right] = nums[right];
            }
            right--;
        }


        //遍历求中间结点
        for (int cur = 0; cur < nums.size(); cur++)
        {
            //dp1顺序
            //dp2倒序
            if (cur == 0)
            {
                if (dp2[cur + 1] == 0)
                {
                    return cur;
                }
            }
            else if (cur == nums.size() - 1)
            {
                if (dp1[cur - 1] == 0)
                {
                    return cur;
                }
            }
            else
            {
                if (dp1[cur - 1] == dp2[cur + 1])
                {
                    return cur;
                }
            }
        }

        return -1;
    }
};

优化：
在这里插入图片描述

class Solution 
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        //顺序
        vector<int> f(n);
        //逆序
        vector<int> g(n);

        //边界问题特殊处理
        f[0] = 0;
        //f[i] -> [0, i - 1]
        for(int i = 1; i < n; i++)
        {
            f[i] = nums[i - 1] + f[i - 1];
        }

        g[n - 1] = 0;
        for(int i = n - 2; i >= 0; i--)
        {
            g[i] = g[i + 1] + nums[i + 1];
        }

        for(int i = 0; i < n; i++)
        {
            if(f[i] == g[i])
            {
                return i;
            }
        }

        return -1;
    }
};

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

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    除自身以外数组的乘积
  3. 思路：前缀 + 后缀数组
class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        f[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
            f[i] = nums[i] * f[i - 1];
        }

        g[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; i--)
        {
            g[i] = nums[i] * g[i + 1];
        }

        vector<int> ret(n);
        for(int i = 0; i < n; i++)
        {
            if(i == 0)
            {
                ret[i] = g[i + 1];
            }
            else if(i == n - 1)
            {
                ret[i] = f[i - 1];
            }
            else
            {
                ret[i] = g[i + 1] * f[i - 1];
            }
        }

        return ret;
    }
};

优化：
在这里插入图片描述

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);

        f[0] = 1;
        //顺序
        for(int i = 1; i < n; i++)
        {
            f[i] = f[i - 1] * nums[i - 1];
        }

        g[n - 1] = 1;
        //逆序
        for(int i = n - 2; i >= 0; i--)
        {
            g[i] = g[i + 1] * nums[i + 1];
        }

        vector<int> ret(n);
        for(int i = 0; i < n; i++)
        {
            ret[i] = f[i] * g[i];
        }

        return ret;
    }
};

5. !和为k的子数字

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    和为k的子数组
  3. 思路：前缀和，元素没有单调性，无法使用滑动窗口，逆向求sum - k，可以求得为i为尾的所有数组
class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        int ret = 0;
        unordered_map<int ,int> hash;
        //sum - k == 0时，即sum就为k
        hash[0] = 1;

        int sum = 0;
        //用哈希表代替遍历
        for(auto e : nums)
        {
            sum += e;
            if(hash.count(sum - k))
            {
                ret += hash[sum - k];
            }
            //插入哈希表
            //可能存在重复前缀和
            hash[sum]++;
        }

        return ret;
    }
};

6. !和可被k整除的子数组

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    和可被k整除的子数组
  3. 思路：前缀和，哈希表，同余定理，C++中负数除以整数的余数修正(num % k + k) % k
class Solution 
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        int sum = 0;
        unordered_map<int,int> hash;
        int ret = 0;
        int count = 0;
        //sum % k 本身就符合要求
        hash[0] = 1;
        for(auto e : nums)
        {
            sum += e;
            //(sum1 - sum2) % k == 0
            //同余定理
            //负数除整数的余数
            //哈希表中存余数
            if(hash.count((sum % k + k) % k))
            {
                ret += hash[(sum % k + k) % k];
            }
            hash[(sum % k + k) % k]++;
        }

        return ret;
    }
};

7. !连续数组

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    连续数组
    3.思路：前缀加哈希表，求长度，记录下标
class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        for(auto& e : nums)
        {
            if(e == 0)
            {
                e = -1;
            }
        }

        unordered_map<int,int> hash;
        int sum = 0;
        int len = 0;
        //细节，刚好sum为0
        hash[0] = -1;
        for(int i = 0; i < nums.size(); i++)
        {
            //将所有的前缀和与对应下标记录至哈希表中
            sum += nums[i];
            //返回的是长度，最长数组的长度
            if(hash.count(sum) && len < i - hash[sum])
            {
                len = i - hash[sum];
            }
            
            //不存在添加下标
            if(!hash.count(sum))
            {
                hash[sum] = i;
            }
        }

        return len;
    }
};

@8. 矩阵区域和

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    矩阵区域和
  3. 思路：前缀和二维数组，边界问题分析

思路：
在这里插入图片描述
边界问题：
在这里插入图片描述

class Solution 
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        vector<int> part1(mat[0].size(), 0);
        vector<vector<int>> answer(mat.size(), part1);
        vector<int> part2(mat[0].size() + 1, 0);
        vector<vector<int>> dp(mat.size() + 1, part2);
        //二维数组的前缀和
        for (int i = 1; i < dp.size(); i++)
        {
            for (int j = 1; j < dp[0].size(); j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        for (int i = 0; i < mat.size(); i++)
        {
            for (int j = 0; j < mat[0].size(); j++)
            {
                int sum = 0;
                //右下角
                //边界情况，修正
                int pos1 = i + k + 1;
                int pos2 = j + k + 1;
                if (pos1 >= dp.size())
                {
                    pos1 = dp.size() - 1;
                }

                if (pos2 >= dp[0].size())
                {
                    pos2 = dp[0].size() - 1;
                }
                sum += dp[pos1][pos2];

                //右上角
                pos1 = i - k;
                pos2 = j + k + 1;
                //i符合，j不符合
                if (pos1 >= 1 && pos2 >= dp[0].size())
                {
                    pos2 = dp[0].size() - 1;
                }

                if (pos1 >= 1 && pos2 < dp[0].size())
                {
                    sum -= dp[pos1][pos2];
                }

                //左下角
                pos1 = i + k + 1;
                pos2 = j - k;
                //i不符合，j符合
                if (pos1 >= dp.size() && pos2 >= 1)
                {
                    pos1 = dp.size() - 1;
                }

                if (pos1 < dp.size() && pos2 >= 1)
                {
                    sum -= dp[pos1][pos2];
                }

                //左上角
                if (i - k >= 1 && j - k >= 1)
                {
                    sum += dp[i - k][j - k];
                }

                answer[i][j] = sum;
            }
        }

        return answer;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/465356.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

R语言：microeco:一个用于微生物群落生态学数据挖掘的R包，第六：trans_nullmodel class

R语言：microeco:一个用于微生物群落生态学数据挖掘的R包，第六：trans_nullmodel class

近几十年来&#xff0c;系统发育分析和零模型的整合通过增加系统发育维度&#xff0c;更有力地促进了生态位和中性影响对群落聚集的推断。trans_nullmodel类提供了一个封装&#xff0c;包括系统发育信号、beta平均成对系统发育距离(betaMPD)、beta平均最近分类单元距离(betaMNT…
阅读更多...
解决后端传给前端的日期问题

解决后端传给前端的日期问题

解决方式&#xff1a; 1). 方式一 在属性上加上注解&#xff0c;对日期进行格式化 但这种方式&#xff0c;需要在每个时间属性上都要加上该注解&#xff0c;使用较麻烦&#xff0c;不能全局处理。 2). 方式二&#xff08;推荐 ) 在WebMvcConfiguration中扩展SpringMVC的消息转…
阅读更多...
专业120+总400+北京理工大学826信号处理导论考研经验北理工电子信息与通信工程，真题，大纲，参考书。

专业120+总400+北京理工大学826信号处理导论考研经验北理工电子信息与通信工程，真题，大纲，参考书。

**今年专业课826信号处理导论&#xff08;信号系统和数字信号处理&#xff09;120&#xff0c;总分400&#xff0c;应群里同学需要&#xff0c;自己总结一下去年的复习经历&#xff0c;希望对大家复习有帮助。**专业课&#xff1a; 北京理工大学专业826是两门合一&#xff0c;…
阅读更多...
Flutter开发进阶之使用工具效率开发

Flutter开发进阶之使用工具效率开发

Flutter开发进阶之使用工具效率开发 软件开发团队使用Flutter开发的原因通常是因为Flutter开发性能高、效率高、兼容性好、可拓展性高&#xff0c;作为软件PM来说主要考虑的是范围管理、进度管理、成本管理、资源管理、质量管理、风险管理和沟通管理等&#xff0c;可以看到Flu…
阅读更多...
微信小程序调用百度智能云API（菜品识别）

微信小程序调用百度智能云API（菜品识别）

一、注册后生成应用列表创建应用 二、找到当前所需使用的api菜品识别文档 三、点链接看实例代码 这里需要使用到如下几个参数&#xff08;如下&#xff09;&#xff0c;其他的参数可以不管 client_id &#xff1a; 就是创建应用后的API Keyclient_secret&#xff1a; 就是创建…
阅读更多...
Vue mqtt 附在线mqtt客户端地址 + 完整示例

Vue mqtt 附在线mqtt客户端地址 + 完整示例

mqtt&#xff1a;轻量级物联网消息推送协议。 目录 一、介绍 1、官方文档 1&#xff09;npm网 2) 中文网 MQTT中文网_MQTT 物联网接入平台-MQTT.CN 2、官方示例 二、准备工作 1、安装依赖包 2、示例版本 三、使用步骤 1、在单页面引入 mqtt 四、完整示例 tips 一、介…
阅读更多...
正则表达式与re模块

正则表达式与re模块

目录 正则表达式 简介 语法&#xff1a; 常用元字符&#xff1a; 量词: 贪婪匹配和惰性匹配&#xff1a; re模块 简介&#xff1a; 常用的几个模块&#xff1a; 1.findall 2.search 3.finditer 4.compile 案例展示&#xff1a; 需求&#xff1a; 思路分析&#…
阅读更多...
《论文阅读》E-CORE：情感相关性增强的移情对话生成 EMNLP 2023

《论文阅读》E-CORE：情感相关性增强的移情对话生成 EMNLP 2023

《论文阅读》E-CORE：情感相关性增强的移情对话生成 EMNLP 2023 前言摘要模型架构图构建边的构建和初始化节点的初始化图更新情感相关性加强解码损失函数总结前言 亲身阅读感受分享，细节画图解释，再也不用担心看不懂论文啦~ 无抄袭，无复制，纯手工敲击键盘~ 今天为大家带来…
阅读更多...
IDEA 多个git仓库项目放一个窗口

IDEA 多个git仓库项目放一个窗口

1、多个项目先通过新建module或者CtrlAltShiftS 添加module引入 2、重点是右下角有时候git 分支视图只有一个module的Repositories。这时候需要去设置把多个git仓库添加到同一个窗口才能方便提交代码。 3、如果Directory Mappings已经有相关项目配置&#xff0c;但是灰色的&…
阅读更多...
浅谈JPA框架

浅谈JPA框架

JPA 前言概述ORM 映射元数据JPQLJPA API附Spring Data JPA 前言 了解 JPA 框架对后续使用 Spring Boot 是有很大帮助的&#xff0c;下面简单介绍 JPA 框架的基础知识。 概述 JPA&#xff08; Java 对象持久化 API &#xff0c;Java Persistence API &#xff09;&#xff0c…
阅读更多...
物联网数据驾驶舱

物联网数据驾驶舱

在信息化时代&#xff0c;数据已经成为驱动企业发展的核心动力。特别是在物联网领域&#xff0c;海量数据的实时采集、分析和监控&#xff0c;对于企业的运营决策和业务优化具有至关重要的作用。HiWoo Cloud作为领先的物联网云平台&#xff0c;其数据监控功能以“物联网数据驾驶…
阅读更多...
npm包、全局数据共享、分包

npm包、全局数据共享、分包

使用 npm 包 小程序对 npm 的支持与限制 目前&#xff0c;小程序中已经支持使用 npm 安装第三方包&#xff0c;从而来提高小程序的开发效率。但是&#xff0c;在小程序中使用npm 包有如下 3 个限制&#xff1a; ① 不支持依赖于 Node.js 内置库的包 ② 不支持依赖于浏览器内置…
阅读更多...
C++——string

C++——string

一学习string的原因 1.从个人理解角度上&#xff1a; 在刚开始学习之前&#xff0c;我只知道学习完string在以后的刷题中能提高做题效率&#xff0c;在对字符串的处理string库中也许有对应的接口去实现需求&#xff0c;不用自己去写函数的实现。 但在学string中改变了之前的…
阅读更多...
安卓安装Magisk面具以及激活EdXposed

安卓安装Magisk面具以及激活EdXposed

模拟器&#xff1a;雷电模拟器 安卓版本: Android9 文中工具下载链接合集&#xff1a;https://pan.baidu.com/s/1c1X3XFlO2WZhqWx0oE11bA?pwdr08s 前提准备 模拟器需要开启system可写入和root权限 一、安装Magisk 1. 安装magisk 将magisk安装包拖入模拟器 点击&#xff1a…
阅读更多...
UnityShader（十六）凹凸映射

UnityShader（十六）凹凸映射

前言&#xff1a; 纹理的一种常见应用就是凹凸映射&#xff08;bump mapping&#xff09;。凹凸映射目的就是用一张纹理图来修改模型表面的法线&#xff0c;让模型看起来更加细节&#xff0c;这种方法不会改变模型原本的顶点位置&#xff08;也就是不会修改模型的形状&#xf…
阅读更多...
《硬件历险》之Mac抢救出现问题的时间机器硬盘中的数据

《硬件历险》之Mac抢救出现问题的时间机器硬盘中的数据

本文虽然使用“抢救”一词&#xff0c;但是运气比较好&#xff0c;远没有达到访问和修改底层的信息来抢救的地步。如果你是需要通过访问和修改底层信息来抢救数据&#xff0c;建议阅读刘伟的《数据恢复技术深度揭秘&#xff08;第二版&#xff09;》或者寻找专业人士的帮助。 《…
阅读更多...
卷积篇 | YOLOv8改进之C2f模块融合SCConv | 即插即用的空间和通道维度重构卷积

卷积篇 | YOLOv8改进之C2f模块融合SCConv | 即插即用的空间和通道维度重构卷积

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。SCConv是一种用于减少特征冗余的卷积神经网络模块。相对于其他流行的SOTA方法&#xff0c;SCConv可以以更低的计算成本获得更高的准确率。它通过在空间和通道维度上进行重构&#xff0c;从而减少了特征图中的冗余信息。这种…
阅读更多...
留学生课设|R语言|研究方法课设

留学生课设|R语言|研究方法课设

目录 INSTRUCTIONS Question 1. Understanding Quantitative Research Question 2. Inputting data into Jamovi and creating variables (using the dataset) Question 3. Outliers Question 4. Tests for mean difference Question 5. Correlation Analysis INSTRUCTIO…
阅读更多...
深度学习 精选笔记（13.1）卷积神经网络-LeNet模型

深度学习 精选笔记（13.1）卷积神经网络-LeNet模型

学习参考&#xff1a; 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增)&#xff0c;以达到集多方教程的精华于一文的目的。 ③非常推荐上面&#xff08;学习参考&#x…
阅读更多...
SAR ADC教程系列5——FFT频谱泄露以及相干采样

SAR ADC教程系列5——FFT频谱泄露以及相干采样

频谱泄露的出现以及如何规避&#xff1f; 为什么要相干采样&#xff1f; 1.分析ADC输出信号的频谱工具&#xff1a;DFT&#xff08;Discrete Fourier Transform) 重点&#xff1a;DFT相邻频谱频率间隔为fs/N 如何规避频谱泄露&#xff1f; 对于DFT&#xff0c;它对于接收到的信…
阅读更多...
最新文章

Copyright @ 2022~2023