Cpp

快速排序(quickSort)

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
#include <bits/stdc++.h>
using namespace std;
int a;
void qsort(int array[],int left,int right)
{
    int i=left,j=right,flag=array[(left+right)/2],middle;
    cout<<"pivot:"<<flag<<"   ";
    for(int i=left;i<=right;++i)
    {
        cout<<array[i];
        if(i-right)cout<<' ';
    }
    do
    {
        while(array[i]<flag)i++;
        while(array[j]>flag)j--;
        if(i<=j)
        {
            middle=array[i];
            array[i]=array[j];
            array[j]=middle;
            i++;
            j--;
        }
        cout<<"->";
        for(int i=left;i<=right;++i)
        {
            cout<<array[i];
            if(i-right)cout<<' ';
        }
    }while(i<=j);
    cout<<endl;
    if(i<right)qsort(array,i,right);
    if(j>left)qsort(array,left,j);
}
int main()
{
    a=8;
    int l[8]={1,3,8,6,4,7,2,5};
    qsort(l,0,a-1);
    for(int i=0;i<a;i++)cout<<l[i]<<' ';
    return 0;
}

输出:

1
2
3
4
5
6
7
pivot:6   1 3 8 6 4 7 2 5->1 3 5 6 4 7 2 8->1 3 5 2 4 7 6 8->1 3 5 2 4 7 6 8
pivot:6   7 6 8->6 7 8
pivot:7   7 8->7 8
pivot:5   1 3 5 2 4->1 3 4 2 5->1 3 4 2 5
pivot:3   1 3 4 2->1 2 4 3->1 2 4 3
pivot:4   4 3->3 4
pivot:1   1 2->1 2

关键在于两处:
i<=j为什么有等于:有等于是为了跳出循环,如果在两个while时就array[i]=array[j]=pivot了,永远不会进入i<j(因为等于),但是i还是小于right导致无限递归.
解决方案:把ij的变化扔出if就可以改成小于了.

array[i]为什么不是小于等于: 在等于时,我们不能跳过,因为跳过会导致pivot永远卡在那里,而不是跟着一起换.而且在左右都等于pivot时陷入死循环.而且如果pivot是最大值或者最小值也会陷入死循环.

cmp函数写法

sort()函数的格式为sort(a,a+100,cmp)(对数组a从a[0]到a[99]排序,[start,end))
cmp函数返回类型为bool,大于序

1
2
3
4
5
6
7
8
9
10
11
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int a[5]={1,4,5,6,2};
    sort(a,a+5,cmp);
    for(int i=0;i<=4;++i)cout<<a[i]<<' ';
    return 0;
}

cmp函数不写默认升序.
对struct的cmp函数会稍显复杂,使用const保证对a的引用不被修改提高性能,输出是对p的降序排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct pl
{
    int p,l;
}a[5];
bool cmp(const pl &a,const pl &b)
{
    return a.p>b.p;
}
int main()
{
    int r[10]={1,7,5,6,8,2,9,4,12,11};
    for(int i=0;i<5;++i)
    {
        a[i].p=r[i];
        a[i].l=r[i+5];
    }
    sort(a,a+5,cmp);
    for(int i=0;i<=4;++i)printf("%d %d\n",a[i].p,a[i].l);
    return 0;
}

指针和引用

1
2
3
int* ptr
int a=15;
ptr=&a;

这样我们就定义了一个指针ptr并把其指向了a.

1
*ptr=80;

可修改指针值来修改变量值.

int* 可以看作是一种定义指针的运算符,但是不同的是int* a,b;定义的b是int而不是指针.

数组名字为数组首元素的指针,可以通过指针++来遍历数组.

引用相当于取了个别名,但是必须立即初始化而且无法修改,引用可以修改原值

1
2
3
int a=5;
int ref=&a;
ref=7;//此时a变为7

为了动态分配内存,可以使用new和delete运算符

1
2
3
4
int* ptr= new int;
delete ptr;
int* ptr0=new int[12];
delete[] ptr0;

定义一个结构体指针

1
Person* personPtr = &person;

这样personPtr就是目标person的指针,同样,如果其是数组,personPtr指的是第一个,可以通过++遍历.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct pl
{
    int p,l;
}a[5];
int main()
{
    int r[10]={1,7,5,6,8,2,9,4,12,11};
    for(int i=0;i<5;++i)
    {
        a[i].p=r[i];
        a[i].l=r[i+5];
    }
    pl* personPtr=a;
    for(int i=0;i<5;++i)
    {
        cout<<(*personPtr).l<<' ';//也可以写成personPtr->l
        personPtr++;
    }
    return 0;
}

const关键字

const可以声明常量,修饰变量等,上面的const保证不变降低复杂性.

memset()函数

memset(array,value,size)
memset根据字节来初始化数组,将value二进制化后填入数组.比如value=100时(0110 0100),int的size为4,所以填入0110 0100 0110 0100 0110 0100 0110 0100,转换为10进制后就很大了.

value 0 127 -1 255 128
初始值 0 0x7F7F7F7F -1 -1 0x80808080

INT_MAX是0x7FFFFFFF,INT_MIN为0x80000000

常见的数值类型size(char[]有最后的\0):

如果你想赋值为固定值,比如127,可以用memset(array,127,1); fill函数也能实现这个功能:std::fill(arr, arr + size, value);``

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int a[12]={0,1,2,3,5,6,7,7,7,8,15,16};
int find(int x)
{
    int l=0,r=12;
    while(l<r)
    {
        int mid=l+(r-l)/2;
        if(a[mid]>=x)r=mid;
        else l=mid+1;
    }
    if(a[l]==x)return l;
    else return -1;
}
int main()
{
    cout<<a[0]<<' '<<find(7);
    return 0;
}

查找一个没有重复数字的数列时l=0,r=11,l<=r即可

搜索

深度优先搜索(DFS):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int k)//k means the times of recursion or the which blank to fill in
{
    if(all blanks are completed)
    {
        answer
        return;
    }
    for(enumeration)
    {
        if(legal)
        {
            record
            dfs(k+1);
            delete
        }
    }
}

示例(洛谷P2329)

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
#include <bits/stdc++.h>
using namespace std;
int nowtime=0,maxtime,num[4],a[4][22]={0},all,sum,ans=0;
void dfs(int x,int i,int s)
{
    if(x>=num[i-1])
    {
        maxtime=max(maxtime,nowtime);
        return;
    }
    if(nowtime+a[i-1][x]<=all/2)
    {
        nowtime+=a[i-1][x];
        dfs(x+1,i,s);
        nowtime-=a[i-1][x];
    }
    dfs(x+1,i,s);
}
int main()
{
    //p2329
    cin>>num[0]>>num[1]>>num[2]>>num[3];
    for(int i=1;i<=4;++i)
        for(int j=0;j<num[i-1];++j)cin>>a[i-1][j];
    for(int i=1;i<=4;++i)
    {
        all=0;
        for(int k=0;k<num[i-1];++k)all+=a[i-1][k];
        sum=0;
        maxtime=0;
        nowtime=0;
        dfs(0,i,all);
        ans+=all-maxtime;
    }
    cout<<ans;
    return 0;
}

广度优先搜索(BFS):

深度优先搜索会优先考虑搜索的深度,不断递归找到答案,不找到不会回头,不适合解答树稀疏的情况,所以引入BFS.

1
2
3
4
5
6
7
8
9
Q.push(Initial state);
while(!Q.empty())
{
	State u =Q.front();//取出队首
	Q.pop();//出队
	for(emurate) //找出u的所有可达状态v
		if(legal) 
		Q.push(v); //入队
}

贴两道题用于复习:

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
#include <bits/stdc++.h>
using namespace std;
struct coord{
    int x,y;
};
int walk[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int ans[410][410];
int main()
{
    //p1443
    queue<coord> Q;
    memset(ans,-1,sizeof(ans));
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    coord tmp={a,b};
    ans[a][b]=0;
    Q.push(tmp);
    while(!Q.empty())
    {
	    coord u =Q.front();
        int j=u.x,k=u.y;
	    Q.pop();
	    for(int i=0;i<8;++i)
        {
            int ux=j+walk[i][0],uy=k+walk[i][1];
            int d=ans[j][k];
		    if(ux<1 or ux>n or uy<1 or uy>m or ans[ux][uy]!=-1)continue;
            ans[ux][uy]=d+1;
            tmp={ux,uy};
		    Q.push(tmp);
        }        
    }
    for(int i=1;i<=n;++i,puts(""))for(int j=1;j<=m;++j)printf("%-5d",ans[i][j]);
    return 0;
}
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
#include <bits/stdc++.h>
using namespace std;
struct node{
    int index,floor,time=0;
}p[220];
int main()
{
    //p1135
    queue<node> Q;
    int n,a,b;
    cin>>n>>a>>b;
    a--,b--;
    for(int i=0;i<n;++i)
    {
        cin>>p[i].floor;
        p[i].index=i;
    }
    p[a].time=1;
    Q.push({a,p[a].floor,1});
    node u;
    while(!Q.empty())
    {
	    u=Q.front();
	    Q.pop();
        for(int i=-1;i<=1;i+=2)
        {
            int now=p[u.index].floor*i+u.index;
            if(now>=0 and now<n and p[now].time==0)
            {
                p[now].time=u.time+1;
                Q.push({now,p[now].floor,p[now].time});
            }
        }
	    if(u.index==b)break;      
    }
    if(p[b].time>=1)cout<<p[b].time-1;
    else cout<<-1;
    return 0;
}

比较

搜索策略：

BFS：逐层搜索，从起始节点开始，依次访问每一层的节点，直到找到目标节点或访问完所有节点。BFS 使用队列（FIFO）来记录待访问的节点。
DFS：深入到图的深处，直到无法继续为止，然后回溯并探索其他路径。DFS 使用栈（LIFO）或递归来实现。

适用场景：

BFS：最短路径问题,层次遍历,最小步骤问题
DFS：深度探索问题,连通性检测,组合、排列问题

实现难度：

BFS 通常需要显式维护一个队列，并且由于它的逐层特性，往往需要更多的内存来存储每一层的节点。
DFS 可以通过递归或显式维护一个栈来实现，递归实现时代码相对简洁，但可能会遇到递归深度过大的问题。

STL: vector数组

vector<int> v(N,i)
建立可变长度数组v,元素类型为int(也可以是其他的),可变数组最开始为N个元素,并初始化为0. N,i均可以省略,默认值为0.
v.push_back(a)
就像队列一样插入元素到末尾.
v.size() v.resize(n,m)
前者返回数组长度,后者resize为n的长度,多删少补,补为m,m可省略.
vector<int>::iterator it定义一个迭代器called it,就像指针一样(不能画等号),*it取元素.一般来说,迭代器用得较少,因为数组元素直接用v[i]表示即可.
v.begin() v.end()返回指针,和队列一样,前者首元素,后者末尾元素+1.

需要注意,vector这种STL中的数组不能用printf()这种c语言的函数
vector数组可以建立二维的
vector<vector<int>> v;
洛谷P3613

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
#include <bits/stdc++.h>
using namespace std;
int m,n,tmp,i,j,k;
int main()
{
    //p3613
    cin>>m>>n;
    vector <vector<int>> v(m+1);
    do
    {
        cin>> tmp;
        if(tmp==1)
        {
            cin>>i>>j>>k;
            if(v[i].size()<j+1)v[i].resize(j+1);
            v[i][j]=k;
        }
        else 
        {
            cin>>i>>j;
            cout<<v[i][j]<<endl;
        }
    }while(--n);
    return 0;
}

栈

栈:后进先出
队列:后进后出
不追求速度的情况下,不用自己手写栈,而是用STL提供的stack
stack<int> s;
s.push(a);
s.pop();
s.top()查询s栈顶元素,如果没有报错
s.size()
s.empty()空返回1,否则返回0

栈的应用较为浅显:

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //p1449
    char s;
    int num=0;
    stack<int > v;
    do
    {
        s=getchar();
        if(s>='0' and s<='9')num=num*10+s-'0';
        else if(s=='.')
        {
            v.push(num);
            num=0;
        }
        else if(s!='@')
        {
            int x=v.top();
            v.pop();
            int y=v.top();
            v.pop();
            switch(s)
            {
                case '+':v.push(x+y);break;
                case '-':v.push(y-x);break;
                case '*':v.push(x*y);break;
                case '/':v.push(y/x);break;
            }
        }
    } while (s!='@');
    printf("%d\n",v.top());
    return 0;
}

队列

queue<int> s;
s.push(a);
s.pop();
s.front() s.back()
s.size()
s.empty()空返回1,否则返回0

链表

list<int> a
a.size()
a.begin() a.end()end指针就是末尾,不用+1
a.push_front(x) a.push_back(x)
a.insert(it,x)在迭代器it前插入x
a.erase(it)删除迭代器所在元素
a.pop_front(x) a.pop_back(x)
a.ins_back(x,y);将y插入在x后面
a.ins_front(x,y);前面
a.ask_back(x)查询x后的数
a.ask_front(x)前的数.

集合

并查集

并查集包括查询和合并的基本操作,具体见

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
#include <bits/stdc++.h>
#define max 5010
using namespace std;
int n,m,p,x,y;
int fa[max];
int find(int c)
{
    if(fa[c]==c)return c;
    else fa[c]=find(fa[c]);
    return fa[c];
}
void join(int a,int b)
{
    if(find(a)!=find(b))fa[find(a)]=find(b);
}
int main()
{
    //p1551
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=0;i<m;++i)
    {
        cin>>x>>y;
        join(x,y);
    }
    for(int i=0;i<p;++i)
    {
        cin>>x>>y;
        if(find(x)!=find(y))cout<<"No";
        else cout<<"Yes";
        printf("\n");
    }
    return 0;
}

集合

Notes
Cpp
https://miao62.github.io/2024/07/28/Cpp/
Author
Miao
Posted on
July 28, 2024
Updated on
August 23, 2024
Licensed under