2023年8月23日#include
cstdio 有两个函数 printf，scanf 用于输出和输入
int : %dfloat : %fdouble : %lfchar : %clong long : %lldiostream 有 cin 读入，cout 输出
using namespace std;
使用了std命名空间，cin、cout定义在该命名空间中，不引入空间会找不到导致出错
int main()
函数执行入口
基本类型
a+b
⭐所有 cout、cin 都能用 scanf、printf 替换，但反过来，由于cout、cin效率可能较低会导致超时
⭐ printf %c 会读入空格跟回车，需要手动加一个空格跟回车；cin 不会读入空格跟回车
#include using namespace std;int main() { int a, b; // ^ 定义两个变量 cin >> a >> b; // ^ 输入（把cin里的值拿到a里面去、b里面去） cout << a + b << endl; // ^ 输出 return 0;}#include #include using namespace std;int main() { int a, b; scanf("%d%d", &a, &b); printf("%d %d\n", a + b, a * b); return 0;}%
C++ 中取模看前面的数，如果负数则负数；而在Lua中取模的结果不可能为负数
cout << 5 % 2 << endl; // 1 cout << -5 % 2 << endl; // -1类型转换
float , double 转 int 下取整 ；int 转 char 整数取ASCII表；
char类型跟int类型运算，结果是int类型；int类型与float型运算会变成float型
隐性类型转换：把精度低的类型转换成另外一个精度高的类型
604
604. 圆的面积 – AcWing题库
题目要求保留四位小数，考虑到float有效数字位只有6~7位，可能出现精度不准确，故改用 double（未来题目看到浮点数也优先使用double）
#include int main() { double r; scanf("%lf", &r); printf("A=%.4lf", 3.14159 * r * r); return 0;}653
653. 钞票 – AcWing题库
#include int main() { int m; scanf("%d", &m); printf("%d\n", m); printf("%d nota(s) de R$ 100,00\n", m / 100); m %= 100; printf("%d nota(s) de R$ 50,00\n", m / 50); m %= 50; printf("%d nota(s) de R$ 20,00\n", m / 20); m %= 20; printf("%d nota(s) de R$ 10,00\n", m / 10); m %= 10; printf("%d nota(s) de R$ 5,00\n", m / 5); m %= 5; printf("%d nota(s) de R$ 2,00\n", m / 2); m %= 2; printf("%d nota(s) de R$ 1,00\n", m / 1); return 0;}617
617. 距离 – AcWing题库
由于隐性类型转换，结果为double，用%d表示数字不正确，需要用%lf
#include int main() { int a; scanf("%d", &a); printf("%.0lf minutos", a / 30.0 * 60); return 0;}618
618. 燃料消耗 – AcWing题库
看数据范围，最大可以到 10 ^ 14 次方远远大于 2 ^ 31，需要改用 long（8字节）
#include int main() { long a, b; scanf("%ld%ld", &a, &b); printf("%.3lf", a * b / 12.0); return 0;}656
656. 钞票和硬币 – AcWing题库
一开始想用两个整数读整数跟小数（%d.%d），但小数位输入可能是 .1 或 .01，读出来都是1，不能处理，只能按浮点数来读
#include int main() { double n; int m; scanf("%lf", &n); m = (int)(n * 100); printf("NOTAS:\n"); printf("%d nota(s) de R$ 100.00\n", m / 10000); m %= 10000; printf("%d nota(s) de R$ 50.00\n", m / 5000); m %= 5000; printf("%d nota(s) de R$ 20.00\n", m / 2000); m %= 2000; printf("%d nota(s) de R$ 10.00\n", m / 1000); m %= 1000; printf("%d nota(s) de R$ 5.00\n", m / 500); m %= 500; printf("%d nota(s) de R$ 2.00\n", m / 200); m %= 200; printf("MOEDAS:\n"); printf("%d moeda(s) de R$ 1.00\n", m / 100); m %= 100; printf("%d moeda(s) de R$ 0.50\n", m / 50); m %= 50; printf("%d moeda(s) de R$ 0.25\n", m / 25); m %= 25; printf("%d moeda(s) de R$ 0.10\n", m / 10); m %= 10; printf("%d moeda(s) de R$ 0.05\n", m / 5); m %= 5; printf("%d moeda(s) de R$ 0.01\n", m / 1); return 0;}2023年8月24日字符串的输入
#include using namespace std;int main() { string a, b, c; cin >> a >> b >> c;666
666. 三角形类型 – AcWing题库
多注意题目意思，如果…否则…，而不是如果、否则两种情况都输出
#include #include using namespace std;int main() { double a, b, c, tmp; cin >> a >> b >> c; if (b >= a && b >= c) { tmp = a; a = b; b = tmp; } else if (c >= a && c >= b) { tmp = c; c = a; a = tmp; } if (a >= b + c) cout << "NAO FORMA TRIANGULO" << endl; else { if (a * a == b * b + c * c) cout << "TRIANGULO RETANGULO" < b * b + c * c) cout << "TRIANGULO OBTUSANGULO" << endl; if (a * a < b * b + c * c) cout << "TRIANGULO ACUTANGULO" << endl; if (a == b && a == c && b == c) cout << "TRIANGULO EQUILATERO" << endl; if (a == b && c != b || a == c && b != c || b == c && a != b) cout << "TRIANGULO ISOSCELES" << endl; } return 0;}658
658. 一元二次方程公式 – AcWing题库
容易忘记最后 2 * a 的括号，导致先除后乘
#include #include int main() { double a, b, c; scanf("%lf%lf%lf", &a, &b, &c); if (b * b - 4 * a * c < 0 || a == 0) { printf("Impossivel calcular"); } else { printf("R1 = %.5lf\n", (-b + sqrt(b * b - 4 * a * c)) / (2 * a)); printf("R2 = %.5lf", (-b - sqrt(b * b - 4 * a * c)) / (2 * a)); } return 0;}2023年8月25日读入个数未知
读入的个数未知时，可以用while(cin >> x)或while(scanf("%d", &x) != -1)或while(~scanf("%d", &x))来输入。
如果输入的最后一个为0且该0不处理，输入语句可以用while(cin >> x && x)或while(cin >> x, x)，逗号表达式取最后一个值。
714
714. 连续奇数的和 1 – AcWing题库
algorithm 函数库的使用 ， % 相关的概念
#include #include #include using namespace std;int main() { int x, y; cin >> x >> y; if (x > y) { swap(x, y); } int total = 0; for (x++; x < y; x++) { if (abs(x) % 2 == 1) total += x; } cout << total; return 0;}725
725. 完全数 – AcWing题库
设一个公约数 d 那么另一个公约数 x / d ， d <= x/d 得 d <= 根号x；另外还要考虑1的特殊情况。
AcWing 726. 质数 – AcWing 这题同理
#include #include #include using namespace std;int main() { int n, x; cin >> n; while (cin >> x, n--) { int sum = 0; for (int i = 1; i * i <= x; i++) { if (x % i == 0) { if (i < x) sum += i; if (x / i != i && x / i < x) sum += x / i; } } if (sum == x) cout << x << " is perfect" << endl; else cout << x << " is not perfect" << endl; } return 0;}2023年8月26日reverse
在 alogorithm 库中，用于翻转数组。涉及题目（翻转整个，然后两边各自再翻转）
memset
在 cstring 库中，用于数组的初始化，速度比循环初始化要快。参数是数组指针，值（字节），长度（字节）
memset(a,-1,sizeof a)memcpy
在 cstring 库中，用于复制数组。参数是目标数组指针，被复制数组指针，长度（字节）
753
753. 平方矩阵 I – AcWing题库
技巧，需要看各个格子距离上下左右边的最短距离。下面两道也是技巧性题目
#include #include #include using namespace std;int main() { int n; while (cin >> n, n) { for (int i = 1; i <= n; i++) { for (int k = 1; k <= n; k++) { cout << min(min(i, k), min(n + 1 - k, n + 1 - i)) << " "; } cout << endl; } cout << endl; } return 0;}754
754. 平方矩阵 II – AcWing题库
#include #include #include using namespace std;int main() { int n; while (cin >> n, n) { for (int i = 1; i <= n; i++) { for (int k = 1; k <= n; k++) { cout << max(i - k + 1, k - i + 1) << " "; } cout << endl; } cout << endl; } return 0;}755
755. 平方矩阵 III – AcWing题库
#include #include #include using namespace std;int main() { long n, m[31] = {1}; for (int i = 1; i > n, n) { for (int i = 1; i <= n; i++) { for (int k = 1; k <= n; k++) { cout << m[i + k - 2] << " "; } cout << endl; } cout << endl; } return 0;}756 ⭐
756. 蛇形矩阵 – AcWing题库
涉及到状态的转变，逻辑题
解题法-1 传统逻辑解题
#include #include #include using namespace std;int main() { int a[101][101]; memset(a, 0, sizeof a); int n, m; cin >> n >> m; int i = 0, k = 0; int c = 1; int mode = 1; while (i - 1 >= 0 && a[i - 1][k] == 0 || i + 1 = 0 && a[i][k - 1] == 0 || k + 1 < n && a[i][k + 1] == 0 || a[i][k] == 0) { if (mode == 1) { a[i][k] = c++; if (k + 1 == m || a[i][k + 1] != 0) { mode = 2; i++; } else k++; } else if (mode == 2) { a[i][k] = c++; if (i + 1 == n || a[i + 1][k] != 0) { mode = 3; k--; } else i++; } else if (mode == 3) { a[i][k] = c++; if (k - 1 < 0 || a[i][k - 1] != 0) { mode = 4; i--; } else k--; } else { a[i][k] = c++; if (i - 1 < 0 || a[i - 1][k] != 0) { mode = 1; k++; } else i--; } } for (int i = 0; i < n; i++) { for (int k = 0; k < m; k++) { cout << a[i][k] << " "; } cout << endl; } return 0;}解题法-2 将移动方式保存到数组中
#include #include #include using namespace std;int res[101][101];int main() { int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int m, n; cin >> n >> m; int mode = 0; for (int k = 1, x = 0, y = 0; k <= m * n; k++) { res[x][y] = k; int a = x + dx[mode]; int b = y + dy[mode]; if (a = n || b = m || res[a][b]) { mode = (mode + 1) % 4; a = x + dx[mode]; b = y + dy[mode]; } x = a; y = b; } for (int i = 0; i < n; i++) { for (int k = 0; k < m; k++) { cout << res[i][k] << " "; } cout << endl; } return 0;}2023年8月27日fgets
默认读入字符串遇到空格就会停止。
fgets用于读入一整行，参数为字符数组地址、最大读多少字符、从哪读，会读入最后的回车符
fgets(s,100000,stdin);cin
cin.getline用于读入一整行，参数为字符数组地址、最大读多少字符
cin.getline(s,1000);getline
getline用于string类型读入一整行
getline(cin,s);puts
puts 输出字符数组，包括换行符
puts(s);cstring 库函数
库里有 strlen，strcmp 、strcpy 与 memcpy 类似
strlen(s); // 只计算字符串的元素，\0不计入其中strcmp(a,b); // 字典序比较，小于返回-1（可能其他负数），等于返回0，大于返回1（可能其他正数） strcpy(a,b); // 把b复制给a两层循环优化
在这种循环下，每次循环 strlen(s) 都要执行一遍，是两层循环。
for (int i = 0; i < strlen(s) ; i++)改成
for (int i = 0, len=strlen(s) ; i < len; i++)或直接
for (int i = 0; i < s[i]; i++)80%的情况用string处理
string s1; // 默认的空字符串string s2 = s1; // s2是s1的副本string s3 = "hiya"; // s3是该字符串字面值的副本string s4(10,'c'); // s4的内容是 ccccccin >> s1 >> s2;// string 不能用scanf读但可以用printf输出printf("%s\n",s1.c_str());cout << s1 << s2;cout << s1.empty() << endl; // 布尔值返回 01cout << s3.empty() << endl; // 布尔值返回 0cout << s3.size() << endl; // 数组长度，O(1)复杂度// 支持比较运算符，相加string s3 = s3 + s4;s3 += s4;s3 = s3 + " is great!" + '!'; // 这里不能用 +=// 加法运算符两边必须有一个 string 类型// 遍历 stringfor (char c : s) cout << c << endl; // 等价于 for 循环体里 char c = str[i]// 引用符号（可以改变 c 的值）for (char &c : s) // 让编译器去猜类型auto s = "Hello World!" // char[]for (auto c : s)裁剪字符串
使用 string类型的 substr 函数
cout << a.substr(0, max_index + 1) + b + a.substr(max_index + 1) << endl;764 勿忘结束符
764. 输出字符串 – AcWing题库
简单，但是容易忘记给b加结束符
#include #include using namespace std;int main() { string a, b; getline(cin, a); for (int i = 0; i < a.size(); i++) { b[i] = a[i] + a[(i + 1) % a.size()]; cout << b[i]; } b = b + '\0'; cout << b; return 0;}770 sstream 库
AcWing 770. 单词替换 – AcWing
不用库的话，判断空格位置，比较麻烦
#include #include #include using namespace std;int main() { string s, a, b, word, res; getline(cin, s); cin >> a >> b; int index = 0; for (int i = 0; i <= s.size(); i++) { if (s[i] == ' ' || s[i] == 0) { if (strcmp(word.c_str(), a.c_str()) == 0) { res = res + b + ' '; } else res = res + word + ' '; word = ""; } else word = word + s[i]; } cout << res; return 0;}用库的话，把读入的字符串再当成一个流（类似于split操作了）
#include #include #include #include using namespace std;int main() { string s, a, b, word, res; getline(cin, s); cin >> a >> b; stringstream ssin(s); string str; while (ssin >> str) if (str == a) cout << b << ' '; else cout << str << ' '; cout << res; return 0;}771 ⭐ 第一类双指针算法
771. 字符串中最长的连续出现的字符 – AcWing题库
#include #include using namespace std;int main() { int n; cin >> n; while (n--) { int max_count = 0; char max_char; string a; cin >> a; for (int i = 0; i < a.size(); i++) { int j = i; while (j < a.size() && a[i] == a[j]) j++; int diff = j - i; if (max_count < diff) { max_char = a[i]; max_count = diff; } i = j - 1; // i 还会再++一次 } cout << max_char << " " << max_count << endl; } return 0;}774 back()、pop_back()
774. 最长单词 – AcWing题库
#include #include using namespace std;int main() { string word, s_max; // s.back() 获取最后一个字符 s.pop_back() 去掉最后一个字符 while (cin >> word) { if (word.back() == '.') word.pop_back(); if (word.size() > s_max.size()) s_max = word; } cout << s_max; return 0;}这里还有一个思想是按词处理而不是先读入一整串再sstream，类似下面的
AcWing 775. 倒排单词 – AcWing
#include #include using namespace std;int main() { string res, word; while (cin >> word) { res = word + " " + res; } cout << res; return 0;}776 ⭐
776. 字符串移位包含问题 – AcWing题库
#include #include #include using namespace std;int main() { string a, b; cin >> a >> b; if (b.size() > a.size()) swap(a, b); for (int i = 0; i < a.size(); i++) { a = a.substr(1) + a[0]; int k = 0; for (int i = 0; i + b.size() <= a.size(); i++) { while (k < b.size() && a[i + k] == b[k]) k++; if (k == b.size()) { puts("true"); return 0; } else k = 0; } } puts("false"); return 0;}2023年8月30日777
777. 字符串乘方 – AcWing题库
#include #include using namespace std;int main() { string s; while (cin >> s, s != ".") { for (int i = 1; i <= s.size(); i++) { if (s.size() % i != 0) continue; string a = s.substr(0, i); string res; int times = s.size() / i; for (int i = 1; i <= times; i++) { res += a; } if (res == s) { cout << times << endl; break; } } } return 0;}也可以通过字符串移位的贪心算法实现
#include #include using namespace std;int main() { string s; while (cin >> s, s != ".") { string res = s; for (int i = 1; i <= res.size(); i++) { res = res.substr(1) + res[0]; if (res == s) { cout << res.size() / i << endl; break; } } } return 0;}778
778. 字符串最大跨距 – AcWing题库
如何处理输入的问题
string s, s1, s2; char c; while (cin >> c, c != ',') s += c; while (cin >> c, c != ',') s1 += c; while (cin >> c) s2 += c;779. 最长公共字符串后缀 – AcWing题库
这题没难度
函数默认参数
默认值需要是后面连续的几个参数，或全部都有默认值
void foo(int a,int b = 5,int c = 10)sizeof 数组问题
main函数显示的是数组长度（40字节），foo函数显示的是指针的长度（64位8字节）。
void foo(int b[]){ cout << sizeof b;}int main(){ int a[10]; cout << sizeof a << endl; foo(a); return 0;}/*408*/inline
加在函数定义前，相当于函数展开，适用于函数调用次数小的情况。对递归函数无效
823 简单递归问题
821. 跳台阶 – AcWing题库
822. 走方格 – AcWing题库
823. 排列 – AcWing题库
#include #include using namespace std;const int N = 10;int n;int pl(int index, int a[], bool h[]) { if (index == n) { for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; } else for (int i = 1; i > n; int a[10] = {0}; bool h[10] = {0}; pl(0, a, h); return 0;}指针、引用
int a = 3;int* p = &a; // 指针int& p2 = a; // 引用、别名链表与指针 ⭐
#include using namespace std;struct Node { int val; Node* next; Node(int _val) : val(_val), next(NULL) {}};int main() { Node* p = new Node(1); // ^ 加new返回地址，不加new返回变量 auto p2 = new Node(2); auto p3 = new Node(3); p->next = p2; // ^ 规定:如果p是指针用->、是变量用. p2->next = p3; // IMPORTANT 头结点：第一个结点的地址而不是值 Node* head = p; for (Node* i = head; i; i = i->next) { cout <val <next = p; head = u; for (Node* i = head; i; i = i->next) { cout <val <next = head->next->next; for (Node* i = head; i; i = i->next) { cout <val << endl; } return 0;}84
84. 求1+2+…+n – AcWing题库
条件表达式脑筋急转弯
class Solution { public: int getSum(int n) { int res = n; n > 0 && (res += getSum(n - 1)); return res; }};28
28. 在O(1)时间删除链表结点 – AcWing题库
class Solution { public: void deleteNode(ListNode* node) { node->val = node->next->val; // 伪装成下一个点 node->next = node->next->next; // 将node删除（访问不到） // *(node) = *(node->next); }};36 ⭐
36. 合并两个排序的链表 – AcWing题库
二路归并，赋值从右往左
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution { public: ListNode* merge(ListNode* l1, ListNode* l2) { auto dummy = new ListNode(-1), tail = dummy; while (l1 && l2) { if (l1->val val) { tail = tail->next = l1; l1 = l1->next; } else { tail = tail->next = l2; l2 = l2->next; } } if (l1) tail->next = l1; else tail->next = l2; return dummy->next; }};87 ⭐
AcWing 87. 把字符串转换成整数 – AcWing
class Solution { public: int strToInt(string str) { int i = 0, flag = 1; while (i < str.size() && str[i] == ' ') i++; if (i == str.size()) return 0; else if (str[i] == '-') { flag = -1; i++; } else if (str[i] == '+') { flag = 1; i++; } long long sum = 0; while (i = '0' && str[i] INT_MAX) { return INT_MAX; } else if (sum * flag < INT_MIN) return INT_MIN; } sum = sum * flag; return (int)sum; }}; for (; i < str.size(); i++) { if (str[i] != ' ') break; }for 循环均可修改为while减少代码量
while (i < str.size() && str[i] == ' ') i++;35 ⭐
AcWing 35. 反转链表 – AcWing
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution { public: ListNode* reverseList(ListNode* head) { if (!head || !head->next) return head; // ^ 特殊情况 auto A = head; auto B = head->next; A->next = NULL; while (B) { auto C = B->next; B->next = A; A = B, B = C; } return A; }};递归写法
class Solution { public: ListNode* reverseList(ListNode* head) { if (!head || !head->next) return head; // ^ 特殊情况 auto tail = reverseList(head->next); head->next->next = head; head->next = NULL; return tail; }};66 ⭐⭐
66. 两个链表的第一个公共结点 – AcWing题库
class Solution { public: ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) { auto A = headA, B = headB; while (A != B) { if (A) A = A->next; else A = headB; if (B) B = B->next; else B = headA; } return A; }};29
29. 删除链表中重复的节点 – AcWing题库
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution { public: ListNode* deleteDuplication(ListNode* head) { if (!head || !head->next) return head; auto tmp = new ListNode(-1); tmp->next = head; auto A = tmp, B = head; while (B && B->next) { auto C = B->next; if (C->val == B->val) { while (C && C->val == B->val) C = C->next; A->next = C; B = C; } else { A = B; B = B->next; } } return tmp->next; }};因为B可以由A推导出，又可以改为
class Solution { public: ListNode* deleteDuplication(ListNode* head) { auto tmp = new ListNode(-1); tmp->next = head; auto A = tmp; while (A->next) { auto C = A->next; while (C->next && A->next->val == C->next->val) C = C->next; if (C != A->next) A->next = C->next; else A = A->next; } return tmp->next; }};vector
int q[100000][100000] 需要大量空间，用可变长数组可以节省很多空间。结尾插入O(1)，开头插入O(n)，自带比较，按字典序比
#include #include using namespace std;int main() { vector a({1, 2, 3}); vector b[233]; struct Rec { int x, y; }; vector c; // a.size(); // a.empty(); // a.clear(); vector::iterator it = a.begin(); // 当成指针来看，it 相当于访问 a[0]， [begin,end) // a.end() 最后位置的下一个位置 // *a.begin() 取值 for (int i = 0; i < a.size(); i++) { } for (auto i = a.begin(); i < a.end(); i++) { } for (int x : a) { } // a.front() 等价于 a[0] 等价于 *a.begin() // a.back() 等价于 a[a.size()-1] // a.pushback(4); 在数组最后添加元素 O(1) // a.pop_back(); 删除末尾元素 return 0;}queue
#include #include #include using namespace std;int main() { queue q; queue a; struct Rec { int x, y; // 优先队列，大根堆，自定义结构体要重载小于号 // 小根堆，重载大于号 bool operator<(const Rec& t) const { return x < t.x; } }; queue c; // ^ 优先队列，每次优先弹最大值，大根堆 priority_queue a; // ^ 小根堆 priority_queue<int, vector, greater> b; priority_queue<pair> b; // 普通队列 a.push(3); // 队尾插入元素 a.pop(); // 队头弹出元素 a.front(); // 返回队头元素 a.back(); // 返回队尾元素 // 优先队列 b.push(1); b.top(); // 取最大值 b.pop(); // 删除最大值 // IMPORTANT 队列、优先队列、栈没有clear函数 // 可以重新初始化 q = queue(); return 0;}stack
#include #include using namespace std;int main() { stack stk; stk.push(1); stk.top(); stk.pop(); // 弹出但不返回 return 0;}deque
在队头队尾插入都是O(1)
#include #include using namespace std;int main() { deque a; a.begin(), a.end(); a.front(), a.back(); a.push_back(1), a.push_front(1); a[0]; a.pop_back(), a.pop_front(); a.clear(); return 0;}set
红黑树
#include #include using namespace std;int main() { set a; // 元素不能重复 multiset b; // 元素可以重复 set::iterator it = a.begin(); it++; it--; // 前驱、后继 ++it, --it; a.end(); a.insert(1); a.find(1); // 返回迭代器，找不到返回 a.end() // 判断x在a中是否存在 a.lower_bound(1); // IMPORTANT 找到大于等于x的最小的元素的迭代器 a.upper_bound(1); // 找到大于x的最小的元素的迭代器 a.count(1); // 存在x返回1，不存在返回0，如果是multiset则返回个数 a.erase(1); // 删除 // struct Rec { int x, y; bool operator<(const Rec& t) const { return x < t.x; } }; set c; // size/empty/clear/ 也有迭代器 return 0;}map
#include #include unordered
unordered_set使用哈希表
#include #include #include #include using namespace std;int main() { unordered_set a; // 比set效率高些，但不支持二分 unordered_multiset b; // 比set效率高些，但不支持二分 unordered_map c; // 比map效率高些，但不支持二分 return 0;}bitset
很长的01二进制串
#include #include using namespace std;int main() { bitset a, b; a[0] = 1; a[1] = 1; a.set(3); // 某位设为1 a.reset(3); // 某位设为0 // 支持位运算 a &= b; return 0;}pair
#include #include using namespace std;int main() { pair a; a = {3, "test"}; cout << a.first << " " << a.second << endl; // 老版本 make_pair(4,"abc") // pair 支持比较，先比较first然后比较second return 0;}与、或、取反、异或
& | ~ ^
常用二进制操作 ⭐
求某一位数字
int i = a >> 2 & 1;返回最后一个1
a & (~a + 1) // 0000001000// 又因为 -a 等同 ~a+1a & -a常用库函数 ⭐
#include #include #include #include using namespace std;struct Rec { int x, y; bool operator<(const Rec &t) const { return x < t.x; }} rec[5];bool cmp(int a, int b) { // a是否应该排在b的前面 return a < b;}bool cmp2(Rec a, Rec b) { // a是否应该排在b的前面 return a.x < b.x;}int main() { // ^ reverse vector a({1, 2, 3, 4}); reverse(a.begin(), a.end()); for (int x : a) cout << x << ' '; cout << endl; int b[] = {1, 2, 2, 4, 5}; reverse(b, b + 5); // 第二个参数写数组最后一个位置的下一个 // ^ unique int m = unique(b, b + 5) - b; // 不同元素数量个数 int m = unique(a.begin(), a.end()) - a.begin(); // 不同元素数量个数 a.erase(unique(a.begin(), a.end()), a.end()); // 把没有用的部分删掉 // ^ random_shuffle srand(time(0)); random_shuffle(a.begin(), a.end()); // 打乱数组 // ^ sort sort(a.begin(), a.end()); // 从小到大 sort(a.begin(), a.end(), greater()); // 从大到小 sort(a.begin(), a.end(), cmp); for (int i = 0; i < 5; i++) { rec[i].x = -i; rec[i].y = i; } sort(rec, rec + 5, cmp2); sort(rec, rec + 5); // 重载小于号 // ^ lower_bound/upper_bound int *p = lower_bound(b, b + 5, 3); // 返回迭代器 int *p = upper_bound(b, b + 5, 3); // 返回迭代器 return 0;}范围遍历
比for循环快一点点
int cnt = 0; for (int x : nums) { if (x == k) cnt++; }68
AcWing 68. 0到n-1中缺失的数字 – AcWing
class Solution { public: int getMissingNumber(vector& nums) { unordered_set s; for (int i = 0; i <= nums.size(); i++) s.insert(i); for (auto x : nums) s.erase(x); return *s.begin(); }};双指针法 ⭐ 32
32. 调整数组顺序使奇数位于偶数前面 – AcWing题库
class Solution { public: void reOrderArray(vector &array) { int i = 0, j = array.size() - 1; while (i < j) { while (i < j && array[i] % 2) i++; while (i < j && array[j] % 2 == 0) j--; if (i < j) swap(array[i], array[j]); } }};2023年8月31日20
20. 用两个栈实现队列 – AcWing题库
class MyQueue { public: /** Initialize your data structure here. */ stack a, b; MyQueue() {} /** Push element x to the back of queue. */ void push(int x) { a.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { while (a.size() > 1) b.push(a.top()), a.pop(); int t = a.top(); a.pop(); while (b.size()) a.push(b.top()), b.pop(); return t; } /** Get the front element. */ int peek() { while (a.size() > 1) b.push(a.top()), a.pop(); int t = a.top(); while (b.size()) a.push(b.top()), b.pop(); return t; } /** Returns whether the queue is empty. */ bool empty() { return a.empty(); }};75
75. 和为S的两个数字 – AcWing题库
使用哈希表，只需要遍历一遍数组
class Solution { public: vector findNumbersWithSum(vector& nums, int target) { unordered_set s; for (auto x : nums) { if (s.count(target - x)) return {target - x, x}; s.insert(x); } }};51 next_permutation ⭐
51. 数字排列 – AcWing题库
返回一个序列的下一个序列，如果是最大了返回false
class Solution { public: vector<vector> permutation(vector& nums) { sort(nums.begin(), nums.end()); vector<vector> res; do { res.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); return res; }};26 lowbit
AcWing 26. 二进制中1的个数 – AcWing
class Solution { public: int NumberOf1(int n) { int res = 0; for (int i = 0; i > i & 1) res++; } return res; }};class Solution { public: int NumberOf1(int n) { int res = 0; while (n) { n -= n & -n; res++; } return res; }};第二种方法快一些
420 火星人 ⭐⭐
420. 火星人 – AcWing题库
#include #include #include using namespace std;const int N = 10010;int n, m;int q[N];int main() { cin >> n >> m; for (int i = 0; i > q[i]; while (m--) next_permutation(q, q + n); for (int i = 0; i < n; i++) cout << q[i] << " "; return 0;}
#include #include #include using namespace std;const int N = 10010;int n, m;int q[N];int main() { cin >> n >> m; for (int i = 0; i > q[i]; while (m--) { int k = n - 1; while (q[k - 1] > q[k]) k--; int min_max = k; for (int i = k; i q[i] && q[i] > q[k - 1]) min_max = i; } swap(q[k - 1], q[min_max]); reverse(q + k, q + n); } for (int i = 0; i < n; i++) cout << q[i] << " "; return 0;}862
862. 三元组排序 – AcWing题库
#include #include using namespace std;struct Data { int x; double y; string z; bool operator<(const Data &t) const { return x > n; for (int i = 0; i > a[i].x >> a[i].y >> a[i].z; sort(a, a + n); for (int i = 0; i < n; i++) { printf("%d %.2lf %s\n", a[i].x, a[i].y, a[i].z.c_str()); } return 0;}