AcWing《语法基础课》笔记

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

常用头文件：

• iostream包括cin、cout、scanf、printf
• cstdin包括scanf、printf
• cmath
• 万能头文件bits/stdc++.h

数据类型：

• bool
• int 2B
• long 4B
• long long 8B
• float 6~7位小数，4B
• double 15~16位小数，8B
• long 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\times5$矩阵中的曼哈顿距离，其中指定坐标$(2, 2)$为中心，可得如下曼哈顿距离矩阵：
$$ \left( \begin{matrix} 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{matrix} \right) $$
若在元素值$\leqslant \lfloor \frac{n}{2} \rfloor $的位置输出*，$\gt \lfloor \frac{n}{2} \rfloor $的位置输出空格，即可得到菱形，用公式描述即：
$$ |x-x_{center}|+|y-y_{center}|\leqslant \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| \leqslant \text{eps}$去判断eps一般取$10^{-6}$

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

计算$2^N$时，可用$log_{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的ArrayList
• a.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. 数字排列