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

前缀和算法习题篇(下)

在这里插入图片描述

1.寻找数组的中心下标

题目描述:

给你一个整数数组 nums ,请计算数组的 中心下标

数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1

示例 1:

输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。

示例 2:

输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。

示例 3:

输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

算法思路:

  • 从题目我们可以知道,除了中心下标的元素以外,该元素左边的前缀和等于该元素右边的后缀和。

  • 所以,我们可以先预处理出来两个数组,一个表示前缀和,另一个表示后缀和。

  • 最后,用一个for循环枚举可能的中心下标,判断每一个位置的前缀和以及后缀和,如果两者相等,就返回当前下标。

代码实现:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n),g(n);
        
        //1.处理前缀和数组以及后缀和数组
        for(int i=1;i<n;i++)
          f[i]=f[i-1]+nums[i-1];
        for(int i=n-2;i>=0;i--)
          g[i]=g[i+1]+nums[i+1];
        
        //2.用for循环枚举可能得中心下标
        for(int i=0;i<n;i++)
          if(f[i]==g[i])
            return i;
        return -1;
    }
};
  • 细节问题: f[0]=g[n-1]=0;(不用写在代码里,原因是vector不初始化时,默认值为0)

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

题目描述:

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法,**且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

算法思路:

  • 从题目中我们知道不能使用除法,所以我们不能使用暴力求解的方法——求出整个数组的乘积,然后除以单个元素的方法。
  • 而对于每一个位置的最终结果ret[i],它由两部分的乘积组成——该位置前的元素的积与该位置后的元素的积。所以,我们可以先预处理出来两个数组,一个表示前缀积,另一个表示后缀积。
  • 最后,用一个for循环枚举当前下标,求出当前下标的值,然后返回。

代码实现:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n),g(n);
        
        //1.处理前缀积数组以及后缀积数组
        f[0]=g[n-1]=1;//细节问题
        for(int i=1;i<n;i++)
          f[i]=f[i-1]*nums[i-1];
        for(int i=n-2;i>=0;i--)
          g[i]=g[i+1]*nums[i+1];
        
        //2.用for循环枚举当前下标
        vector<int> ret(n);
        for(int i=0;i<n;i++)
          ret[i]=f[i]*g[i];

        return ret;
    }
};
  • 细节问题: f[0]=g[n-1]=1;

3.和为K的子数组

题目描述:

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数

子数组是数组中元素的连续非空序列。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

提示:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

算法思路:

  • 设 i 为数组中的任意位置,用 sum[i] 表示[0, i] 区间内所有元素的和。

  • 想知道有多少个以 i 为结尾的和为 k 的子数组,就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和为 k 。那么 [0, x] 区间内的和是不是就是sum[i] - k 了。

  • 于是问题就变成:找到在 [0, i - 1] 区间内,有多少前缀和等于 sum[i] - k 的即可。

  • 我们不用真的初始化⼀个前缀和数组,因为我们只关心在 i 位置之前,有多少个前缀和等于sum[i] - k 。因此,我们仅需用一个哈希表,一边求当前位置的前缀和,⼀边存下之前每⼀种前缀和出现的次数。

代码实现:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;//统计前缀和出现的次数
        hash[0]=1;

        int sum=0,ret=0;
        for(auto x:nums)
        {
            sum+=x;//计算当前位置的前缀和
            if(hash.count(sum-k)) 
              ret+=hash[sum-k];//统计个数
            hash[sum]++;
        }
        return ret;
    }
};

4.和可被K整除的子数组

题目描述:

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1:

输入:nums = [4,5,0,-2,-3,1], k = 5
输出:7
解释:
有 7 个子数组满足其元素之和可被 k = 5 整除:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

算法思路:

同余定理

如果 (a - b) % n == 0 ,那么我们可以得到⼀个结论: a % n == b % n 。⽤文字叙述就是,如果两个数相减的差能被 n 整除,那么这两个数对 n 取模的结果相同。

在C++中负数取模的结果,以及如何修正负数取模的结果

a%p修正之后(正负统一)——>(a%p+p)%p。

  • 设 i 为数组中的任意位置,用sum[i] 表示[0, i] 区间内所有元素的和。

  • 想知道有多少个以 i 为结尾的可被 k 整除的子数组,就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和可被 k 整除。

  • 设 [0, x - 1] 区间内所有元素之和等于 a , [0, i] 区间内所有元素的和等于 b ,可得(b - a) % k == 0 。由同余定理可得, [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。

  • 于是问题就变成:找到在 [0, i - 1] 区间内,有多少前缀和的余数等于 sum[i] % k 的即可。

  • 我们不用真的初始化⼀个前缀和数组,因为我们只关心在 i 位置之前,有多少个前缀和等于sum[i] - k 。因此,我们仅需用⼀个哈希表,⼀边求当前位置的前缀和,⼀边存下之前每⼀种前缀和出现的次数。

代码实现:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0%k]=1;//0 这个数的余数

        int sum=0,ret=0;
        for(auto x:nums)
        {
            sum+=x;//算出当前位置的前缀和
            int r=(sum%k+k)%k;//修正后的余数
            if(hash.count(r)) 
              ret+=hash[r];//统计结果
            hash[r]++;
        }
        return ret;
    }
};

5.连续数组

题目描述:

给定一个二进制数组 nums , 找到含有相同数量的 01 的最长连续子数组,并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示:

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1

算法思路:

  • 我们可以稍微转化一下题目,把它变成我们所熟悉的题型。

  • 本题让我们找出一段连续的区间, 0 和 1 出现的次数相同。如果将 0 记为 -1 , 1 记为 1 ,问题就变成了找出一段区间,这段区间的和等于 0 。于是,就和 (和为 K 的子数组 )这道题的思路⼀样。

  • 设 i 为数组中的任意位置,用sum[i] 表⽰ [0, i] 区间内所有元素的和。

    想知道最大的以 i 为结尾的和为 0 的子数组,就要找到从左往右第一个 x1 使得 [x1, i]区间内的所有元素的和为 0 。那么 [0, x1 - 1] 区间内的和是不是就是 sum[i] 了。

  • 于是问题就变成:找到在 [0, i - 1] 区间内,第⼀次出现 sum[i] 的位置即可。

  • 我们不用真的初始化⼀个前缀和数组,因为我们只关心在 i 位置之前,第一个前缀和等于 sum[i]的位置。因此,我们仅需用⼀个哈希表,⼀边求当前位置的前缀和,⼀边记录第⼀次出现该前缀和的位置。

代码实现:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> hash;
        hash[0]=-1;//默认有一个前缀和为0的情况

        int sum=0,ret=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i]==0?-1:1;//计算当前位置的前缀和
            if(hash.count(sum))
              ret=max(ret,i-hash[sum]);
            else
              hash[sum]=i;
        }
        return ret;
    }
};

6.矩阵区域和

题目描述:

给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和:

  • i - k <= r <= i + k,
  • j - k <= c <= j + k
  • (r, c) 在矩阵内。

示例 1:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]

示例 2:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100

算法思路;

  • 由题目知,我们在填写结果矩阵的时候,要找到原矩阵对应区域的左上角以及右下角的坐标

  • 左上角坐标: x1 = i - k,y1 = j - k ,但是由于会「超过矩阵」的范围,因此需要对 0取⼀个 max 。因此修正后的坐标为: x1 = max(0, i - k), y1 = max(0, j - k) ;

  • 右下角坐标: x1 = i + k,y1 = j + k ,但是由于会「超过矩阵」的范围,因此需要对 m - 1 ,以及 n - 1 取⼀个 min 。因此修正后的坐标为: x2 = min(m - 1, i + k), y2 = min(n - 1, j + k) 。

  • 然后将求出来的坐标代入到二维前缀和矩阵的计算公式上即可~(但是要注意下标的映射关系)

代码实现:

class Solution 
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m=mat.size(),n=mat[0].size();
        //1.预处理一个前缀和矩阵
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
          for(int j=1;j<=n;j++)
            dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mat[i-1][j-1];

        //2.使用
        vector<vector<int>> ret(m,vector<int>(n));
        for(int i=0;i<m;i++)
          for(int j=0;j<n;j++)
          {
            int x1=max(0,i-k)+1,y1=max(0,j-k)+1;
            int x2=min(m-1,i+k)+1,y2=min(n-1,j+k)+1;
            ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
          }
        return ret;
    }
};

最后,本篇文章到此结束,感觉不错的友友们可以一键三连支持一下笔者,有任何问题欢迎在评论区留言哦~
在这里插入图片描述


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

相关文章:

  • Linux自动挂载磁盘的方法
  • 创建一个简单的spring boot+vue前后端分离项目
  • 芯片详细讲解,从而区分CPU、MPU、DSP、GPU、FPGA、MCU、SOC、ECU
  • Weblogic - General - 弱口令 任意文件读取漏洞
  • Ceph与RAID在存储中的协同工作过程
  • LeetCode - #187 Swift 实现重复的DNA序列
  • 网络安全---CMS指纹信息实战
  • [练习]简单结构体操作程序
  • 告别 Excel,拥抱 R 语言:开启数据分析新时代
  • k8s集成MinIo
  • 精品PPT | 某制造集团灯塔工厂解决方案
  • C# 操作 文件
  • [STM32 HAL库]串口中断编程思路
  • 微服务入门:从零开始构建你的微服务架构
  • xiao esp32 S3播放SD卡wav音频
  • 最大矩阵面积问题
  • 【GPT进化之路】从 GPT-1 的初试锋芒到 GPT-4 的跨模态智能时代
  • 青少年CTF练习平台 EasyMD5解题思路
  • go语言zero框架通过chromedp实现网页在线截图的设计与功能实现
  • SQLMAP的下载安装和使用(Windows)
  • HTML 的基础知识及其重要性
  • go语言 goc覆盖率统计
  • 如何安装linux版本的node.js
  • 本地仓库管理之当前分支内的操作
  • Stata应用:将数据“画”在中国地图上|Python数据分析
  • springboot财务管理系统