0


★ 算法OJ题 ★ 前缀和算法(上)

Ciallo~(∠・ω< )⌒☆ ~ 今天,将和大家一起做几道前缀和算法题 ~

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页:椎名澄嵐-CSDN博客

算法专栏:★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️


壹 【模板】一维前缀和

1.1 题目

【模板】前缀和_牛客题霸_牛客网

1.2 算法解析

1.3 撰写代码

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int main()
  5. {
  6. // 读取数据
  7. int n, q;
  8. cin >> n >> q;
  9. vector<int> arr(n + 1);
  10. for (int i = 1; i <= n; i++) cin >> arr[i];
  11. // 预处理前缀和数组
  12. vector<long long> dp(n + 1);
  13. for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];//此处有溢出风险
  14. // 使用前缀和数组
  15. int l = 0, r = 0;
  16. while(q--)
  17. {
  18. cin >> l >> r;
  19. cout << dp[r] - dp[l - 1] << endl;
  20. }
  21. return 0;
  22. }

贰 【模板】二维前缀和

2.1 题目

【模板】二维前缀和_牛客题霸_牛客网

2.2 算法解析

2.3 撰写代码

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int main()
  5. {
  6. // 读入数据
  7. int n = 0 , m = 0, q = 0;
  8. cin >> n >> m >> q;
  9. vector<vector<int>> arr(n + 1, vector<int>(m + 1));
  10. for (int i = 1; i <= n; i++)
  11. for (int j = 1; j <= m; j++)
  12. cin >> arr[i][j];
  13. // 预处理前缀和矩阵
  14. vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
  15. for (int i = 1; i <= n; i++)
  16. for (int j = 1; j <= m; j++)
  17. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
  18. // 使用前缀和矩阵
  19. int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
  20. while(q--)
  21. {
  22. cin >> x1 >> y1 >> x2 >> y2;
  23. cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
  24. }
  25. return 0;
  26. }

叁 寻找数组的中心下标

3.1 题目

  1. 寻找数组的中心下标 - 力扣(LeetCode)

3.2 算法解析

3.3 撰写代码

  1. class Solution {
  2. public:
  3. int pivotIndex(vector<int>& nums)
  4. {
  5. int n = nums.size();
  6. vector<int> f(n);
  7. vector<int> g(n);
  8. // 预处理前缀和数组和后缀和数组
  9. for (int i = 1; i < n; i++)
  10. f[i] = f[i - 1] + nums[i - 1];
  11. for (int i = n - 2; i >= 0; i--)
  12. g[i] = g[i + 1] + nums[i + 1];
  13. // 使用前缀和数组和后缀和数组
  14. for (int i = 0; i < n; i++)
  15. if(f[i] == g[i])
  16. return i;
  17. return -1;
  18. }
  19. };


肆 除自身以外数组的乘积

4.1 题目

  1. 除自身以外数组的乘积 - 力扣(LeetCode)

4.2 算法解析

4.3 撰写代码

  1. class Solution {
  2. public:
  3. vector<int> productExceptSelf(vector<int>& nums)
  4. {
  5. int n = nums.size();
  6. vector<long long> f(n), g(n);
  7. // 预处理前缀积和后缀积
  8. f[0] = g[n - 1] = 1;
  9. for (int i = 1; i <= n - 1; i++)
  10. f[i] = f[i - 1] * nums[i - 1];
  11. for (int i = n - 2; i >= 0; i--)
  12. g[i] = g[i + 1] * nums[i + 1];
  13. // 使用前缀积和后缀积
  14. vector<int> ret(n);
  15. for (int i = 0; i <= n - 1; i++)
  16. ret[i] = f[i] * g[i];
  17. return ret;
  18. }
  19. };


~ 完 ~


本文转载自: https://blog.csdn.net/2302_80328146/article/details/143209772
版权归原作者 椎名澄嵐 所有, 如有侵权,请联系我们删除。

“★ 算法OJ题 ★ 前缀和算法(上)”的评论:

还没有评论