
目录
- 持续更新中...
- 1、双指针
- 移动零
- 复写零
- 快乐数
- 长度最小的子数组
- dd爱框框
- 2、递归与回溯
- 3、排序算法
- 4、查找算法
持续更新中…
1、双指针
- 对撞指针:一般用于顺序结构中,也称左右指针。两指针从两端向中间移动,一个指针从最左端开始,另一个从最右端开始,然后逐渐往中间逼近。终止条件一般是两个指针相遇或者错开
left == right
||left > right
。 - 快慢指针:让两个移动速度不同的指针在数组或链表等序列结构上移动,经典用法有环形链表。如果我们要研究的问题出现循环往复的情况时,均可考虑快慢指针。
- 滑动窗口:维护一个动态的窗口,在满足某些条件的情况下移动窗口,从而避免重复计算,提高效率。
移动零
- 移动零
数组划分,根据某种规则将数组分为不同性质的两块。
这道题中用 l,r 维护一段区间,区间内全都是0。也就是说 l 始终指向的数字就是0。
class Solution {
public:void moveZeroes(vector<int>& nums) {int l = 0, r = 0;while (r < nums.size()){if (nums[r]) swap(nums[r], nums[l++]);r++;}}
};
复写零
- 复写零
快乐数
- 快乐数
类似链表中带环的问题,当快慢指针相遇时入环。
class Solution {
public:int func(int m){int sum = 0;while (m){sum += pow(m % 10, 2);m /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = func(n);while (slow != fast){slow = func(slow);fast = func(func(fast));}return slow == 1;}
};
长度最小的子数组
- 长度最小的子数组
dd爱框框
- dd爱框框
#include <bits/stdc++.h>
using namespace std;int main()
{int n, x;cin >> n >> x;vector<int> a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];int left = -1, right = -1, sum = 0, len = INT_MAX;for (int l = 1, r = 1; r <= n; r++){ sum += a[r]; // 1.进窗口while (sum >= x) // 2.判断{if (r - l + 1 < len){// 3.更新结果left = l, right = r;len = right - left + 1;}sum -= a[l++]; // 4.出窗口}}cout << left << " " << right << endl;return 0;
}
2、递归与回溯
3、排序算法
4、查找算法
本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~
