Acwing笔记汇总

一、《语法基础课》

Acwing《语法基础课》笔记

万能头文件： bits/stdc++.h

字符的读入：

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

max数学表达式：max = (a + b + |a − b|) / 2

swap函数：
在新c++编译器中，iostream含有swap函数，可交换基础类型，如swap(int x, int y)，而不必swap(int &x, int &y)
旧一点的版本需要导入#include 库
#include 里有swap(x, y)函数

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

  1. if (表达式1, 表达式2, 表达式3) {...}
  2. 等价于
  4. 表达式1;
  5. 表达式2;
  6. if (表达式3) {...}
  8. if(cin >> x && x > 0) {...}  
  9. if(cin >> x, x > 0) {...}   // "cin >> x"仅做执行，然后抛弃其返回值

浮点数比较问题：C++中，表达式Acwing笔记---《语法基础课》 - 图1并不成立。由于浮点数精度损失，应该用Acwing笔记---《语法基础课》 - 图2去判断，eps一般取10−6。

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，sizeof(src))

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

读取字符串的方法：

  1. char s[N];
  3. scanf("%s", s);          // 不能读取含空格、换行符的字符串
  4. gets(s);                // 能读取含空格的字符串，同时自动去掉换行符\n
  5. fgets(s, N, stdin);      // 能读取含空格的字符串，但不会去掉换行符\n。【注意】
  1. #include <string>
  2. string str;
  4. cin >> str;             // 不能读取含空格、换行符的字符串
  5. getline(cin, str);       // 能读取含空格的字符串，同时自动去掉换行符\n

字符串操作：

  1. #include <cstring>      // 或<string.h>
  3. char a[N], b[N];
  4. strlen(a);              // O(N)复杂度，使用前最好用变量保存字符串长度。统计的长度不包括`\0`
  5. strcat(a, b);           // 把字符串b拼接到a之后，拼接后的字符串保存在a中
  6. strcmp(a, b);           // 根据字典排序比较字符串
  7. strcpy(b, a);           // 把字符串a的内容拷贝到字符串b
  9. for (int i = 0; str[i]; i++) {...}      // 遍历字符串
  1. string str;
  3. string s(5, 'a');           // 构造重复字符的字符串
  4. str.empty();                // 判空
  5. str.size();                 // 长度，与stelen()不同的是，这个复杂度是O(1)，不用额外的变量保存
  6. str.c_str();                // 转成char数组，此时才可用printf输出
  7. str.substr(begin, length);   // 子串
  8. str.pop_back();             // 删除最后一个字符
  9. // 字符串比较">"、"<"
  10. // 字符串拼接"+"
  11. //注意：使用+对字符串拼接时，要求左右两边至少有一个string对象，即str = "a" + "b";会报错。
  13. for (char ch : str) {...}   // 遍历（不可修改字符）
  14. for (char &ch : str) {...}  // 遍历（可修改字符）

字符串流：

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

char数组难点：

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

函数中的数组参数：

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

默认参数值：

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

内联：

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

fgets的坑：

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

结构体：

  1. // 定义
  2. struct Node {
  3.     int val;
  4.     Node* next;
  6.     // 构造器
  7.     Node(int _val): val(_val), next(NULL) {}        // 编译更快
  8.     Node(int _val) {
  9.         val = _val;
  10.     }
  11. };
  13. // 使用
  14. Node* p = new Node(1);
  15. //注意：链表中的头结点指的是链表第一个结点的地址，而不是结点本身。

类：

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

类与结构体的区别：结构体默认是public，类默认是private。

数组类容器：

  1. #include <vector>
  3. // 定义
  4. vector<int> a;      // 一维数组
  5. vector<int> b[N];   // 二维数组
  7. // 初始化
  8. vector<int> a({1, 2, 3});
  10. // 操作
  11. a[k];           // 取值
  12. a.size();       // 长度
  13. a.empty();      // 判空
  14. a.clear();      // 清空
  16. a.front();              // 读取第1个元素
  17. a.back();               // 读取最后1个元素
  18. a.push_back(x);          // 在末尾插入元素
  19. int x = a.pop_back();    // 删除末尾元素并返回
  21. int* p = lower_bound(a, a + a.size(), x);   
  22. // 查找数组在指定范围内大于等于x的元素地址（要求数组有序）
  23. int* p = upper_bound(a, a + a.size(), x);   
  24. // 查找数组在指定范围内大于x的元素地址（要求数组有序）
  26. int index = lower_bound(a, a + a.size(), x); - a;   
  27. // 查找数组在指定范围内大于等于x的元素下标（要求数组有序）
  28. int index = upper_bound(a, a + a.size(), x); - a;   
  29. // 查找数组在指定范围内大于x的元素下标（要求数组有序）
  31. // 遍历
  32. for (int i = 0; i < a.size(); i++) {...}                            
  33. // 方式1，通过a[i]读取元素值
  34. for (vector<int>::iterator i = a.begin(); i < a.end(); i++) {...}     
  35. // 方式2（迭代器），通过*i读取元素值
  36. for (auto i = a.begin(); i < a.end(); i++) {...}                     
  37. // 方式3（迭代器简化版）
  38. for (int x : a) {...}                                             
  39. // 方式4，通过x读取元素值
  41. 说明：
  42. vector是变长数组，类似java的ArrayList
  43. a.begin()返回的是vector第1个元素的地址，而a.end()返回的是最后一个元素的下一个位置的地址
  44. a.end() - a.begin() == a.size()
  45. *a.begin() == a[0]
  1. #include <queue>
  3. /**************************************************
  4. ** 普通队列queue
  5. ***************************************************/
  6. // 定义
  7. queue<int> q;
  9. // 操作
  10. q.push(x);              // 入队（末尾插入元素）
  11. int x = q.pop();         // 出队（删除第1个元素）
  12. a.front();              // 查看队头元素
  13. a.back();               // 查看队尾元素
  14. // a.clear()
  16. /**************************************************
  17. ** 优先队列（堆）
  18. ***************************************************/
  19. // 元素为基本类型
  20. priority_queue<int> a;                                  // 大根堆
  21. priority_queue<int, vector<int>, less<int>> a;          // 大根堆
  22. priority_queue<int, vector<int>, greater<int>> b;          // 小根堆
  25. // 元素为自定义类型
  26. struct Rec {
  27.     int a, b;
  29.     // 大根堆需要自定义类重载<号
  30.     bool operator< (const Rec& t) const {
  31.         return a < t.a;
  32.     }
  34.     // 小根堆需要自定义类重载>号
  35.     bool operator> (const Rec& t) const {
  36.         return a > t.a;
  37.     }
  38. }
  40. priority_queue<Rec> a;                                  // 大根堆
  41. priority_queue<Rec, vector<Rec>, less<Rec>> a;          // 大根堆
  42. priority_queue<Rec, vector<Rec>, greater<Rec>> b;       // 小根堆
  44. // 操作
  45. a.push(x);              // 插入元素（位置不确定）
  46. a.top();                // 查看堆顶元素（大根堆是最大值，小根堆是最小值）
  47. a.pop();                // 删除堆顶元素（大根堆是最大值，小根堆是最小值）
  50. 注意：
  51. 队列没有clear()方法
  52. 优先队列插入时无序，输出时有序
  53. 优先队列存储自定义类型时，需要重载运算符
  54. 大根堆重载<
  55. 小根堆重载>
  1. #include <stack>
  3. // 定义
  4. stack<int> s;
  6. // 操作
  7. s.push(x);          // 入栈
  8. s.top();            // 查看栈顶
  9. s.pop();            // 出栈（不放回出栈元素！）
  10. //注意：stack的pop()方法不像java返回栈顶元素！
  1. #include <deque>
  3. // 定义
  4. deque<int> q;
  6. // 操作
  7. q[i]                // 随机访问
  8. q.begin();          // 队头元素地址，用*q.begin()读取元素
  9. q.end();            // 队尾元素地址，用*q.end()读取元素
  10. q.front();          // 队头元素值
  11. q.back();           // 队尾元素值
  13. push_back();        // 队尾插入元素
  14. push_front();       // 队头插入元素
  15. pop_back();         // 队尾删除元素
  16. pop_front();        // 队头插入元素
  1. #include <set>
  3. // 定义
  4. set<int> s;             // 集合
  5. multiset<int> ms;       // 多重集合（允许元素重复）
  7. // 操作
  8. s.size();
  9. s.empty();
  10. s.claer();
  12. s.begin();
  13. s.end();
  15. s.insert(x);
  16. s.find(x);              // 返回迭代器，可用if(s.find(x) == s.end())判断是否存在元素x
  17. s.lower_bound(x);        // 返回大于等于x的最小元素的迭代器
  18. s.upper_bound(x);        // 返回大于x的最小元素的迭代器
  20. s.erase(x);             // 删除x并返回迭代器
  21. s.count(x);             // 统计x出现的次数（普通集合只会返回0或1，多重集合可能返回大于1的数）
  24. 说明：
  25. 自定义类要求重载<
  26. find()、erase()、lower_bound()和upper_bound()都是O(logn)复杂度
  27. count()是O(k+logn)复杂度
  1. #include <unordered_set>
  3. unordered_set<int> s;           // 哈希表
  4. unordered_multiset<int> s;
  1. #include <bitset>
  3. // 定义二进制串
  4. bitset s;
  6. // 操作
  7. s.count();      // 1的个数
  8. s.set(p);       // 第p位设为1
  9. s.reset(p);     // 第p位设为0
  12. 说明：
  13. bitset元素支持位运算符&、|和~等等
  14. 求x的第k位二进制数：x >> k & 1
  15. 求x从右起的第1个1：lowbit(x) = x & -x，实际上是原码和补码做与操作。
  16.                  例如110110返回10，11000返回1000

有序对容器

  1. pair:
  2. pair<int, int> a = {5, 6};
  3. pair<int, int> b = make_pair(5, 6);
  6. map：
  7. #include <map>
  8. map<string, int> m;   // 定义
  10. // 操作
  11. a["a"] = 4;     // 类似数组的操作
  12. m.insert();
  13. m.find();
  16. unordered_map：
  17. 哈希映射，效率更高

algorithm算法库

  1. #include <algorithm>
  3. vector<int> a;
  5. // 翻转
  6. reverse(a.begin(), a.end());
  7. reverse(a, a + a.size());
  9. // 去重
  10. unique(a, a + a.size());                        // 返回去重后最后一个元素的地址
  11. int m = unique(a, a + a.size()) - a;             // 去重后数组的长度
  12. a.erase(unique(a.begin(), a.end()), a.end());     // 真删除重复元素
  14. // 打乱
  15. random_shuffle(a.begin(), a.end());
  17. // 排序
  18. sort(a.begin(), a.end());                       // 升序
  19. sort(a.begin(), a.end(), greater<int>());         // 降序
  21. bool cmp(int a, int b) {return a - b;}              // 自定义比较方法
  22. sort(a.begin(), a.end(), cmp);                      // 自定义排序
  25. 注意：
  26. random_shuffle()常结合ctime的srand( time(0) )使用
  27. unique并没有真的删除重复元素，它仅将重复的元素放到非重复元素部分的后边