算法学习总结(未完待续)
2021/11/4 11:09:53
本文主要是介绍算法学习总结(未完待续),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分查找
- 35
- 34
- 1
- 69
- 1658
- 81
- 475
- 300
- 1011
- 4
// 普通二分算法,查找target目标值 while (l < r) { int mid = (l + r) >> 1; if (nums[mid] < target) { l = mid + 1; } else if (nums[mid] > target) { r = mid - 1; } else { // nums[mid] == target return mid; } } return -1; // 没有找到 // 查找第一个大于等于target值的下标 while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= target) { r = mid; // r为最终结果 } else { l = mid + 1; } } // 查找第一个大于target值的下标 while (l < r) { int mid = (l + r) >> 1; if (nums[mid] > target) { r = mid; // r为最终结果 } else { l = mid + 1; } }
并查集
Class UnionSet { public: int *fa, n; UnionSet(int n) : n(n) { fa = new int[n + 1]; for (int i = 0; i <= n; i++) fa[i] = i; } int get(int x){ return fa[x] = (fa[x] == x ? x : get(fa[x]); } void merge(int a, int b) { fa[get[a]] = get(b); } };
单调队列
用于求RMQ(Range Minimum/Maximum Query)问题——求区间最值的问题
- 239、滑动窗口最大值 / 剑指 Offer 59 - I、 滑动窗口的最大值
- 剑指 Offer 59 - II、 队列的最大值
- 862、和至少为k的最短子数组(单调队列/滑动窗口)
- 1438、绝对差不超过限制的最长连续子数组(滑动窗口 + 单调队列)
vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> q; vector<int> ret; for (int i = 0; i < nums.size(); i++) { while (q.size() && nums[q.back()] < nums[i]) { q.pop_back(); } q.push_back(i); if (i - q.front() == k) { q.pop_front(); } if (i + 1 < k) { continue; } ret.push_back(nums[q.front()]); } return ret; }
单调栈
找到下一个更大/更小的元素
- 496、下一个更大元素 I
- 503、下一个更大元素 II
- 739、每日温度 / 剑指 Offer II 038、每日温度
- 901、 股票价格跨度
vector<int> nextGreatElement(vector<int> & num1, vector<int> & nums2) { vector<int> ret(nums.size()); stack<int> s; for (int i = 0; i < nums.size(); i++) { while(s.size() && nums[s.top()] < nums[i]]) { ret[s.top()] = nums[i]; s.pop(); } s.push(i); } return ret; }
字典树(Tire)
滑动窗口
- 76、最小覆盖子串 / 剑指 Offer II 017、 含有所有字符的最短字符串
- 剑指 Offer II 014. 字符串中的变位词 / 567、 字符串的排序
- 438、 找到字符串中所有字母异位词 / 剑指 Offer II 015、 字符串中的所有变位词
- 剑指 Offer 48、 最长不含重复字符的子字符串 / 3、 无重复字符的最长子串 / 剑指 Offer II 016、 不含重复字符的最长子字符串
- 超级短串
void slidingWindow(string s, string t) { unordered_map<char, int> h, window; for (char c : t) { h[c]++; } int l = 0; int r = 0; int valid = 0; while (right < s.size()) { char c = s[r]; r++; ... // 进行窗口内数据的一系列更新 while (window needs shrink) { char d == s[l++]; l++; ... // 进行窗口内数据的一系列更新 } } }
贪心与区间问题(区间贪心)
- 435
- 452
差分
- 1094、 拼车
- 1107、 航班系统预订
差分数组对应的概念是前缀和数组,对于数组 [1,2,2,4],其差分数组为 [1,1,0,2],差分数组的第 i 个数即为原数组的第 i-1 个元素和第 i 个元素的差值,也就是说我们对差分数组求前缀和即可得到原数组。
差分数组的性质是,当我们希望对原数组的某一个区间[l,r]施加一个增量inc时,差分数组 d 对应的改变是:d[l] 增加 inc ,d[r+1] 减少 inc。这样对于区间的修改就变为了对于两个位置的修改。并且这种修改是可以叠加的,即当我们多次对原数组的不同区间施加不同的增量,我们只要按规则修改差分数组即可。
未完待续
这篇关于算法学习总结(未完待续)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统