【C++例题/训练】：前缀和&&差分

IsLand1314

发布于 2024-10-15 20:14:49

970

文章被收录于专栏：学习之路

🚀 前言：

前面我们已经通过【算法/学习】前缀和&&差分-CSDN博客学习了前缀和&&差分的效相关知识，现在我们开始进行相关题目的练习吧

1. 校门外的树

思路：给[0, n]的数组都标记为1，然后输出m行范围，[l, r]都标记为0。

AC代码如下：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n, m;
    cin>>n>>m;
    for(int i = 0; i <= n; i++) a[i] = 1;
    int l, r;
    for(int i = 1; i <= m; i++)
    {
        cin>>l>>r;
        for(int j = l; j <= r; j++) a[j] = 0;
    }
    int cnt = 0;
    for(int i = 0; i <= n; i++) {
        if(a[i] == 1) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

2. 值周

思路： 该题与上题意思相同，但是数据范围更大，因此我们不能使用上面的方法，我们可以使用前缀和，使让数组a内的数据先初始化为0，然后对[ l, r ]进行操作，a[l]--, a[r + 1]++，然后操作M次后，再 a[i] += a[i - 1];这样可以使得每个区域内的数都小于0.

AC代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7 + 10;

int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    int l, r;
    for (int i = 0; i < m; i++){
        cin >> l >> r;
        a[l]--, a[r + 1]++;  //前缀和，l-r标记为-1，r + 1又标记为1
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
    }
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        if (a[i] >= 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

3. 中位数图

思路： 🔥1.由于是求中位数是b的连续子序列，那么我们只要找到一串连续的数，里面包含数b，且大于b的数的数目与小于b的数的数目相等，才是我们要找的序列。 🔥2.由于数据范围给的比较大，我们可以简化一下，把比b大的数直接赋值为1，小的就赋值为-1. 同时，我们再用一个sum来求和，sum往一边统计的时候，当sum==0的时候说明大于b的数的数目与小于b的数的数目相等，也就是我们找到了一个序列。 🔥3.那么两边都有的情况怎么考虑呢？我们可以往一边记录，用一个num数组来记录sum的加减情况。我们可以来看一下题目的样例： {5，7，2，4，3，1，6}->{1，1，-1，4，-1，-1，1} 🔥往左遍历： 1.sum+=-1-->sum==-1,可以这样，num[n+sum]+=1,也就是左边有一个比b小的情况加1. 2.sum+=1->sum==0,num[n+sum]+=1，左边刚好找到一个成功的序列，ans++. 3.sum+=1-->sum==1,num[n+sum]+=1,左边有一个比b大的情况加一。 🔥现在往右遍历：先初始化sum=0. 然后sum+=-1->sum==-1,右边找到了一个比b小的数，而num[n+1]表示左边有一个比b小的情况的数目，也就是num[n-sum],我们可以用ans+=num[n-sum]。后面同理，最后ans==4.（ans初始值为1，因为自己本身也是一个序列）

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
ll a[N], s[N];

int main()
{
	int n, b;
	cin >> n >> b;
	int pos, x;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] > b)a[i] = 1;
		else if (a[i] < b) a[i] = -1;
		else pos = i;//标记中位数的位置
	}

	ll sum = 0, ans = 1; //自己也算一个
	for (int i = pos - 1; i >= 1; i--) {
		sum += a[i];
		s[n + sum]++; //记录左边和为sum的数量
		if (!sum) ans++; //sum为零就说明小于b的数的数量于大于b的数量相同
	}
	sum = 0; //再往右遍历，同时与左边比较
	for (int i = pos + 1; i <= n; i++) {
		sum += a[i];
		ans += s[n - sum]; //加上左边与其互补的数量
		if (!sum) ans++;
	}
	cout << ans << endl;
}

4. 激光炸弹

思路：先用二维前缀和的公式，求出g[x][y]的矩阵内的价值，然后就开始记录哪个正方形内的价值最大即可

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;
int n, R;
int g[5005][5005];

int main()
{
	cin >> n >> R;
	memset(g, 0, sizeof g);
	int xx = R, yy = R; //xx和yy表示边界，初始化为最小的R
	for (int i = 0; i < n; i++)
	{
		int x, y, v;
		cin >> x >> y >> v;
		g[x][y] = v;
		xx = max(xx, x); //记录输入的最大边
		yy = max(yy, y); 
	}

	for (int i = 1; i <= xx; i++){
		for (int j = 1; j <= yy; j++){
			g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];
		}
	}

	int ans = 0;
	for (int i = R; i <= xx; i++){
		for (int j = R; j <= yy; j++) {
			ans = max(ans, g[i][j] - g[i - R][j] - g[i][j - R] + g[i - R][j - R]);
		}
	}
	
	cout << ans << endl;
	return 0;
}

5. 二分

思路：题意是求裁判最多说对了几次。对于每次猜数，如果猜的数是𝑎a，那么根据题目有三种情况：

数大了：说对的范围是(−inf⁡,𝑎](−inf,a]
数小了：说对的范围是[𝑎,+inf⁡)[a,+inf)
数相等：说对的范围是[𝑎,𝑎+1)[a,a+1)

序列上操作，那么差分可以满足；然后把上面这些区间中，重叠次数最多的区间求出来，就是数所在的区间；这个区间重叠的次数就是我们要的答案。由于数字较大，所以用了map搞离散化。

#include <iostream>
#include <map>
#include <limits.h>
using namespace std;

const int inf = INT_MAX;//int型数据最大值，因为是对每个数进行统计

const int N = 1e7 + 10;
int a[N];
char s[N];
map<int, int> mp;

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> s[i];
	for (int i = 1; i <= n; i++){
		if (s[i] == '.') mp[a[i]]++, mp[a[i] + 1]--;
		if (s[i] == '+') mp[a[i]]--, mp[-inf]++;
		if (s[i] == '-')mp[inf]--, mp[a[i] + 1]++;
	}

	int ans = -inf, h = 0;
	for (auto e : mp){
		h += e.second;
		ans = max(h, ans);
	}

	cout << ans << endl;
}

6. 货仓选址

思路：如下图，选择n个仓库位置得中位数即可，该问题的本质就是求

的最小总和即可，当我们以后遇到该类问题时，只要使得p为所有ai的中位数即可

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> a;
	for (int i = 0; i < n; i++){
		int x;
		cin >> x;
		a.push_back(x);
	}
	sort(a.begin(), a.end());
	int p = a[a.size() / 2];
	int ans = 0;
	for (int i = 0; i < n; i++) ans += abs(a[i] - p);
	cout << ans << endl;
	return 0;
}

7. 最大子矩阵

思路： 求出其对应的前缀和矩阵，然后由于数据是从 1- 109，直接枚举即可。

int getMaxMatrix(vector<vector<int>>& matrix) {
	int n = matrix.size();
	// 1.预处理前缀和
	vector<vector<int>> s(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
		}
	}
	vector<int> ans(4);
	int ret = -1e6 + 10;
	// 2.找最大子矩阵 (四重for循环)
	for (int x1 = 1; x1 <= n; x1++) {
		for (int y1 = 1; y1 <= n; y1++) {
			for (int x2 = x1; x2 <= n; x2++) {
				for (int y2 = y1; y2 <= n; y2++) {
					ret = max(ret, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
				}
			}
		}
	}
	return ret;
}

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	cout << getMaxMatrix(a) << endl;

	return 0;
}

8. 主持人调度（二)

思路： 差分数组，题目等同于求当前位置最大被多少个区间包围。

//方法一：差分数组的映射
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
	map<int, int> mp;
	for (int i = 0; i < startEnd.size(); i++) {
		mp[startEnd[i][0]]++; //左边 ++
		mp[startEnd[i][1]]--; //右边 --
	}
	int ans = 0, res = 0;
	for (auto ip : mp) {
		res += ip.second;
		ans = max(ans, res);
	}
	return ans;
}

9. 寻找数组的中心下标

题目描述：给你一个整数数组 nums ，请计算数组的 中心下标 。

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

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

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

思路： 假设两个数组 f，g f [ i ] 表示：[0, i - 1] 区间内所有元素的和（前缀和数组）

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

g[ i ] 表示：[i + 1, n - 1] 区间内所有元素的和（后缀和数组）

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

则此时问题转化为求 [0, n] 内存在 i 使得 f [ i ] = g[ i ] 注：为避免越界访问，则 f [ 0 ] = g[ n - 1 ] = 0 填表顺序：f 表从左往右，g表从右往左

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

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

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

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

思路： 该题与上题思路相同。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        vector<int> f(n, 1), 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];

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

11. 和为 K 的子数组

题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。（注：子数组内的数字可能是负数）

思路： 以 i 位置内为结尾的所有子数组，在[0，i - 1] 区间内，找有多少个前缀和等于 sum[ i ] - k 我们可以用一个哈希 <前缀和，该前缀和出现次数>来记录。细节处理：

在计算 i 位置之前，哈希表里面只保存 [0，i - 1] 位置的前缀和
用一个变量 sum 标记前一个位置的前缀和
假设枚举到 0 位置时此时的整个前缀和为 k，那么就会去[0，-1]区间内找前缀和为0的，因此先需要初始化：hash[ 0 ] = 1

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))  // 如果在当前位置，哈希表内存在某个和等于 sum - k
                ret += hash[sum - k]; //统计个数
            hash[sum]++; 
        }
        return ret;
    }
};

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

题目描述：给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中连续的部分。

思路： 该题与上题思路类型。我们先来补充几个知识。 同余定理：

（a - b）% p = 0 --- > a % p = b % p

【负数 % 正数】的结果以及修正：

负数 % 正数 = 负数 --> (修正) a % p + p --> (正负统一) （a % p + p） % p

看完上面两个补充知识之后，只需在[0，i - 1] 区间内，找有多少个前缀和余数等于 sum % k，注：需要避免为负数要记得修正。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;

        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;
    }
};

13. 连续数组

题目描述：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

思路： 我们可以数组中所有的 0 修改成 -1，这题就转化成找出最长的子数组，使得子数组的所有元素的和为0即可，那么该题就与和为 K 的子数组类似，和为K的子数组 --> 和为0的子数组但是我们这题需要求的是长度。那么我们这里的哈希表应该是<前缀和，前缀和下标> 细节处理：

当前位置使用完之后就丢进哈希表。
如果出现了重复的 <sum，i>，只保留前面的那一对<sum，i>
规定空的前缀的结束下标为 −1，由于空的前缀的元素和为 0，因此在遍历之前，首先在哈希表中存入键值对 (0,−1)：hash[ 0 ] = -1
长度计算：在遍历过程中，对于每个下标 i，如果 sum 的值在哈希表中已经存在，则取出 sum 在哈希表中对应的下标 j，nums 从下标 j + 1 到下标 i 的子数组中有相同数量的 0 和 1，因此该子数组的长度为 i − j，（不包括 j 那个格子）使用该子数组的长度更新最长连续子数组的长度；如果 counter 的值在哈希表中不存在，则将当前余数和当前下标 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; //为 0 时则处理为 -1
            if (hash.count(sum)) //判断当前前缀和是否存在
                ret = max(ret, i - hash[sum]);
            else hash[sum] = i; // 不存在才存，因为要存该前缀和对应的最小的下标
        }
        return ret;
    }
};

14. 矩阵区域和

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

思路： 用二维前缀和求法：sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[ i ][ j ];求得该矩阵的前缀和 answer[ i ][ j ] 的求法：则相当于是以[i，j]为中心从[i - k，j - k] 到 [i + k，j + k] 的矩阵，注意越界的问题，因此我们应该做一些特殊处理如 x1 = max (0，i - k) ，x2 = min (m - 1，i + k) 还要注意下标的映射问题：我们在填前缀和表时，需要多加一行一列，此时前缀和上的下标[i,，j] 在mat矩阵上的映射应该为[i - 1，j - 1]，然后我们使用前缀和表去填answer时，answer表上的下标[i，j]在前缀和表上的映射应该为[i + 1，j + 1]

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> sum(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        vector<vector<int>> answer(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;
                // 填表
                answer[i][j] = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
            }
        }
        return answer;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-24，如有侵权请联系 cloudcommunity@tencent.com 删除

数据