《信息学C++知识讲解》:前缀和算法总结(二)

《信息学C++知识讲解》:前缀和算法总结(二)

前缀和是一个数组的某项下标之前(包括该元素)的所有数组元素的和,前缀和是一种重要的预处理操作,可以降低查询的时间复杂度。
本文以 leetcode 中算法题为例子多前缀和算法的应用进行说明

前缀和应用举例

01、统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。示例 1:输入:nums = [1,1,2,1,1], k = 3 输出:2 解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1]

力扣(LeetCode)第1248道题

同求连续子区间的和,只不过改为了连续子区间的奇数数字个数,同样可以使用前缀和的思路求解。

class Solution {public:    int numberOfSubarrays(vector<int>& nums, int k) {        unordered_map<int,int> mp;//记录 奇数个数-次数        mp[0] = 1;        int count = 0,pre = 0;//仅需要记录前一个值即可,不需要用数组记录所有的前缀和        for(int i = 0;i< nums.size();i++)        {            if( nums[i] % 2 == 1)                pre++;//计算前缀和            if(mp.find(pre-k) != mp.end())//前面结果中存在满足条件的前缀和            {                count+=mp[pre-k];            }            mp[pre]++;        }        return count;    }};

02、连续子数组和

给定一个包含非负数的数组和一个目标整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,总和为  的倍数,即总和为 n*k,其中 n 也是一个整数。示例 1: 输入: [23,2,4,6,7], k = 6 输出: True 解释: [2,4] 是一个大小为 2 的子数组,并且和为 6。

力扣(LeetCode)第523道题

求连续子数组的和可以采用前缀和的思路。区间[i,j]的和为k的倍数,即求  nums[j] –  nums[i] 差为k的倍数,只要 nums[j] 和  nums[i] 除以k的余数相等即满足需求,因此只要记录每个位置前缀和除以k的余数即可。

本题只需要判断是否存在,对于每个余数只需要记录第一次出现位置即可,初始化前缀和为0的位置下标为-1。

当k = 0时,只要存在两个前缀和相等,则区间和为0,同样满足要求。

class Solution {public:    bool checkSubarraySum(vector<int>& nums, int k) {        unordered_map<int,int> pre_map;//记录 前缀和%k - 首次位置        int sum = 0;        pre_map[0]=-1;//初始化前缀和为0的下标为-1        for(int i = 0;i < nums.size();i++)        {            sum += nums[i];//前缀和            if( k != 0)            {                sum = sum%k;//对k求余数            }            if( pre_map.find(sum) != pre_map.end())//存在满足条件的前缀和            {                if( i - pre_map[sum] > 1)//判断长度大于1                    return true;            }            else            {                pre_map.insert({sum,i});            }        }        return false;         }};

03、每个元音包含偶数次的最长子字符串

给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 ‘a’,’e’,’i’,’o’,’u’ ,在子字符串中都恰好出现了偶数次。示例 1:输入:s = “eleetminicoworoep” 输出:13 解释:最长子字符串是 “leetminicowor” ,它包含 e,i,o 各 2 个,以及 0 个 a,u 。

力扣(LeetCode)第1371道题

在题1248统计「优美子数组」中,统计连续子区间奇数数字出现的次数,本题改为了多个字符出现的次数,同样适用前缀和的思路;在题523连续子数组和中,条件是前缀和是k的整数倍,本题中条件为偶数次,即前缀和是2的整数倍,即两个位置对2求余的结果相等即可。

  • 用二进制数字记录状态:我们可以对每个元音字母都维护一个前缀和的数组,实际上我们数组中保存的是每个前缀和对2的余数,即0和1,因此没必要真的维护5个数组,使用一个二进制数字即可表示当前的组合状态,二进制数字中一位代表一个元音字母的状态。比如 00000表示每个元音字母都没出现。本题需求转换为找两个位置的二进制状态相等。
  • 用异或翻转二进制位:用二进制位表示从开始到当前位置的状态,未出现标记成0,出现一次标记为1,再次出现则翻转为0,即某一个位对1进行异或的结果。
  • 哈希表优化:本题中需求为找两个位置的状态相同,并且距离最远。只需要记录每个位置首次出现的位置即可,不断的找相同的状态,越靠后出现的离的越远。
class Solution {public:    int findTheLongestSubstring(string s) {        int res = 0;//保存返回结果        s = '#'+s;//前置添加一个固定字符,初始化-1的位置        unordered_map<int,int> mp;//每种状态首次出现的位置        string str_temp = "aeiou";//同二进制数字中位的位置        int pre = 0;//前缀状态,初始化为00000        for(int i = 0;i < s.length();i++)        {            for(int j = 0;j< 5;j++)            {                if( s[i] == str_temp[j])                    pre = pre^(1 << (4 - j))  ;//对相应位置的状态和1进行异或,0变0、0变1            }            if( mp.find(pre) != mp.end())//状态相等            {                res = max(res,i-mp[pre]);//更新最远距离            }            else            {                mp[pre] = i;//记录首次出现的位置            }        }        return res;    }};

04、二维区域和检索-矩阵不可变

给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。示例: 给定 matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12

力扣(LeetCode)第304题

先构造前缀和,然后可以O(1)计算给出任意子矩阵的和。

class NumMatrix {public:    vector<vector<int>> presum;//记录前缀和    int rowcount =0;    int colcount = 0;     NumMatrix(vector<vector<int>>& matrix) {        rowcount = matrix.size();        if( rowcount  == 0 ) return;        else            colcount = matrix[0].size();        if(colcount == 0 ) return;
presum = vector(rowcount,vector(colcount,0));//初始化前缀和数组 //构造前缀和数组,presum[i][j] = nums[i][j] + presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1] for(int i =0;i < rowcount;i++) { for(int j = 0;j < colcount;j++) { presum[i][j] = matrix[i][j]; if( i-1 >= 0) presum[i][j] += presum[i-1][j] ; if( j-1 >= 0) presum[i][j] += presum[i][j-1] ; if( i-1>= 0 && j-1 >= 0) presum[i][j] -= presum[i-1][j-1] ; } } } int sumRegion(int row1, int col1, int row2, int col2) { if(rowcount == 0 || colcount == 0) return 0; //子矩阵和公式:presum[row2][col2] - presum[row1-1][col2] - presum[row2][col1-1] +presum[row1-1][col1-1] int res = presum[row2][col2]; if( row1 -1 >=0) res -= presum[row1-1][col2]; if( col1 -1 >=0) res -= presum[row2][col1-1]; if(row1 -1 >= 0 && col1-1 >=0 ) res += presum[row1-1][col1-1]; return res; }};
/** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */

微信扫码领取0元编程课


核桃编程-弹窗图

This will close in 180 seconds

少儿编程0元课

 
少儿编程0元课  

少儿素质课推荐

 
少儿素质课推荐  

少儿逻辑0元课

 
少儿逻辑0元课  

公众号

关注公众号

x
少儿编程学习网
专注青少年编程学习、课程推荐、科技特长生规划
2023-06-06 14:32:49
您好,有任何疑问请与我们联系!
您的工单我们已经收到,我们将会尽快跟您联系!
[官方群:675726029]
[Mars老师:Qbit-School]
[Mars老师]
17732463686
取消

选择聊天工具: