语法基础
馨er BOSS
  2022-01-11 16:47:37 2022-01-11 16:47      3.2k 字  14 分钟

acwing语法基础课笔记，结合柳婼的pdf

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

1.1 常用头文件

  • iostream包括cin、cout、scanf、printf
  • cstdio包括scanf、printf
  • cmath，相当于C语言里面的math.h
  • cctype，相当于C语言里面的ctype.h
  • cstring，相当于C语言里面的string.h
  • 万能头文件bits/stdc++.h

1.2 数据类型

  • bool
  • int 2B
  • long 4B
  • long long 8B
  • float 6~7位小数，4B
  • double 15~16位小数，8B
  • long double 16B

1.3 字符的读入

1
2
scanf("%c%c", &a, &b);      // 会把空格读入
cin >> a >> b;              // 会忽略中间的空格（1个或多个）

1.4 OJ系统的输出格式问题

  • 忽略每一行末尾的空格
  • 忽略输出结果最后的换行符

1.5 max数学表达式的理解

$max=\frac{a+b+\vert a-b\vert}{2}$

因为 “ 短 + 二者之差 = 长 ”

所以有 “ 长 + （ 短 + 二者之差 ）= 长 + 长 = 2 * 长 ”

2 scanf/printf语法及判断语句

1
2
cin.tie(0);//代码优化
ios::sync_with_stdio(false);//代码优化

判断浮点数是否为0：

1
!x

3 循环语句

3.1 输入函数返回值的妙用

1
2
3
4
5
6
7
if(cin >> x && x > 0) {...}         // 写法1
if(cin >> x, x > 0) {...}           // 写法2。与写法1不同的是，这里的if语句不考虑"cin >> x"的返回值。"cin >> x"仅做执行，然后抛弃其返回值，最后对判断x > 0。即等价于"cin >> x; if(x > 0) {...}"，可以节省1行。

if(scanf("%d", &x) && x > 0) {...}  // 写法1
if(scanf("%d", &x), x > 0) {...}    // 写法2

if(~scanf("%d", &x)) {...}          // 判断是否非法输入（EOF），用于文件读取

3.2 逗号运算符

C++的,运算符对逗号前后的表达式进行运算，然后舍弃前一个表达式的返回值，仅仅返回最后一个表达式的返回值，例

1
if (表达式1, 表达式2, 表达式3) {...}

等价于

1
2
3
表达式1;
表达式2;
if (表达式3) {...}

节省了2行代码

4 数组

4.1 浮点数比较问题

C++中，表达式$\sqrt{3}\times \sqrt{3} == 3$并不成立，由于浮点数精读损失，应该用$\vert\sqrt{3}\times\sqrt{3}-3\vert\leq eps$去判断，eps一般取$10^{−6}$

4.2 高精度运算的数组大小问题

计算$2^N$时，可用lg2N估算数组长度

4.3 cstring一些函数用法

memset赋值是按字节赋值，因此只有赋予-1和0时才与预期一致。其最后一个参数的单位是Byte

memset(arr, 0, n * sizeof(int))

memset(arr, -1, n * sizeof(int))

sizeof可不加括号，即可这样使用sizeof a，其返回单位是Byte

memcpy用于拷贝数组，格式为memcpy(dest，src，izeof(src))

4.4 数组初始化的坑

在函数内定义的数组不会自动初始化为0，都是随机数，例如main函数里。而在函数外定义的数组会自动初始化为0。

5 字符串

5.1 读取字符串的方法

C语言方法

1
2
3
4
5
char s[N];

scanf("%s", s);    // 不能读取含空格、换行符的字符串
gets(s);           // 能读取含空格的字符串，同时自动去掉换行符\n
fgets(s, N, stdin);// 能读取含空格的字符串，但不会去掉换行符\n。【注意】

C++方法：

1
2
3
4
5
6
#include <string>

string str;

cin >> str;             // 不能读取含空格、换行符的字符串
getline(cin, str);       // 能读取含空格的字符串，同时自动去掉换行符\n

5.2 字符串操作

C语言方法

1
2
3
4
5
6
7
8
9
#include <cstring>      // 或<string.h>

char a[N], b[N];
strlen(a);              // O(N)复杂度，使用前最好用变量保存字符串长度。统计的长度不包括`\0`
strcat(a, b);           // 把字符串b拼接到a之后，拼接后的字符串保存在a中
strcmp(a, b);           // 根据字典排序比较字符串
strcpy(b, a);           // 把字符串a的内容拷贝到字符串b

for (int i = 0; str[i]; i++) {...}      // 遍历字符串

C++方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string str;

string s(5, 'a');           // 构造重复字符的字符串
str.empty();                // 判空
str.size();                 // 长度，与stelen()不同的是，这个复杂度是O(1)，不用额外的变量保存
str.c_str();                // 转成char数组，此时才可用printf输出
str.substr(begin, length);   // 子串
str.pop_back();             // 删除最后一个字符
str.length();               // 有几个字符就是长度多少，不存在char[]里面的什么末尾的结束符之类的
// 字符串比较">"、"<"
// 字符串拼接"+"

for (char ch : str) {...}   // 遍历（不可修改字符）
for (char &ch : str) {...}  // 遍历（可修改字符）

注意：使用+对字符串拼接时，要求左右两边至少有一个string对象，即str = "a" + "b";会报错。

5.3 字符串流

1
2
3
4
5
6
7
8
9
#include <iostream>
string s;
stringstream ssin(s);
while(ssin >> s) {...}      // 按空格拆分s，例如英语句子拆分单词

// 可用如下代码代替
while(cin >> word) {
    ...
}

5.4 char数组难点

1
2
3
4
5
char a[] = {'C', '+', '+'};
char b[4] = {'D', '+', '+', '\0'};
char c[5] = {'E', '+', '+', '\0'};          // 最后一个位置会补\0

cout << a << endl;          // 输出"C++D++"，因为字符数组a不会自动添加'\0'，cout会读取到b的部分

6 函数

6.1 函数中的数组参数

1
2
3
4
5
6
7
8
9
int size(int a[]) {
    return sizeof a;
}

int main() {
    int a[10];
    cout << sizeof a << endl;           // 4B * 10 = 40B
    cout << size(a) << endl;            // 8B，虽然函数f能修改实参a的内容，但其本质是一个不同的数组指针指向数组的内存空间，故对函数内的数组参数a调用sizeof，返回的是数组指针的长度。在64位系统中，指针的长度等于64b=8B
}

6.2 默认参数值

1
void f(int a, int b = 10) {...}     // 需要默认值的变量只能放在靠后的位置

6.3 内联

1
inline void f() {...}           // 编译时把函数体复制到调用函数的位置，减少函数跳转次数

fgets的坑：

fgets会读入\n，因此遍历字符串时，应当用for (int i = 0; str[i] != '\n'; i++)，而不能用 for (int i = 0; str[i]; i++)

7 结构体、类、指针与引用

7.1 结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义
struct Node {
    int val;
    Node* next;

    // 构造器
    Node(int _val): val(_val), next(NULL) {}        // 编译更快
    Node(int _val) {
        vall = _val;
    }

};

// 使用
Node* p = new Node(1);

注意：链表中的头结点指的是链表第一个结点的地址，而不是结点本身。

7.2 类

1
2
3
4
5
6
class Node {
private:
    ...
public:
    ...
};          // 注意类末尾要加分号！

类与结构体的区别：

  • 结构体默认是public
  • 类默认是private

Leetcode式模板：

1
2
3
4
class Solution {
public:
    int f() {...}
};

8 STL容器、位运算与常用库函数

8.1 数组类容器

vector

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
#include <vector>

// 定义
vector<int> a;      // 一维数组
vector<int> b[N];   // 二维数组

// 初始化
vector<int> a({1, 2, 3});

// 操作
a[k];           // 取值
a.size();       // 长度
a.empty();      // 判空
a.clear();      // 清空

a.front();              // 读取第1个元素
a.back();               // 读取最后1个元素
a.push_back(x);          // 在末尾插入元素
int x = a.pop_back();    // 删除末尾元素并返回

int* p = lower_bound(a, a + a.size(), x);       // 查找数组在指定范围内大于等于x的元素地址（要求数组有序）
int* p = upper_bound(a, a + a.size(), x);       // 查找数组在指定范围内大于x的元素地址（要求数组有序）

int index = lower_bound(a, a + a.size(), x); - a;   // 查找数组在指定范围内大于等于x的元素下标（要求数组有序）
int index = upper_bound(a, a + a.size(), x); - a;   // 查找数组在指定范围内大于x的元素下标（要求数组有序）

// 遍历
for (int i = 0; i < a.size(); i++) {...}                            // 方式1，通过a[i]读取元素值
for (vector<int>::iterator i = a.begin(); i < a.end(); i++) {...}     // 方式2（迭代器），通过*i读取元素值
for (auto i = a.begin(); i < a.end(); i++) {...}                     // 方式3（迭代器简化版）
for (int x : a) {...}                                             // 方式4，通过x读取元素值

说明：

  • vector是变长数组，类似java的ArrayList
  • a.begin()返回的是vector第1个元素的地址，而a.end()返回的是最后一个元素的下一个位置的地址
  • a.end() - a.begin() == a.size()
  • *a.begin() == a[0]

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 <queue>

/**************************************************
** 普通队列queue
***************************************************/
// 定义
queue<int> q;

// 操作
q.push(x);              // 入队（末尾插入元素）
int x = q.pop();         // 出队（删除第1个元素）
a.front();              // 查看队头元素
a.back();               // 查看队尾元素
// a.clear()

/**************************************************
** 优先队列（堆）
***************************************************/
// 元素为基本类型
priority_queue<int> a;                                  // 大根堆
priority_queue<int, vector<int>, greater<int>> b;          // 小根堆

// 元素为自定义类型
struct Rec {
    int a, b;

    // 大根堆需要自定义类重载<号
    bool operator< (const Rec& t) const {
        return a < t.a;
    }
    
    // 小根堆需要自定义类重载>号
    bool operator> (const Rec& t) const {
        return a > t.a;
    }

}

priority_queue<Rec> a;                                  // 大根堆
priority_queue<Rec, vector<Rec>, greater<Rec>> b;          // 小根堆

// 操作
a.push(x);              // 插入元素（位置不确定）
a.top();                // 查看堆顶元素（大根堆是最大值，小根堆是最小值）
a.pop();                // 删除堆顶元素（大根堆是最大值，小根堆是最小值）

注意：

  • 队列没有clear()方法
  • 优先队列插入时无序，输出时有序
  • 优先队列存储自定义类型时，需要重载运算符
    • 大根堆重载<
    • 小根堆重载>

stack

1
2
3
4
5
6
7
8
9
#include <stack>

// 定义
stack<int> s;

// 操作
s.push(x);          // 入栈
s.top();            // 查看栈顶
s.pop();            // 出栈（不放回出栈元素！）

注意：stack的pop()方法不像java返回栈顶元素！

deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <deque>

// 定义
deque<int> q;

// 操作
q[i]                // 随机访问
q.begin();          // 队头元素地址，用*q.begin()读取元素
q.end();            // 队尾元素地址，用*q.end()读取元素
q.front();          // 队头元素值
q.back();           // 队尾元素值

push_back();        // 队尾插入元素
push_front();       // 队头插入元素
pop_back();         // 队尾删除元素
pop_front();        // 队头插入元素

set

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

// 定义
set<int> s;             // 集合
multiset<int> ms;       // 多重集合（允许元素重复）

// 操作
s.size();
s.empty();
s.claer();

s.begin();
s.end();

s.insert(x);
s.find(x);              // 返回迭代器，可用if(s.find(x) == s.end())判断是否存在元素x
s.lower_bound(x);        // 返回大于等于x的最小元素的迭代器
s.upper_bound(x);        // 返回大于x的最小元素的迭代器

s.erase(x);             // 删除x并返回迭代器
s.count(x);             // 统计x出现的次数（普通集合只会返回0或1，多重集合可能返回大于1的数）

说明：

  • 自定义类要求重载<
  • find()、erase()、lower_bound()和upper_bound()都是O(logn)复杂度
  • count()是O(k+logn)复杂度

unordered_set

1
2
3
4
#include <unordered_set>

unordered_set<int> s;           // 哈希表
unordered_multiset<int> s;

bitset

1
2
3
4
5
6
7
8
9
#include <bitset>

// 定义二进制串
bitset s;

// 操作
s.count();      // 1的个数
s.set(p);       // 第p位设为1
s.reset(p);     // 第p位设为0

说明：

  • bitset元素支持位运算符&、|和~等等
  • 求x的第k位二进制数：x >> k & 1
  • 求x从右起的第1个1：lowbit(x) = x & -x;
    • 实际上是原码和补码做与操作
    • 例如110110返回10，11000返回1000

8.2 有序对容器

pair

1
2
pair<int, int> a = {5, 6};
pair<int, int> b = make_pair(5, 6);

map

1
2
3
4
5
6
7
8
9
#include <map>

// 定义
map<string, int> m;

// 操作
a["a"] = 4;     // 类似数组的操作
m.insert();
m.find();

unordered_map

哈希映射，效率更高

8.3 algorithm库

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

vector<int> a;

// 翻转
reverse(a.begin(), a.end());
reverse(a, a + a.size());

// 去重
unique(a, a + a.size());                        // 返回去重后最后一个元素的地址
int m = unique(a, a + a.size()) - a;             // 去重后数组的长度
a.erase(unique(a.begin(), a.end()), a.end());     // 真删除重复元素

// 打乱
random_shuffle(a.begin(), a.end());

// 排序
sort(a.begin(), a.end());                       // 升序
sort(a.begin(), a.end(), greater<int>());         // 降序

bool cmp(int a, int b) {return a - b;}              // 自定义比较方法
sort(a.begin(), a.end(), cmp);                      // 自定义排序

注意：

  • random_shuffle()常结合ctime的srand( time(0) )使用
  • unique并没有真的删除重复元素，它仅将重复的元素放到非重复元素部分的后边

8.4 cctype头文件中的函数

判断元素是否属于某个类型

isalpha 大小写字母

islower 小写字母

isupper 大写字母

isdigit 数字

isalnum 大小写字母，数字

isblank space 和 \t

isspace space 和 \t，\n，\r

tolower 转换为小写字母

toupper 转换为大写字母

  • 本文标题：语法基础
  • 本文作者：馨er
  • 创建时间：2022-01-11 16:47:37
  • 本文链接：https://sjxbbd.vercel.app/2022/01/11/7dfca4941869/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！