X02-day8-1班默写资料
2023-08-10 13:31:52
发布于：浙江
67阅读
0回复
0点赞
1.所学过的容器有哪些
set<int> se;
map<int,int> mp;
vector<int> ve;
stack<int> st;
queue<int> q;
string;
2.迭代器遍历的全部拼写【不允许使用auto】
set<int>::iterator it;
3.队列的函数方法有哪些
q.push();
q.pop();
q.front();
q.empty();
q.size();
4.二分查找模板
int solve(int a[],int x){
int cnt = -1;
while(l<=r){
int mid = (l+r)/2;
if(a[mid]>x){
cnt = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
return cnt;
}
5.DFS模板
void dfs(int x,int y){
if(x == zdx && y==zdy){
flag = 1;
return ;
}
for(int i=0;i<4;i++){
int xx = x + dirx[i];
int yy = y + diry[i];
if(xx < 1 ||xx > n ||yy < 1 || y > m) continue;
if(s[xx][yy] == '#') continue;
if(vis[xx][yy]== 1) continue;
vis[xx][yy] = 1;
dfs(xx,yy);
}
}
6.BFS模板
void bfs(int x,int y){
queue<node> q;
q.push({x,y});
vis[x][y] = 1;
while(!q.empty()){
x = q.front().x;
y = q.front().y;
q.pop();
if(x == zdx && y == zdy){
return 1;
}
for(int i=0;i<4;i++){
xx = x + dirx[i];
yy = y + diry[i];
if(xx < 1 ||xx > n ||yy < 1 || y > m) continue;
if(s[xx][yy] == '#') continue;
if(vis[xx][yy]== 1) continue;
vis[xx][yy] = 1;
q.push({xx,yy});
}
}
}
7.图上搜索
void bfs(int x){
queue<int> q;
q.push(x);
vis[x] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=0;i<ve[u].size();i++){
int v = ve[u][i];
if(vis[v] == 1) continue;
vis[v] = 1;
q.push(v);
}
}
}
8.树的存储 + 先序遍历
#include<iostream>
using namespace std;
const int N = 1e3+5;
struct node{
int data;
int l,r;
}tree[N];
int n,a[N];
void dfs(int root){
if(tree[root].data == 0){
return ;
}
cout << tree[root].data;
dfs(tree[root].l);
dfs(tree[root].r);
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> tree[i].data >> tree[i].l >> tree[i].r;
}
dfs(1);
return 0;
}
9.高精度加法
void add(string s1,string s2){
int lens1 = s1.length();
int lens2 = s2.length();
for(int i=0;i<lens1;i++){
a[i] = s1[lens1 - 1 - i] - '0';
}
for(int i=0;i<lens2;i++){
b[i] = s2[lens2 - 1 - i] - '0';
}
int len = max (lens1,lens2);
for(int i=0;i<len;i++){
c[i] += a[i] + b[i];
c[i+1] += c[i]/10;
c[i] %= 10;
}
while(c[len-1]){
len++;
}
for(int i=len-1;i>=0;i--){
cout <<c[i];
}
}
10.高精度除法
void division(string s,long long m){
long long sum = 0;
int len = s.length();
int cnt = 0;
for(int i=0;i<len;i++){
sum = sum * 10 + (s[i] - '0');
a[i] = sum / m;
sum %= m;
}
while(cnt<len-1 && a[cnt] == 0){
cnt ++;
}
for(int i=cnt;i<len;i++){
cout << a[i];
}
}
有帮助，赞一个