算法笔记-滑动窗口&双指针
2021/9/17 11:05:00
本文主要是介绍算法笔记-滑动窗口&双指针,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
滑动窗口
-
分析题意,确定窗口的意义
-
设置窗口的left,right指针:
(1)先移动右指针,当窗口满足条件时,记录状态;
(2)再移动左指针,寻找下一个窗口
leetcode.1208 尽可能使字符串相等
class Solution { public: int equalSubstring(string s, string t, int maxCost) { int res = 0; int n = min(s.size(), t.size()); vector<int> cost(n, 0); for (int i = 0; i < n; ++i) { cost[i] = abs(s[i] - t[i]); } int left = 0; int right = 0; int winSum = 0; while (right < n) { winSum += cost[right]; while (winSum > maxCost) { winSum -= cost[left]; left++; } res = max(res, right - left + 1); right++; } return res; } };
差分
一维差分
- 定义
vector<int> nums = {1, 2, 5, 8, 13}; vector<int> diff(nums.size()); for (int i = 1; i < diff.size(); ++i) { diff[i] = nums[i] - nums[i-1]; }
- 用法
进行区间的修改,比如某区间增加或者删减一个值
对区间[x, y)增加1,则:
// [x, y)增加1 diff[x] += 1; diff[y] -= 1;
-
对某数组的某区间进行频繁增减操作:
(1)先求出其对应差分数组;
(2)对差分数组进行处理;
(3)遍历差分数组,求前缀和,即可还原数组。
leetcode.1094 拼车
class Solution { public: bool carPooling(vector<vector<int>>& trips, int capacity) { int MAX_LEN = 1e3 + 1; vector<int> diff(MAX_LEN); for (const auto& tp: trips) { int nums = tp[0]; int start = tp[1]; int end = tp[2]; diff[start] += nums; diff[end] -= nums; } int counts = 0; for (const auto& i: diff) { counts += i; if (counts > capacity) return false; } return true; } };
前缀和
一维前缀和
vector<int> nums(n, 0); 对应的前缀和数组为: // 长度加1 vector<int> preSum(n + 1, 0); // 初始化 for (int i = 1; i < preSum.size(); ++i) { preSum[i] = preSum[i-1] + nums[i-1]; } // 计算[i, j)区间内的子序和 // i [0, n-1], j [1, n] int sum = preSum[j] - preSum[i] // 以0位为第一个元素的所有区间前缀和 for (int i = 1; i < preSum.size(); ++i) { cout << preSum[i] - preSum[0] << endl; }
leetcode.560 和为k的子数组
class Solution { public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(); vector<int> preSum(n + 1, 0); for (int i = 1; i < preSum.size(); ++i) { preSum[i] = preSum[i-1] + nums[i-1]; } int res = 0; unordered_map<int, int> mp; mp[0] = 1; for (int j = 1; j <= n; ++j) { int require = preSum[j] - k; if (mp.find(require) != mp.end()) { res += mp[require]; } mp[preSum[j]]++; } return res; };
二维差分及前缀和
https://www.cnblogs.com/LMCC1108/p/10753451.html
二维前缀和 -> leetcode.304
这篇关于算法笔记-滑动窗口&双指针的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署