第一讲:变量、输入输出、表达式、顺序语句
-
float 有效位数 6-7位,很多情况下位数不够,涉及浮点数计算使用double 类型
-
#inlclude <cstdio>
包含 scanf 和printf 输入输出#include <iostream>
包含cin cout ,在使用前 要声明作用域 常用using namespace std;
-
scanf 输入char 类型时 要注意 空格和回车也会读入。
double a = 1.222;
printf("%10.2lf", a);
%f | float |
---|---|
%lf | double |
%d | int |
%lld | long long |
%s | 字符串 |
%c | char |
%10.2lf ----保留两位小数 右对齐10位
%-10.2lf -----左对齐10位
%010.2lf -----右对齐 10 位 用0填充
- 浮点数判断相等问题 两个浮点数有时在精度上存在问题,需要通过
abs(a - b) <1e9
的方式判定大小
第二讲 判断语句
- 感觉没什么东西记
第三讲 循环
-
完全数 枚举时约数时 i * i <= n 缩小判断次数,防止超时
-
连续输入
while(cin >> n){} // 输入到EOF 自动结束循环
while (cin >> n, n) // ,后作为判断,当读入0时结束循环
- 菱形 曼哈顿距离
abs(i - cx) + abs(j - cy)
第四讲 数组
-
平方矩阵1 距离四条边的最小值
-
高精度计算
计算2的N次方。数据太大 普通变量存不下
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[3000], size = 1, n;
a[0] = 1;
cin >> n;
while (n--) // 运算次数
{
int t = 0; //表示进位
for (int i = 0; i < size; i++)
{
t += a[i] * 2;
a[i] = t % 10;
t /= 10
}
if (t) a[size ++] =t; // 先读取 size的值 再 size + 1
}
for (int i = size - 1;i >= 0; i --) cout << a[i];
cout << endl;
}
-
全局变量定义的 数组 开辟在堆空间 自动初始化为0, 栈空间需要手动初始化
int a[100] = {0};
-
平方矩阵2
abs(i - j) + 1;
-
平方矩阵3
for (int i = 0; i < n; i++)
{
for(int j = 0; j < n; j ++)
{
int v = 1;
for (int k = 0; k < i + j; k++) v * 2;
cout << v <<' ';
}
}
-
蛇形矩阵
-
偏移量 右 下 左 上 (0,1)(1,0) (0,-1) (-1,0)
x轴 {0, 1, 0, -1} y轴 {1, 0, -1, 0}
撞墙判断 :
- 越界
- 已经有读入的值
#include <iostream>
using namespace std;
int res[100][100];
int main()
{
int n, m;
cin >> n >> m;
int dx[] = {0,1, 0, -1}, dy[] = {1, 0, -1, 0};
for (int x = 0, y = 0, d = 0, k=1; k<= n * m; k++)
{
res[x][y] = k;
int a = x + dx[d], b = y + dy[d];
if (a < 0|| a >= n || b < 0 || b >= m ||res[a][b])
{
d = (d + 1) % 4;
a = x + dx[d] ,b = y + dy[d];
}
x = a, y = b;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) cout << res[i][j] << ' ';
cout << endl;
}
return 0;
}
第五讲 字符串
-
定义
char s[] = "abcd";
string str = "abcd";
- 以\0结束 定义的长度要比实际长度多一位
char a[5] = "abcd";
-
读取
- cin 读取字符串 过滤空格和 回车 string 和 普通类型都能读取
scanf(“%s”, &s);
读取字符串同 cin 只能读取 普通类型getline(cin,s);
读取一行字符串 用于string 类型fgets(s, 5, stdin);
读取一行字符串 用于普通类型cin.getline(s, 4);
读取一行普通类型 字符串
-
输出
- printf(“%s”, s); printf 不能直接输出string
printf("%s", s.c_str());
- puts(“abcd”) 同printf
- cout << s;
- printf(“%s”, s); printf 不能直接输出string
-
遍历
- 普通类型
for (int i = 0; s[i] ; i++) cout << s[i];
- string
for (int i = 0; i < s.size(); i++) cout << s[i];
for (char c : s) cout << c;
-
提取 某个字符的ACSII码
s[i] - 'a';
-
string拼接的时候 当两个对象不是string 类型时会报错
-
#include <cstring>
- strlen() 放回字符串长度
- strcmp(a, b) 比较大小 大返回 1 小返回 -1 等于返回 0
- strcpy(a, b) 将b 赋值给 a
-
第一类双指针
int j = i;
while (j < size && s[j] == s[i]) j++;
i = j - 1;
- stringstream 的用法
定义
stringstream ssin(s)
库
#include <sstream>
stringstream ssin(s);
string str;
while (ssin>> str)
if (str == a) cout << b << ' ';
else cout << str << ' ';
-
子串判断问题
for (int i = 0; i < a.size() - b.size(); i++)
{
int j = 0
for (; j < b.size(); j ++)
if (a[i + j] != b[j])
break;
if (j == b.size())
return true;
}
第六讲 函数
- 多维数组形参的写法:
void print(int a[][10]){...}
第二维一定要写
- 短路 逻辑表达式 && 语句
第七讲 结构体 指针
-
结构体 和类 唯一的区别 类默认是private 结构体默认是public
-
链表
struct Node
{
int val;
Node* next;
Node(int _val) : val(_val), next(NULl) {} // 构造函数
};
int main()
{
Node* p = new Node(1); // new Node 返回地址;Node 返回值
auto q = new Node(2); // auto 自动推断 类型
auto o = new Node(3);
p->next = q;
q->next = o;
Node* head = p;
}
头结点 第一个节点的地址。
链表的遍历
for (Node* i = head;i; i = i->next)
{
cout << i->val <<endl;
}
第八讲 STL容器
vector
定义
#include <vector>
vector <int> a; // 定义一个变长度的的 int 数组
vector <int> b[233] // 定义第一维 233 第二维长度动态变化的二维数组
struct rex{
int x, y;
};
vector <rec> c; // 自定义的结构体类型的vector
函数
vector <int> a;
a.size();
a.empty();
a.clear(); //清空
a.push_back(x) // x 插入a的尾部
a.pop_back() //弹出最后一个
迭代器
定义
vector<int> ::iterator it = a.begin();
vector<int> ::iterator it = a.end(); //最后一个后一个
*it // 取到vector 的值
遍历
for (int i = 0; i < a.size(); i++) cout << a[i]<< ' '
for (vector<int>::iterator it = a.begin(); it != a.end(); it ++)
cout <<*it <<' ';
for (int x : a) cout << x <<' ';
front/ back
a.front() == a.begin();
a.back() == a.end() - 1;
队列queue
定义
#include <queue>
queue<int> a;
queue<double> b;
struct rec{...};
queue<rec> c;
priority_queue<int> q; //大根堆
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
priority_queue<pair<int,int>> q;
struct rec
{
int a, b;
bool operator< (const rec& t) const
{
return a < t.a;
}
};
priority_queue<rec> q;
操作
循环队列
a.push(1); // 队尾插入
a.pop(); // 队头弹出
a.front(); // 返回队头
a.back(); // 返回队尾
优先队列 priority_queue
a.push(1); // 插入
a.pop(); // 删除堆顶元素
a.top(); // 查询堆顶元素
队列没有clear函数
stack
#include <stack>
stack<int> stk;
stk.push(1);
stk.pop();
stk.top();
deque 双端队列
#include <deque>
begin/end
push_back
push_front
pop_back
pop_front
clear
set
#include <set>
set<int> a; // 元素不能重复
multiset<int> b;// 元素可以重复
struct rec
{
int x, y;
bool operator< (const rec& t) const
{
return x < t.x;
}
};
set<rec> c;
迭代器
set<int> :: iterator it;
it ++; it --; // ++ 下一个大的元素 -- 上一个小的元素
s.begin();
s.end();
函数
s.insert(x) // 插入x
s.find(x) // 查找 返回迭代器
s.lower_bound(x); // 查找大于等于x的最小的一个 返回迭代器
s.upper_bound(x); // 查找大于x 最小的一个 返回迭代器
s.erase(x);
s.erase(it);
s.count(x) // 个数
map
#include <map>
map <key_type, value_type> name;
map <long long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;
unordered_set
无序的set
unordered_map
无序的map
bitset
用于位运算
bitset<1000> a
a.set(3); // a[3]设置为1
a.reset(3); // a[0] 设置为0
a.count() // 计数
pair
pair<int, string> a, b;
a = {3, "ddd"};
cout << a.first<< ' ' << a.second <<endl;
a = make_pair(4, 'agg'); // 重新赋值。
第九讲
-
求x的第k位数字 x>>k & 1;
-
lowbit(x) = x & -x 返回x的最后一位1
-
reverse 翻转
reverse(a.begin(), a.end()); reverse(a, a + n);
-
unique 去重
-
random_shuffle 随机打乱
-
sort
-
lower_bound/upper_bound
-
lower_bound 大于等于x的迭代器的位置
-
upper_bound 大于x的迭代器的位置
-
重载操作符 ,
bool operator< (const 结构体 &t) const
{
return x < t.x;
}
大佬nb