0%

快速排序

方法思想:分治法

将Array[l—r]分为Array[l-x]和Arrar[x-r](l和r为左右边界)

  • 左边的数组全部小于等于x
  • 右边的数组全部大于等于x
  • x只是一个参考值,随意

步骤:

  1. 确定分界点:q[l],q[(l+r)/2],q[r] (随便选一个作为分界点)
  2. ⭐调整区间

20220108113406

使左边的区间全部小于等于x,右边的区间全部大于等于x

只需要保证区间≤x 或者 ≥x 就行,区间内部的顺序不需要管

  1. 递归处理左右两段区间

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int q[], int l, int r)
{
//递归的终止情况
if(l >= r) return;
//第一步:分成子问题
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
//第二步:递归处理子问题
quick_sort(q, l, j), quick_sort(q, j + 1, r);
//l---j -x- i---r
//第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤
}


题目

最小K个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quick_sorr(arr,0,arr.size()-1);
vector<int> temp;
temp.assign(arr.begin(),arr.begin()+k);
return temp;
}
private:
void quick_sorr(vector<int>& arr,int l,int r){
if(l>=r) return;
int i=l-1,j=r+1,x=arr[(l + r) >> 1];
while(i<j){
do i++;while(arr[i]<x);
do j--;while(x<arr[j]);
if(i<j) swap(arr[i],arr[j]);
}
quick_sorr(arr,l,j),quick_sorr(arr,j+1,r);
}
};

最接近原点的K个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
quick_sorr(points,0,points.size()-1);

return {points.begin(),points.begin()+k};
}

private:
void quick_sorr(vector<vector<int>>& a, int l,int r){
if(l >= r) return ;

int i = l - 1,j = r + 1;
int sum = a[(l + r) >> 1][0]*a[(l + r) >> 1][0]+a[(l + r) >> 1][1]*a[(l + r) >> 1][1];
while(i < j){
do i++; while(a[i][0] * a[i][0] + a[i][1] * a[i][1] < sum);
do j--; while(a[j][0] * a[j][0] + a[j][1] * a[j][1] > sum);
if(i < j) swap(a[i],a[j]);
}

quick_sorr(a,l,j);
quick_sorr(a,j+1,r);
}
};

整数二分

20220108144457
20220108144656

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质,例如:arr[mid]>=x
else l = mid + 1;
}
return l;

//返回的l,是数组下标,对应结果的下标
//仅通过下标,无法判断找的对不对
//还需要进一步判断
int ans=bsearch_1(0,n-1);
if(arr[ans]==x) prinf("%d ",ans+1);//如果输出下标直接返回,如果是第几个位置还要下标+1
else printf("-1 ");
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}


P2249查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

const int N=1e6+10;

int arr[N];
int n,m;
int target;
int search(int l,int r)
{

while(l<r)
{
int mid=l+r>>1;
if(arr[mid]>=target) r=mid;
else l=mid+1;
}

return l;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
while(m--)
{
scanf("%d",&target);
int ans=search(0,n-1);
if(arr[ans]==target)
printf("%d ",ans+1);
else printf("-1 ");
}

return 0;
}


小数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}

优先队列(堆)

优先队列也就是堆

什么是堆呢?

堆是一颗完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。

priority_queue<int , vector<int>,greater<int>> heap;//创建小根堆
1
2
3
4
5
6
7
8
9
10
11

引用头文件 #include<queue>
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容


1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;

//自定义比较类型
//左大于右就会建立小顶堆,反而建立大顶堆

// 小顶堆--pair类型的比较
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};

练习题目

Leetcode-前K个高频元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
// 小顶堆
class mycmp{
public:
bool operator() (const pair<int,int> &l,const pair<int,int> &r)
{
return l.second>r.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> heap;
for(int i=0;i<nums.size();++i)
{
++map[nums[i]];
}
for(auto i : map){
heap.push(i);
if(heap.size()>k)
{
heap.pop();
}
}
vector<int> ans;

while(!heap.empty())
{
ans.push_back(heap.top().first);
heap.pop();
}
return ans;
}
};

单调栈

单调栈实际上就是,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内的元素都保持有序(单调递增或单调递减)。

单调栈用途不太广泛,只处理一种典型的问题,叫做 Next Greater Element。本文用讲解单调队列的算法模版解决这类问题,并且探讨处理「循环数组」的策略。

首先,讲解 Next Greater Number 的原始问题:给你一个数组,返回一个等长的数组,对应索引存储下一个更大元素,如果没有更大的元素,就存 -1。不好用语言解释清楚,直接上一个例子:

给你一个数组 [2,1,2,4,3],你返回数组 [4,2,4,-1,-1]

解释:第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2;第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数,填 -1;3 后面没有比 3 大的数,填 -1。

这道题的暴力解法很好想到,就是对每个元素后面都进行扫描,找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O($n^2$)

这个问题可以这样抽象思考:把数组的元素想象成并列站立的人,元素大小想象成人的身高。这些人面对你站成一列,如何求元素「2」的 Next Greater Number 呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的 Next Greater Number,因为比「2」小的元素身高不够,都被「2」挡住了,第一个露出来的就是答案。

20210811102755

这个情景很好理解吧?带着这个抽象的情景,先来看下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> ans(nums.size()); // 存放答案的数组
stack<int> s;
for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮

s.pop(); // 矮个起开,反正也被挡着了。。。
}

ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个

s.push(nums[i]); // 进队,接受之后的身高判定吧!
}
return ans;
}

这就是单调队列解决问题的模板。for 循环要从后往前扫描元素,因为我们借助的是栈的结构,倒着入栈,其实是正着出栈。while 循环是把两个“高个”元素之间的元素排除,因为他们的存在没有意义,前面挡着个“更高”的元素,所以他们不可能被作为后续进来的元素的 Next Great Number 了。

这个算法的时间复杂度不是那么直观,如果你看到 for 循环嵌套 while 循环,可能认为这个算法的复杂度也是 O(n^2),但是实际上这个算法的复杂度只有 O(n)。

分析它的时间复杂度,要从整体来看:总共有 n 个元素,每个元素都被 push 入栈了一次,而最多会被 pop 一次,没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的,也就是 O(n) 的复杂度。

现在,你已经掌握了单调栈的使用技巧,来一个简单的变形来加深一下理解。

给你一个数组 T = [73, 74, 75, 71, 69, 72, 76, 73],这个数组存放的是近几天的天气气温(这气温是铁板烧?不是的,这里用的华氏度)。你返回一个数组,计算:对于每一天,你还要至少等多少天才能等到一个更暖和的气温;如果等不到那一天,填 0 。

举例:给你 T = [73, 74, 75, 71, 69, 72, 76, 73],你返回 [1, 1, 4, 2, 1, 1, 0, 0]。

解释:第一天 73 华氏度,第二天 74 华氏度,比 73 大,所以对于第一天,只要等一天就能等到一个更暖和的气温。后面的同理。

你已经对 Next Greater Number 类型问题有些敏感了,这个问题本质上也是找 Next Greater Number,只不过现在不是问你 Next Greater Number 是多少,而是问你当前距离 Next Greater Number 的距离而已。

相同类型的问题,相同的思路,直接调用单调栈的算法模板,稍作改动就可以啦,直接上代码把。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> dailyTemperatures(vector<int>& T) {
vector<int> ans(T.size());
stack<int> s; // 这里放元素索引,而不是元素
for (int i = T.size() - 1; i >= 0; i--) {
while (!s.empty() && T[s.top()] <= T[i]) {
s.pop();
}
ans[i] = s.empty() ? 0 : (s.top() - i); // 得到索引间距
s.push(i); // 加入索引,而不是元素
}
return ans;
}

单调栈讲解完毕。下面开始另一个重点:如何处理「循环数组」

同样是 Next Greater Number,现在假设给你的数组是个环形的,如何处理?

给你一个数组 [2,1,2,4,3],你返回数组 [4,2,4,-1,4]。拥有了环形属性,最后一个元素 3 绕了一圈后找到了比自己大的元素 4 。

20210811105745

首先,计算机的内存都是线性的,没有真正意义上的环形数组,但是我们可以模拟出环形数组的效果,一般是通过 % 运算符求模(余数),获得环形特效:

1
2
3
4
5
6
7
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
print(arr[index % n]);
index++;
}

回到 Next Greater Number 的问题,增加了环形属性后,问题的难点在于:这个 Next 的意义不仅仅是当前元素的右边了,有可能出现在当前元素的左边(如上例)。

明确问题,问题就已经解决了一半了。我们可以考虑这样的思路:将原始数组“翻倍”,就是在后面再接一个原始数组,这样的话,按照之前“比身高”的流程,每个元素不仅可以比较自己右边的元素,而且也可以和左边的元素比较了。

20210811110157

怎么实现呢?你当然可以把这个双倍长度的数组构造出来,然后套用算法模板。但是,我们可以不用构造新数组,而是利用循环数组的技巧来模拟。直接看代码吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n); // 存放结果
stack<int> s;
// 假装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= nums[i % n])
s.pop();
res[i % n] = s.empty() ? -1 : s.top();
s.push(nums[i % n]);
}
return res;
}

单调队列

也许这种数据结构的名字你没听过,其实没啥难的,就是一个「队列」,只是使用了一点巧妙的方法,使得队列中的元素单调递增(或递减)。这个数据结构有什么用?可以解决滑动窗口的一系列问题。

单调队列是一种主要用于解决滑动窗口类问题的数据结构,即,在长度为 n 的序列中,求每个长度为 n 的区间的区间最值

题目

理解

在一堆数字中,已知最值,如果给这堆数添加一个数,那么比较一下就可以很快算出最值;但如果减少一个数,就不一定能很快得到最值了,而要遍历所有数重新找最值。

回到这道题的场景,每个窗口前进的时候,要添加一个数同时减少一个数,所以想在 O(1) 的时间得出新的最值,就需要「单调队列」这种特殊的数据结构来辅助了。

一个普通的队列

1
2
3
4
5
6
7
8
class Queue
{
void push(int n);
// 或 enqueue,在队尾加入元素 n

void pop();
// 或 dequeue,删除队头元素
}

单调队列操作

1
2
3
4
5
6
7
8
9
10
11
class MonotonicQueue
{
// 在队尾添加元素 n
void push(int n);

// 返回当前队列中的最大值
int max();

// 队头元素如果是 n,删除它
void pop(int n);
}

当然,这几个 API 的实现方法肯定跟一般的 Queue 不一样,不过我们暂且不管,而且认为这几个操作的时间复杂度都是 O(1),先把这道「滑动窗口」问题的解答框架搭出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> maxSlidingWindow(vector<int>& nums,int k)
{
MonotonicQueue window;
vector<int> res;
for(int i =0; i < nums.size(); i++)
{
if(i < k -1)
{//先把窗口的前 k - 1 填满
window.push(nums[i]);
}
else
{// 窗口开始向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k +1]);
// nums[i - k + 1] 就是窗口最后的元素
}
}
return res;
}

20210809212742

实现单调队列

首先我们要认识另一种数据结构:deque,即双端队列。很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class deque {
// 在队头插入元素 n
void push_front(int n);
// 在队尾插入元素 n
void push_back(int n);
// 在队头删除元素
void pop_front();
// 在队尾删除元素
void pop_back();
// 返回队头元素
int front();
// 返回队尾元素
int back();
}

而且,这些操作的复杂度都是 O(1)。这其实不是啥稀奇的数据结构,用链表作为底层结构的话,很容易实现这些功能。

「单调队列」的核心思路和「单调栈」类似。单调队列的 push 方法依然在队尾添加元素,但是要把前面比新元素小的元素都删掉:

1
2
3
4
5
6
7
8
9
10
11
class MonotonicQueue{
private:
deque<int> data;
public:
void push(int n){
while(!data.empty()&& data.back()< n)
data.pop_back();
data.push_back(n);
}
};

你可以想象,加入数字的大小代表人的体重,把前面体重不足的都压扁了,直到遇到更大的量级才停住

20210809212959

如果每个元素被加入时都这样操作,最终单调队列中的元素大小就会保持一个单调递减的顺序,因此我们的 max() API 可以可以这样写:

1
2
3
int max(){
return data.front();
}

pop() API 在队头删除元素 n,也很好写:

1
2
3
4
void pop(int n){
if(!data.empty()&& data.front()== n)
data.pop_front();
}

之所以要判断 data.front() == n,是因为我们想删除的队头元素 n 可能已经被「压扁」了,这时候就不用删除了:
20210809213911

至此,单调队列设计完毕,看下完整的解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
classMonotonicQueue{
private:
deque<int> data;
public:
void push(int n){
while(!data.empty()&& data.back()< n)
data.pop_back();
data.push_back(n);
}
int max(){return data.front();}
void pop(int n){
if(!data.empty()&& data.front()== n)
data.pop_front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums,int k){
MonotonicQueue window;
vector<int> res;
for(int i =0; i < nums.size(); i++){
if(i < k -1){//先填满窗口的前 k - 1
window.push(nums[i]);
}else{// 窗口向前滑动
window.push(nums[i]);
res.push_back(window.max());
window.pop(nums[i - k +1]);
}
}
return res;
}

总结

单调队列在添加元素的时候靠删除元素保持队列的单调性

时间复杂度

读者可能疑惑,push 操作中含有 while 循环,时间复杂度不是 O(1) 呀,那么本算法的时间复杂度应该不是线性时间吧?

单独看 push 操作的复杂度确实不是 O(1),但是算法整体的复杂度依然是 O(N) 线性时间。要这样想,nums 中的每个元素最多被 push_back 和 pop_back 一次,没有任何多余操作,所以整体的复杂度还是 O(N)。

空间复杂度就很简单了,就是窗口的大小 O(k)。

题目

LeetCode-滑动窗口的最大值

模板

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
int q[nums.size()], hh=0, tt=-1;
memset(q, 0, sizeof q);
for(int i=0; i<nums.size(); i++){
if(hh<=tt && q[hh]<=i-k) hh ++;
while(hh<=tt && nums[q[tt]] <= nums[i]) tt--;
q[++ tt] = i;
if(i>=k-1) res.push_back(nums[q[hh]]);
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++ i)
{
scanf("%d", &a[i]);
if (i - k + 1 > q[hh]) ++ hh; // 若队首出窗口,hh加1
while (hh <= tt && a[i] <= a[q[tt]]) -- tt; // 若队尾不单调,tt减1
q[++ tt] = i; // 下标加到队尾
if (i + 1 >= k) printf("%d ", a[q[hh]]); // 输出结果
}
cout << endl;
hh = 0; tt = -1; // 重置!
for (int i = 0; i < n; ++ i)
{
if (i - k + 1 > q[hh]) ++ hh;
while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
q[++ tt] = i;
if (i + 1 >= k) printf("%d ", a[q[hh]]);
}
return 0;
}
//----

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k, q[N], a[N];//q[N]存的是数组下标
int main()
{
int tt = -1, hh=0;//hh队列头 tt队列尾
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i = 0; i <n; i ++) cin>>a[i];
for(int i = 0; i < n; i ++)
{
//维持滑动窗口的大小
//当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
//滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
if(hh <= tt && k < i - q[hh] + 1) hh ++;
//构造单调递增队列
//当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
//就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k) printf("%d ", a[q[hh]]);
}
puts("");
hh = 0,tt = -1;
for(int i = 0; i < n; i ++)
{
if(hh <= tt && k < i - q[hh] + 1) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if(i + 1 >= k ) printf("%d ", a[q[hh]]);
}
return 0;
}



VIP_Canceler V1.4.1

1. 更新日志:

  • 更新Fake Location[1.3.0.2]

1.3之前的版本将不在适配

  • 减小了内存占用

2. 支持软件:

阅读全文 »

1. 下载PicGo插件

20210722205519

先在扩展商店中下载PicGo插件(别告诉我你连VS code都没有)

2. 选择搭建图床的网站

目前picgo只支持weibo, qiniu, tcyun, upyun, github, aliyun, imgur 和 smms这几种,不支持gitee

这里我选择用GitHub做演示

如果你用其他的网站,方法也都是差不多的

阅读全文 »