基础语法

语法基础课

1.变量、输入输出、表达式和顺序语句

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
/*
字节：
bool 1byte
char 1byte
int 4byte 
float 4byte
double 8byte
int类型的商不为整数的话下去整，直接抹去小数点后面的数字
比较浮点值的时候会加上精准度误差如
if(fabs(x-y)<=eps) 相等
else if (a<b-eps) a小于b
else a大于b
const double eps = 1e-6
位数：Nlog(10)2   log(10)2≈3. 
double有效位数16位，小数点后15位
int有效数在正负20亿左右
const类型为只读变量，不能修改
1KB=1024byte
1MB=1024KB
1GB=1024MB
B=byte b=bit
1Mb 1s的下载速度是1Mb=1/8MB=128KB

输入输出:
#include <cstdio>
scanf("%x",&a);
int: %d;
float: %f;
double: %lf;
char: %c;
字符串： %s;
printf("%x",a);
1、读入的个数未知时，可以用while(cin >> x)或while(scanf("%d", &x) != -1)或while(~scanf("%d", &x))来输入。
2、如果输入的最后一个为0且该0不处理，输入语句可以用while(cin >> x && x)或while(cin >> x, x)，从左到右执行，返回值是最后一个
3、while(true)
cin >> x;
4、while(n--)cin>>n;
%%百分号转译
scanf在读入字符时不会自动过滤空格、回车和tab（制表符）
输入小于10万次，可以用cin cout
C++1s可以进行10亿次操作

最小数字宽度:
a. %8.3f, 表示这个浮点数的最小宽度为8，保留3位小数，当宽度不足时在前面补空格。
b. %-8.3f，表示最小宽度为8，保留3位小数，当宽度不足时在后面补上空格。
c. %08.3f, 表示最小宽度为8，保留3位小数，当宽度不足时在前面补上0。


*/

2.判断语句

1
2
3
/*
if语句下如果判断非零，则!=可以省略；
*/

3.循环语句

1
2
3
4
5
6
7
8
9
/*
while的条件判断可以用逗号隔开
break是直接退出循环，continue是跳过本次循环后面的进入下一次循环
循环嵌套，先行后列
循环n次：
1.for(int i =1;i<=n;i++)
2.for(int i =0;i<n;i++)
3.for(int i = n-1;i>=0;i--)
*/

4.数组

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
/*
int a[10000]={0}; 将数组全部初始化成0
定义数组没有给出的值默认是0
函数内定义的数组是随机值，函数外的数组一定都是0（int main（）函数），即局部变量随机，全局变量都是0（原因是内存上面是栈存放指令，下面是堆负责存放数据，堆是虚拟的，用一块开一块内存，最开始标记为全部指向零，但栈是开多少就是多少，里面的值不会清空
C++默认的栈空间是一M，不够大定义很大会报错，函数外面的变量会放在堆空间里面，没有长度限制只有内存限制
定义完一定要用一下

数组下标一定从0开始

位数多的时候用数组来表示整数，数组里的每一位是数字里的每一位
加减乘逆序存入数组，除法顺序存入数组
高精度算法
lgx 下取整为x的位数

二维数组
a[x][y]：a[0][0],a[0][1].....a[0][y];
二维数组初始化样例：
a[3][4]={{1,2,3,4},{2,3,4,2},{2,3,3,1}}
初始化不连续的数组只能用循环
二维数组的输入
for(int i =0;i<n;i++)
    for(int j = 0;j<m;j++)
        cin >>a;
二维数组的输出
for(int i = 0;i<n;i++){
    for(int j = 0;j<n;j++) cout<<a[i][j]<<' ';
cout<<endl;
}

清空数组
#include <cstring>
memset(数组名字，初始化的值，初始化的长度)
中间数不是把数组赋值，而是赋值byte，即8bit，如赋值2，一个字节就是0000 0010，常见赋值0(00000000)和-1，（11111111）
所有单位都是字节byte 1byte=8bit，因此初始化全部的长度=数组内变量数量*类型字节数
例：int a[10] memset(a,0,40)
注：是每个字节变成0,
memset(a,1,)
一个byte有8个bit，每个int类型有4个byte，每个int有32bit，即8组XXXX，从0开始将40个byte全部变成1，相当于每个byte都为0000 0001。
即0000 0001 0000 0001 0000 0001 0000 0001，所以10个变量，每个变量都是0001 0000 0001 0000 0001 0000 0001

数组长度
sizeof为运算符，相当于！而非函数，不需要括号，可以求某一个数组占用的字节数量

数组复制
memcopy(复制的目标数组，原数组，复制的长度（sizeof))
同样是字节数量；





*/

5.字符串

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
/*
ASCII
10 回车
32 空格
48 0
65 A
97 a

字符串是字符数组加上结束符\0
\0的ACSII码表NUL
可以用字符串来初始化字符数组，此时每个字符串结尾会暗含一个\0，因此字符数组长度至少比字符串长度多1
例：
char a1[] = {'c','+','+'};
char a2[] = {'c','+','+','\0'};
char a3[] = "C++";

字符串输出
cout<<a2;从头开始输出
cout<<a2+1;从第二个数开始输出
puts();
字符串输入
char s[100]
cin >> s;数组下标从0开始
scanf("%s",s);
cin >>s+1;数组下标从1开始
数组名字=首元素地址
读入字符串遇到空格 回车 结束才会停止

读一整行包括空格
fgets(字符串名字，最多读入数量，读入文件（一般为stdin）)还会读入回车
string s;
cin.getline(cin,s);
getline(cin,s);

输入量大字符串
输入量小string

字符串函数
#include <cstring>
strlen(s) string的长度，只计算字符串的元素，\0不计入其中
strcmp(a,b) 比较两个字符串的大小，a<b，返回-1，a==b返回0，a>b返回1，这里的比较方式是字典序
注：字典序一般和贪心相关，一旦确定哪个大后面可以不用比较
strcpy(a,b) 将字符串b复制给从a开始的字符数组

遍历输出字符数组中的字符
for(int i =0;i<strlen(s);i++) cout<<s[i]<<endl;   双重循环，效率低
for(int i =0,len =strlen(s);i<len;i++)
cout<<s[i]<<endl;
for(int i = 0;str[i];i++)
cout<<str[i]<<endl;
*/
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
#include <string>
(可以动态地把两个字符串拼在一块，字符数组不可以)
string的初始化：
string s1; 默认的空字符串
string s2 =s1; s2是s1的副本
string s3 = "hiya"; s3是该字符串字面值的一个副本
string s4(10,'c') s4的内容是cccccccccc

输入输出一个string：
cin >> s1>>s2;
cout<<s1<<' '<<s2
puts()
不能用scanf读入一个string
但是可以用printf输出string
printf("%s\n",s1.c_str()) .c_str()会返回字符数组的首地址
读入空格
cin.getline(s1,10000)
getline(cin,s1)
getline会读入回车
string类型要写puts(b.c_str());

s1.size() 返回字符串的长度 速度是O(1)

s1.empty() 判断字符串是不是空的

判断大小s1>s2 s1==s2 s1<s2 s1!=s2;

string s3 = s2+s1;支持两个string相加
s3+=s1;string+="abc";支持累加
在string做加法运算的时候，字面值和字符都会被转化成string对象，因此直接相加就是将这些字面值串联起来。
当把string对象和字符字面值及字符串字面值混在一条语句中使用时，必须确保每个加法运算符的两侧的运算对象至少有一个是string，否则会报错，且必须是等号左边，因为运算是从左到右进行的

处理string对象中的字符
遍历string
可以将string对象当成字符数组来处理
例：
#include <iostream>
for(int i =0;i<s.size();i++); cout<<c <<endl;
for(char c : s)cout<< c<<endl;
for(类型 变量 ：字符串名字) cout<<c<<endl；
相当于
for(int i = 0;i<s.size();i++); char c =str[i];
去掉空格
 string res;
        for(auto c : str)
            {
                if(c==' ') res+="%20";
                else res+=c;
            }
            return res;






改变某个值
for(char &c : s)
for(auto &c : s)

back() 返回最后一个字符
pop_back() 删除最后一个字符

#include <sstream>
stringstream ssin(s); // 把他当成cin只不过是从s这个字符串里面获取

substr(i, len) 截取字符串 起始位置是i，返回从i开始，长度为len的一段，即(i,i+len-1),如果超出，最多到最后一个字符截至
substr(i)从当前位置截取到最后

string str求取长度,len=str.length()
char str[N]求取长度，len =strlen(str)

大小写字符差值为32，字符数字与数字之间差个‘0’即48

substr(string,start,length)
a.substr(start,length)
从string的start位置开始提取字符串，length为待提取的字符串长度，若length不指定，为空，为负值或者大于字符串长度的时候，返回整个字符串的所有字符。

ASCII码最大
int p=0;
for(int i =0;i<a.size();i++)
	if(a[i]>a[p]) p = i;

s.find(string,location)查找指定字符，从某个位置向后开始查找，返回该起始位置，若查找不到，则返回-1
s.rfind(string,location)查找指定字符，从右往左开始找，返回该起始位置，若查找不到，则返回-1；
s.replace(起始位置，后面几个字符，替换)；

遍历字符串输出最开始符合某个条件的位置可以用重复字符串的方式：
例：输出字符串中第一个只出现一次的字符。
for (int i = 0; str[i]; i ++ ) cnt[str[i] - 'a'] ++ ;
    for (int i = 0; str[i]; i ++ )
        if (cnt[str[i] - 'a'] == 1)
        {
            cout << str[i] << endl;
            return 0;
        }

strstr(s1,s2)用来判断字符串s2是否是s1的子串，如果是，则返回s1从s2第一次出现的位置开始到s1结尾的字符串。

字符串位移
a=a.substr(1)+a[0];//字符串右移一位

第一类双指针算法
for(int i =0;i<s.size();i++);
int j =i;
while(j<s.size()&&s[j]==' ')j++;
i = j-1;
*/
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
/*
#include <sstream>
stringstream ssin(s);
stringstream ss;
ss<<a;
//初始化成字符串流

string str;
while(ssin>>str)
if(str == a) cout<<b<<' '
把字符串流中的每一个字符串读出来
举例：
stringstream ssin(s);
int a,b;
string str;
double c;
ssin >>a >>str >>b >>c;
cout<<a<<endl<<str<<endl<<b<<endl<<c<<endl;
输入
123 yxc 321 1.123
将会输出 
123
yxc
321 
1.123
作用是从字符串中提取出各种需要的信息，读入什么信息就写什么类型

#include <sstream>
stringstream ss;自定义字符串流；
ss<<a;读入字符串；
stringstream ssin(s)将字符串作为字符串流通过空格隔开，
每一个分隔开的字符串作为原字符串的字串
ssin>>和cin>>等价
while(cin>>c)
while(ssin>>c)
ssin不会读入空格
字符数组组成的字符串读出信息：
char s[1000]
fgets(s,1000,stdin);
int a,b;
char str[1000];
double c;
sscanf(s,"%d%s%d%lf",&a,str,&b,&c);
printf("%d\n%s\n%d\n%lf\n",a,str,b,c);
输入
123 yxc 321 1.123
将会输出 
123
yxc
321 
1.123
*/

6.函数

  • 一个典型的函数定义包括：返回类型、函数名字、由0或多个形参组成的列表以及函数体
  • 注：每一个变量都要声明类型

编写函数

1
2
3
4
5
6
int foo(int n){//返回类型 函数名 形参
    int res=1;
    for(int i =1;i<=n;i++)
        	res*=i;//函数体
    return res;//函数返回值
}

函数返回值的类型：

变量类型

void

参数也可以是空参数

函数声明

1
int foo(int n);//定义的时候不需要写函数体

静态变量在函数内只会被创建一次，调用不管多少次用的都是一个变量，只在第一次调用被初始化，相当于在函数内部开了一个仅供函数的全局变量，静态变量不赋值的时候为0，开在堆里面，特别大的数组开在栈里面可能会爆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int output(){
    static int cnt= 0;
    cnt++;
    cout<<"call :"<<cnt<<"times";
}
int main(){
    output();
    output();
    output();
    output();
    output();
        //最后输出call : 5times;
}

函数内部修改不影响函数外部修改

传引用参数

当函数的形参为引用类型时，对形参的修改会影响实参的值。使用引用的作用：避免拷贝、让函数返回额外信息

1
2
3
4
5
6
7
8
9
10
11
12
int max(int &x,int &y ){//引用
    x=10,y=20;
if(x>y )return x;
return y;
}
int main(){
    int a,b;
cin>>a>>b;
cout<<max(a,b)<<endl;
cout<<a<<b;
return 0;
}

二维数组第一维数量可以去掉，第二维不可以去掉

由于数组是传引用函数，函数内形参的修改会影响函数外数组即实参的值

参数可以是默认参数：

1
int foo(int a,int b=10)//如果传值b就是实参的值，如果不传b就是10

默认值必须是后面的参数不能只是第一个参数，但可以都是默认值。

inline

不是调用函数而是相当于直接复制粘贴内部代码到主函数，只适合短小且调用次数不是很多的函数。

没有返回值的函数，return后可以为空。

只有先声明才能用函数

递归

函数自己调用自己

1
2
3
4
int fact(int a){
    if(a==1)return 1;
    return n*fact(n-1)
}

递归一定要有结束条件不然容易死循环

7.类、结构体、指针和引用

类

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 <iostream>
using namespace std;
class person{
  private://只能在类里面调用
  int age,height;
    double money;
    string books[1000];
    
  public://可以在类内外调用
    string name;
    void say(){
        cout<<"I am"<<name <<endl;
        
    }
    int get_age(){
            return age;
        }
    void add_money(double x)
        money +=x;
};//一定要加分号
int main(){
    person c;
    c.name = "kugeln";
    c.add_money(10000); 
}

类里面未定义的变量默认private，结构里面未定义的变量默认public

短简单结构，复杂长类

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
struct person{
 int age,height;
 double money;
    person(){}
 person(int _age,int _height,double  _money)//构造函数，不需要写类型；
 {
   age = _age;
     height = _height;
     money = _money;
 }
    person(int _age,int _height,double _money) : age(_age),height(_height),money(_money){}
};
int main(){
    person p(18,180,100);
    return 0;
}

指针

引用

指针指向存放变量的值的地址

nullptr，是c++中空指针类型的关键字，是在C++11中引入的。用来表示空指针类型。

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;
char a,b;
int main(){
   int a =10;
   int* p =&a;//int类型的指针，p取a的地址，指针名是p，p本身存的值就是a的地址，*p表示取到a的值。
   return 0;
}


数组名是一种特殊的指针。指针可以做运算。数组的地址是开头的地址，连续排布

指针运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

int main()
{
    int a[5] = {1, 2, 3, 4, 5};

    for (int i = 0; i < 5; i ++ )
        cout << *(a + i) << endl;
//不是数值相加，而是跳到另外一个变量
     // 指针加减只能同类型
    int* p = &a;
    int& p = a;//引用、别名
    
    
    
    return 0;
  
}

链表

在链表中，如果头结点可能被删掉，则需要一个虚拟头结点，最后返回虚拟节点->next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

struct Node{
    int val;
    Node* next;//只能定义指针不能定义变量
    Node (int _val) :val(_val),next(NULL){}
}
int main(){
      Node node = Node(1);//定义了一个node类型的变量
      Node* p = new Node(1);//new返回的是地址，不加new返回的是值
    p->next = p;//定义一个指针指向自己
    p.next = p;//指针调用
    p->next = p;//变量调用
    
    
    auto p =new Node(1);
    auto q =new Node(2);
    auto o =new Node(3);
    p->next = q;
    q->next = o;//链表，第一个点即头结点，头结点地址head而非值
}

如何遍历链表

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

struct Node{
    int val;
    Node* next;
    Node (int _val) :val(_val),next(NULL){}
}
int main(){
    auto p =new Node(1);
    auto q =new Node(2);
    auto o =new Node(3);
    p->next = q;
    q->next = o;
    Node* head = p;
     
    for(Node* i = head;i;i = i->next)
        cout<<i->value<<endl;//链表的遍历方式
}

链表操作

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
#include <iostream>
using namespace std;

struct Node{
    int val;
    Node* next;
    Node (int _val) :val(_val),next(NULL){}
}
int main(){
    auto p =new Node(1);
    auto q =new Node(2);
    auto o =new Node(3);
    p->next = q;
    q->next = o;
    Node* head = p;
    
    Node* u = new Node(4);
    u->next = head;
    head = u;//头插法，插入值的下一个指向原头结点，头结点变为插入值
    
    Node* u = new Node(4);
    Node* tail = new Node(-1);//虚拟节点
    tail->next = u;
    tail = tail->next;
    //尾插法
    //链表的删除是指遍历的时候跳过该节点
    head->next=head->next->next;//head指向2，跳过1，相当于删除
    for(Node* i = head;i;i = i->next)
        cout<<i->value<<endl;//链表的遍历方式
}
头插法图示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
struct node{
     int val;
     node* next;
     node (int _val):val(_val),next(NULL){}
}*head;
int main(){
    auto a = new node(1);
    auto b = new node(2);
    head = a;//插入头结点
    for(node* i = head;i;i=i->next)
      cout<<i->val<<' '; //遍历目前链表
    cout<<endl;
    b->next = head;//保存头结点指向的节点，防止节点丢失
    head = b;//将要插入的点变为头节点，即插入节点
    for(node* i = head;i;i=i->next)
      cout<<i->val<<' ';
      system("pause");
    return 0;
}
尾插法图示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
struct node{
     int val;
     node* next;
     node (int _val):val(_val),next(NULL){}
}*head;
int main(){
   auto a = new node(1);
   auto b = new node(2);
   node* tail;
   head = a;//a为链表原始数据，头结点
   tail= a;//链表中只有a，因此既是头结点也是尾结点
   b->next = NULL; //链表最后一个数指向空，为插入做准备
   a->next = b;//a指向b，将b插入a后面
  for(node* i = head;i;i=i->next)
    cout<<i->val<<' ';//遍历输出链表
  system("pause");
return 0;

}

链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* reverseList(ListNode* head) {
       // 记录前驱结点
       ListNode* pre = nullptr;
       auto cur = head;
       while(cur)
       {
           auto next = cur->next;
           cur->next = pre;
           pre = cur;
           cur = next;
       }  
       return pre;
   }

两个链表的第一个公共结点

题解

  1. 用两个指针 p1，p2 分别指向两个链表 headA，headB 的头结点，同时向后遍历。
  2. 当指针到达链表末尾时，重新定位到另一个链表的头结点。
  3. 当它们相遇时，所指向的结点就是第一个公共结点。

解释
设A链表的非公共部分长度为LA，B链表的非公共部分长度为LB，公共部分长度为C。

A链表总长度为LA + C，B链表总长度为LB + C。
当指针按照题解方式走下去，p1第二次走到公共节点的时候，走过的长度为LA + C + LB，p2第二次走到公共节点的时候，走过的长度为LB + C + LA。p1 p2走过的长度相等，p1 p2 相遇。
所以，当p1 p2 相遇（相等）的时候，指向的节点就是公共节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA;
        ListNode *p2 = headB;

        while (p1 != p2) {
            if(p1 != NULL)//p1没有走到结尾
                p1 = p1->next;//p1指向下一个节点
            else//p1走到结尾
                p1 = headB;//p1指向另一个链表头
            if(p2 != NULL)//p2没有走到结尾
                p2 = p2->next;//p2指向下一个节点
            else  //p2走到结尾 
                p2 = headA;//p2指向另一个链表头
        }
        return p1;
    }
};

链表排序合并

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
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), tail = dummy;
        //新建一个链表；
        while (l1 && l2)//判断两个是否为空
            if (l1->val < l2->val)//如果l1指向的值小于l2指向的值
            {
                tail = tail->next = l1;
                //
                l1 = l1->next;
            }
            else
            {
                tail = tail->next = l2;
                l2 = l2->next;
            }

        if (l1) tail->next = l1;
        if (l2) tail->next = l2;

        return dummy->next;
    }
};


8.STL

vector

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> a;
    vector<int> b[123];
    struct Rec
    {
        int x,y;
        
    };
    vector<Rec> c;
}

函数

1
2
3
4
5
6
7
8
9
10
11
12
13
a.size();//输出大小
a.empty();//判断是否为空，返回布尔值
//所有容器都有

a.clear();//删掉容器里的所有元素，时间复杂度O（n），其余大部分是O(1)，队列、优先队列和栈没有
a.begin();//第一个迭代器的地址
*a.begin();//相当于a[0]
a.end();//最后一个位置的下一个位置，即便捷，越界访问,即a[a.size()]
//迭代器左闭右开，包含begin不包含end
a.front();//相当于a[0],*a.begin();
a.back();//相当于a[a.size()-1]
a.push_back(4);//往a的最后面加一个元素
a.pop_back();//删除a的最后一个元素

迭代器

1
2
3
4
5
6
vector<int>::iterator it = a.begin();
it +2;//相当于访问a[2]
it：//相当于访问a[0]
*it //取得迭代器的值


遍历迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//遍历vector

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int<> a({1,2,3});
    cout<<a[0]<<' '<<a*.begin()<<endl;
    for(int i = 0;i<a.size();i++)
        cout<<a[i]<<endl;//第一种方式
    for(vector<int>::iterator i = a.begin();i !=a.end();i++) 
        cout<<*i<<' '; //第二种方式
     for(auto i = a.begin();i !=a.end();i++) 
        cout<<*i<<' ';//第三种方式
    for(int  x : a) cout<<x<<' ';
    //第四种方式
    
}

队列

主要包括循环队列queue和优先队列priority_queue两个容器

队列特性先进先出

优先队列优先弹出所有数的最大值

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
#include <iostream>
#include <queue>
using namespace std;
int main(){
    //队列的声明
   queue<int> q;
   queue<double> a;
   struct Rec{
       int a,x,y;
   };
    queue<Rec> b;
    
    //优先队列的定义
    priority_queue<int>q;//大根堆
  priority_queue<int,vector<int>,greater<int>> b;//小根堆，即优先弹出最小值
    
    struct Rec{
        int a,b;
        bool operator<(const Rec& t) const {
            return a<t.a;
        }
    };
    priority_queue<Rec> d;
    //结构体优先队列的定义,大根堆
     struct Rec{
        int a,b;
        bool operator>(const Rec& t) const {
            return a>t.a;
        }
    };
    priority_queue<Rec,vector<Rec>,greater<Rec>> d;//结构体优先队列的定义，小根堆

  // 循环队列queue
        a.push(1);// 从队尾插入     
        a.pop();// 从队头弹出
        a.front();// 返回队头元素
        a.back();// 返回队尾元素
 //   优先队列priority_queue
    	a.push(1);//把元素插入堆
        a.pop();//删除堆顶元素即最大值
    	a.top();//查询堆顶元素（最大值）*/
    
    //清空队列，即重新初始化
    q = queue<int> ();
}

栈

先进后出

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <stack>
using namespace std;
int main(){
    stack<int> stk;
    stk.push(1);//插入一个元素
    stk.top();//返回栈顶元素
    stk.pop();//弹出栈顶元素
}

双端队列

既可以队头队尾插入也可以队头队尾弹出，在头部增删元素仅需要O(1)的时间，支持向数组一样随机访问

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
#include <iostream>
#include <deque>
using namespace std;
int main(){
   deque<int> a;//定义一个双端队列
   a.begin(),a.end();//返回头尾迭代器
   a.front(),a.back();//返回头尾元素
    a.push_back(1),a.push_front(2);
    //在队尾插入1，在队头插入2
    a[0];//随机访问一个元素
    a.pop_back();//弹出最后一个元素
    a.pop_front();//弹出第一个元素
    a.clear();//清空一个队列
    
    
    
    
    
    
    
    
    
    
    
    
     return 0;
}

set

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
#include <iostream>
#include <map>
using namespace std;
int main(){
  set<int> a;//元素不能重复，重复元素会被忽略
    multiset<int> b;//元素可以重复
    
    set<int>::iterator it = a.begin();
    it ++;it --;
    ++it;--it;
    a.end();//a的最大元素的下一个位置的迭代器，前闭后开
    --a.end();//指向集合中最大元素的迭代器
    a.begin();//a的最小元素的迭代器
    //时间复杂度为O(1)
    
    a.insert(x);//插入一个元素，时间复杂度为O（logn）
    a.find(x);//查找一个元素，返回一个迭代器，如果没找到，返回值相当于a.end()，时间复杂度为O（logn）
    if(a.find()==a.end()) //判断x是否在a里存在
    struct rec{
        int x,y;
        bool operator< (const rec&t)const{
            return x<t.x;
        }
    };
    set<rec> c;//定义结构体set
    a.size();//大小
    a.empty();//是否为空
    a.clear();//清空
    
    a.lower_bound(x);//查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器
        a.upper_bound(x);//查找大于x的元素中最小的一个，并返回指向该元素的迭代器
    //二者的时间复杂度都为O（logn）
    
    a.erase(it);//删除迭代器it指向的元素，时间复杂度O(logn)
    a.erase(x);//删除所有等于x的元素，时间复杂度为O(k+logn),k是被删除的元素个数
    a.erase(pos,n); //删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
    a.erase(position);//删除position处的一个字符(position是个string类型的迭代器)
    a.erase(first,last);//删除从first到last之间的字符（first和last都是迭代器）    

    
    
    
    a.count(x);//a里面x元素的个数
}

map

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。

map<key_type, value_type> name;

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
#include <iostream>
#include <map>
using namespace std;
int main(){
 map<int,int>a;//存的是一个二元组，定义一个map,把第一个元素映射到第二个元素里
    a[1] =2;
    a[10000]=3;
    cout<<a[1]<<endl;
    
    map<string,int> a;
    a["kugeln"]=2;
    cout<<a["kugeln"]<<endl;//把kugeln映射到1
    
    map<string,vector<int>>a;
    a["kugeln"]=vector<int>();
    cout<<a["kugeln"].size()<<endl;
    
     map<string,vector<int>>a;
    a["kugeln"]=vector<int>({1,2,3,4});、
    cout<<a["kugeln"][2]<<endl;
    
    // size/empty/clear/begin/end均与set类似。
   a.insert({"a",{}});//第一个元素对应第一个类型，第二个元素对应第二个类型
    a.find(x);//在a里面查找key为x的迭代器
    
    #include <unordered_set>
    unordered_set<int>a;//哈希表，不能存储重复元素
    #include <unordered_multiset>
    unordered_multiset<int>b;//哈希表，能存储重复元素
    #include <unordered_map>
    unordered_map<int,int>c;
}

bitset

1
2
3
4
5
6
#include <bitset>
bitset<1000>a,b;//初始化全0
a[0]=1;
a.set(3);//把a[3]赋值为1
a.reset(3);//把a[3]赋值为0
//无clear函数

pair

pair 定义在头文件 utility 中，一个pair保存两个数据成员 ， 分别命名为 first 、second ，成对出现的数据，可以利用对组来返回这两个数据。与其他标准库类型不同，pair数据成员是 public 的。

pair的基本操作
标准库定义的pair操作如下：

  • pair<T1, T2> p：创建一个空的pair对象

  • pair<T1, T2> p(v1, v2)：用v1、v2来初始化pair对象

  • pair<T1, T2> p={v1, v2}：用v1、v2来初始化pair对象

  • make_pair(v1, v2)：返回一个由v1、v2初始化pair组，其类型根据v1、v2的值来进行推测

  • p.first：返回p的第一个元素

  • p.second：返回p的第二个元素

  • p1==p2：当两个对象的first和second成员都相等时，两个pair对象才相等。

1
2
3
4
pair<int,string> a;//定义
a={3,"kugeln"};//赋值
cout<<a.first<<' '<<a.second<<endl;
//pair支持比较运算，先比较第一个关键字，再比较第二个关键字

9.位运算

符号 运算
& 与
| 或
~ 非
^ 异或
>> 右移
<< 左移

异或可以看成不进位加法

a>>k 相当于a/2^k

a<<k 相当于a*2^k

1
2
3
4
5
6
7
8
/*常用操作：
求x的第k位数字，从个位数开始看 （二进制表示）
x >> k & 1
lowbit(x) = x & -x，返回x的最后一位1
110110返回10，11000返回1000
-a=~a+1

*/

10.常用库函数

1
2
3
4
5
6
7
8
9
//reverse 翻转:
#include <algorithm>
vector<int> a({1,2,3,4,5});
reverse(a.begin(),a.end());//翻转一个vector
for(int x : a)cout<<x<<' ';
cout<<endl;

int a[]={1,2,3,4,5};
reverse(a,a+5);//左闭右开翻转数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//unique 去重
//返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。 重复的元素会被放到容器末端
#include <algorithm>
int a[]={1,1,2,2,3,3,4};
int m = unique(a,a+7)-a;
cout<<m<<endl;
for(int i = 0;i<m;i++)cout<<a[i]<<' ';

//把一个vector去重：
vector<int> a({1,1,2,2,3,3,4});
int m = unique(a.begin(), a.end()) – a.begin();

//把一个数组去重，元素存放在下标1 ~ n：
int m = unique(a + 1, a + n + 1) – (a + 1);


a.erase(unique(a.begin(),a.end()),a.end());//把数组后面除了不同元素之外的元素都删除
1
2
3
4
5
6
7
8
9
10
11
12
13
//random_shuffle函数
vector<int> a({1,1,2,2,3,3,4});
random_shuffle(a.begin(),a.end());
for(int x :a)cout<<x<<' ';


#include <algorithm>
#include <ctime>
vector<int> a({1,1,2,2,3,3,4});
srand(time(0));
random_shuffle(a.begin(),a.end());
for(int x :a)cout<<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
35
36
37
//sort函数
sort(a.begin(),a.end());//从小到大排序
sort(a.begin(),a.end(),greater<int>());//从大到小排序
//自定义排序：
bool cmp(int a,int b)//a是否应该排在b的前面
{
    return a<b;
}
sort(a.begin(),a.end(),cmp);
//结构体排序
bool cmp(rec a,rec b)//a是否应该排在b的前面
{
    return a.x<b.x;
}
struct rec{
    int x;
    int y;
    
}a[5];
for(int i = 0;i<5;i++){
    a[i].x=-i;
    a[i].y=i;
}
sort (a,a+5,cmp);//从小到大排列
//另一种方法，结构体重载
struct rec{
    int x;
    int y;
    bool operator<(const rec&t)const{
        return x<t.x;
    }a[5];
}a[5];
for(int i = 0;i<5;i++){
    a[i].x=-i;
    a[i].y=i;
}
sort (a,a+5);//从小到大排列
1
2
3
4
5
6
7
8
9
10
11
//lower_bound/upper_bound二分
//lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
//upper_bound的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
lower_bound(a.begin(),a.end(),x);

//在有序int数组（元素存放在下标1 ~ n）中查找大于等于x的最小整数的下标：
int i = lower_bound(a + 1, a + 1 + n, x) - a;
vector<int> a{1,2,3,4,5,6};
int t = upper_bound(a.begin(),a.end(),6)-a.begin();
//在有序vector<int>中查找小于等于x的最大整数（假设一定存在）：
int y = *--upper_bound(a.begin(), a.end(), x);
1
2
3
4
5
6
7
8
9
10
//next_premutation
//每运行一次就可以把数组排成下一个字典排数列；与之对应的是prev_permutation，即排出上一个字典序
#include <algorithm>
next_permutation(起始位置，末尾位置+1);
next_permutation(a，a+n);//n输出数量
next_permutation(a.begin(),a.end());
next_permutation(起始位置，末尾位置，自定义排序)
do{
    
}while(next_permutation(a.begin(),a.end()))

重要的头文件

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
/*
#include <cmath>
sqrt(x),pow(底数,指数),abs(x)（整数绝对值）fabs(x)小数绝对值函数

#include <iostream>
cin,cout函数
swap(a,b)函数
#include <algorithm>
max(a,b)函数  reverse（翻转起始位置，翻转的终止位置的下一个位置）

#include <iomanip>
cout<<fixed<<setprecision(x) cout保留x位小数

#include <cstring>
string类型
memset
memcopy
strlen
strcpy
strcmp

#include <cstdio>
printf，scanf函数
puts函数

#include <cctype>
islower isupper 判断一个字符是否为大写字母或者小写字母，不是返回0；是返回1；
tolower 和toupper用于转换字符的大小写
char a=tolower(a);
char b=toupper(b);

vector函数
判断数据个数
s.size();
判断存储容量
s.capacity();
判断是否为空
s.empty();
尾部删除
s.pop_back();
尾部插入
s.push_back();
开头
s.begin();
结尾
s.end();
*/

重要的数学知识

1
2
3
4
5
6
/*
曼哈顿距离
d(i,j)=|xi-xj|+|yi-yj|
切比雪夫距离
d= max(|x1-x2|,|y1-y2|)
*/
算法
#算法
基础语法
http://example.com/2024/03/11/备战408（1）/
作者
Kugeln
发布于
2024年3月11日
许可协议