Acwing《语法基础课》笔记

文章目录

Acwing《语法基础课》笔记第1讲：变量、输入输出、表达式与顺序语句第2讲 `scanf`/`printf`语法及判断语句第3讲 循环语句第4讲 数组第5讲 字符串第6讲 函数第7讲 结构体、类、指针与引用第8讲 STL容器、位运算与常用库函数数组类容器有序对容器algorithm库难题

---

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

常用头文件：

iostream包括cin、cout、scanf、printfcstdin包括scanf、printfcmath万能头文件bits/stdc++.h

数据类型：

boolint 2Blong 4Blong long 8Bfloat 6~7位小数，4Bdouble 15~16位小数，8Blong double 16B

字符的读入：

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

OJ系统的输出格式问题

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

max数学表达式可以通过几何理解： $$\text{max}=\frac{a+b+|a-b|}{2}$$ 因为 “ 短 + 二者之差 = 长 ”

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

基本模板：

#include <cstdio> using namespace std; int main() { return 0; }

难题：

656. 钞票和硬币

---

第2讲 scanf/printf语法及判断语句

判断浮点数是否为0：

!x

难题：

668. 游戏时间2

---

第3讲 循环语句

用曼哈顿距离解决菱形输出问题：

曼哈顿距离指的是两个点在标准坐标系上的绝对轴距离之和 $$\text{dist}=|x_1-x_2|+|y_1-y_2|$$ 输出$n=5$的菱形矩阵时，可分析$5\times 5$矩阵中的曼哈顿距离，其中指定坐标$(2,2)$为中心，可得如下曼哈顿距离矩阵： $$\left(\begin{array}{ccccc}4& 3& 2& 3& 4\\ 3& 2& 1& 2& 3\\ 2& 1& 0& 1& 2\\ 3& 2& 1& 2& 3\\ 4& 3& 2& 3& 4\end{array}\right)$$ 若在元素值$\leqslant \lfloor \frac{n}{2} \rfloor $的位置输出‘\ast ‘，$\gt \lfloor \frac{n}{2} \rfloor $的位置输出空格，即可得到菱形，用公式描述即： $$|x-x_{center}|+|y-y_{center}|⩽\lfloor \frac{n}{2}\rfloor$$ 在输出菱形时，$x_{center}=\lfloor \frac{n}{2}\rfloor ,y_{center}=\lfloor \frac{n}{2}\rfloor$

swap函数：

在新c++编译器中，iostream含有swap函数，可交换基础类型，如swap(int x, int y)，而不必swap(int &x, int &y)

旧一点的版本需要导入#include <algorithm>库

#include <algorithm>里有swap(x, y)函数

输入函数返回值的妙用：

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），用于文件读取

逗号运算符：

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

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

等价于

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

节省了2行代码

重复执行n次的简单模板：

while (n--) { ... }

难题：

725. 完全数

---

第4讲 数组

浮点数比较问题：

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

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

计算$2^N$时，可用$lo{g}_{10}{2}^N$估算数组长度

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

数组初始化的坑：

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

难题：

753. 平方矩阵 I

754. 平方矩阵 II

756. 蛇形矩阵

---

第5讲 字符串

读取字符串的方法：

C语言方法

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

C++方法：

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

字符串操作：

C语言方法

#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++方法

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(); // 删除最后一个字符 // 字符串比较">"、"<" // 字符串拼接"+" for (char ch : str) {...} // 遍历（不可修改字符） for (char &ch : str) {...} // 遍历（可修改字符）

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

字符串流：

#include <sstream> string s; stringstream ssin(s); while(ssin >> s) {...} // 按空格拆分s，例如英语句子拆分单词 // 可用如下代码代替 while(cin >> word) { ... }

char数组难点：

char a[] = {'C', '+', '+'}; char b[4] = {'D', '+', '+', '\0'}; char c[5] = {'E', '+', '+', '\0'}; // 最后一个位置会补\0 cout << a << endl; // 输出"C++D++"，因为字符数组a不会自动添加'\0'，cout会读取到b的部分

难题：

763. 循环相克令

772. 只出现一次的字符

770. 单词替换

771. 字符串中最长的连续出现的字符

777. 字符串乘方

779. 最长公共字符串后缀

---

第6讲 函数

函数中的数组参数：

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 }

默认参数值：

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

内联：

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

fgets的坑：

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

难题：

821. 跳台阶

823. 排列

---

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

结构体：

// 定义 struct Node { int val; Node* next; // 构造器 Node(int _val): val(_val), next(NULL) {} // 编译更快 Node(int _val) { vall = _val; } }; // 使用 Node* p = new Node(1);

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

类：

class Node { private: ... public: ... }; // 注意类末尾要加分号！

类与结构体的区别：

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

Leetcode式模板：

class Solution { public: int f() {...} };

难题：

84. 求1+2+…+n

36. 合并两个排序的链表

87. 把字符串转换成整数

29. 删除链表中重复的节点

---

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

数组类容器

vector：

#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的ArrayLista.begin()返回的是vector第1个元素的地址，而a.end()返回的是最后一个元素的下一个位置的地址a.end() - a.begin() == a.size()*a.begin() == a[0]

queue：

#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：

#include <stack> // 定义 stack<int> s; // 操作 s.push(x); // 入栈 s.top(); // 查看栈顶 s.pop(); // 出栈（不放回出栈元素！）

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

deque：

#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：

#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：

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

bitset：

#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

有序对容器

pair

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

map：

#include <map> // 定义 map<string, int> m; // 操作 a["a"] = 4; // 类似数组的操作 m.insert(); m.find();

unordered_map：

哈希映射，效率更高

algorithm库

#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并没有真的删除重复元素，它仅将重复的元素放到非重复元素部分的后边

难题

75. 和为S的两个数字

51. 数字排列

---

P.S. 如果大家有兴趣，可以去Acwing《语法基础课》看看 我在Acwing也分享了一份，欢迎去围观