X02随笔

        //X02为期十天笔记

一、Day01: 时间复杂度, 空间复杂度: 程序性能衡量的指标, 因为CPU作为计算机的中央处理器在单位时间内运行次数是有限制的, 所以解决问题时候, 应该尽可能的减少执行次数和内存开销来保证完成预期功能。这就体现出高手与菜鸟的区别了。

eg:
1+2+3+4+.....+n = ? for(int i=1;i<=n;i++) s+=i; cout<<s; 菜鸟写法, 时间复杂度为O(n), 随着n的增大, for循环执行次数也会正比增大, 并不是最优解法。

  优化:  s = (1+n)*n/2; 无论n如何改变, 该代码就一行,只会执行一次, 时间复杂度是: O(1).

记住: O(2*n+10) 等价于O(n), 因为当n无穷大, 常数可以忽略为1.
O(n2+2n+10) 等价于 O(n2); 因为n无穷大, 2n+10基本上不影响。 换句话说: n2+2n+10 == n2

空间复杂度同理, 一般不要在循环内创建变量, 极其消耗内存。
时间复杂度:
O(logn)<O(sqrt(n))<O(n)<O(nlongn)<O(n2)<O(n3)<O(n!); 二分查找的效率高,就是因为时间复杂度极其低,达到了对数级别 - O(logn), 以2为底数的求对数 次查找。

模拟算法: 一切的C++编程语言写出来的程序都是为了模拟"问题的场景", 将遇到的问题场景使用程序去描述, 通过运行程序得到预期的结果。 电脑简化了过程， 极快的运行出预期的答案。

枚举算法: 俗称"挨个试一下", 逐个尝试可能的结果, 暴力枚举极大的降低了效率, 但却是是一种解决问题的手段， 在部分场景下暴力枚举因为超时,并不满足业务需求, 此时需要使用特殊算法解决。 常见的: 鸡兔同笼, 水仙花数就可以使用枚举。

前缀和: 原始数组 - a[1], a[2],a[3]....a[n-1],a[n]
前缀和数组: pre[1] = a[1], pre[2] = pre[1]+a[2]; pre[n] = pre[n-1]+a[n];
作用: 区间求和操作特别快, 因为降低了时间复杂度, 区间循环累加省略了。
[L,R]和 = pre[R] - pre[L-1];

差分: 比前缀和难一点, 没出现在课件中, 掌握差分起始和结束的增量即可。

vector数组。 不想多说, STL容器, 动态数组, 好处 - 自动扩容, 提供的函数: push_back(), size(), resize(), erase()等极大的方便对vector中的数据进行操作。

STL: string, list, map, queue,stack, set, multiset, vector, prority_queue 自己总结。

二、Day02 - 贪心算法
问题拆解为若干不, 每一步的最优解叠加出全局的最优解。
1 2 10 5 20 100 50元钱分别一张, 只能拿3张,如何拿到最大面值?
贪心: sort()排序, 按照最小或者最大, 结构体数组排序。
接水问题, 礼物分组, 最优装载, 活动安排 认真体会。 小码君赛马设计双指针思想

#include <iostream>
#include <algorithm> //sort()函数
using namespace std;
struct Tree{
double weight; //每棵树都有重量
double val; //每棵树都有价值
double rate; //单位价值
};
//按照 单位价值从高到低进行排序, 小码君优先选取单价价值高的树木
bool cmp(Tree x, Tree y){
return x.rate>y.rate;
}

int n,m;
double ans=0; //小码君每摘走一点树木,ans增加对应的价值
Tree a[1001]; //保存每棵树的信息

int main(){
cin>>n>>m; //输入n棵树, m小码君的袋子承重
//输入n棵树的信息, 保存到结构体数组a中
for(int i=1;i<=n;i++) {
cin>>a[i].weight>>a[i].val;
//因为树可以分割。 优先选取最大单位价值(a[i].rate)的树
a[i].rate = a[i].val/a[i].weight;
}
sort(a+1,a+1+n,cmp); //就对a数组中的n棵树进了排序(按照单价价值)。

//依次去取出每棵树 
for(int i=1;i<=n;i++){
	if(a[i].weight<=m){//小码君的袋子承重大于等于第i棵树的重量 
		ans+=a[i].val;
		m-=a[i].weight;	
	}
	else{//当前树木的重量>小码君袋子的剩余承重 
		ans+=m*a[i].rate;
		break;	//小码君的袋子已经被填充满了 
	}
}
printf("%.2lf",ans);
return  0;

}

#include <bits/stdc++.h>
using namespace std;
int w,n,ans=0; //w:分组最大不能超出的价值。 n:纪念品的件数。 ans:分组数
int a[30010]; //存储每件纪念品的价值
int main(){
cin>>w>>n;
for(int i=1;i<=n;i++){//输入n件纪念品的价值
cin>>a[i];
}
sort(a+1,a+n+1); //默认就是升序
int l = 1, r = n; //l--> <----r
while(l<=r){ //游标还没有相遇, 分组未结束
if(a[l]+a[r]<=w){//可以分一组
l++;
r--;
ans++; //组数自增1
}
else{
r--;
ans++; //自成一组
}
}
cout<<ans;
return 0;
}

三、Day03 - 二分查找和二分答案
二分查找核心思想: 在有序的序列中,不断的折半缩小查找范围,直到left和right相遇表示查找结束, 找得到返回元素位置, 找不到返回-1。 时间复杂度: log2(n)

二分答案: 答案有无数个可能，但是答案呈现一个单调递增或递减的规律, 随着答案的变化, 一定会导致成本的递增或递减, 所以可以使用二分的思想找到最优的答案来满足条件的同时还能最大化的降低成本。 核心思想: while结束, ans记录最优的答案。

二分查找:
#include <bits/stdc++.h>
using namespace std;
/*
二分: 有序序列。1 2 2 2 3 算
*/
//在数组a中查找x所在的位置,找不到则返回-1. 数组下标1开始
int findX(int a[],int n,int x){
int left = 1, right = n;
int pos = -1; //存储x所在的下标,找不到则pos=-1
while(left<=right){//二分还未结束,可以二分
int mid = (left+right)/2;
if(a[mid]>x){
right = mid-1;
}
else if(a[mid]<x){
left = mid+1;
}
else{ //找到a[mid]==x, x下标就是mid
pos = mid;
break;
}
}
return pos; //返回x的下标
}
int a[110],n,x;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>x;
cout<<findX(a,n,x);
return 0;
}

二分答案:
#include <iostream>
using namespace std;
const int N = 1e6+10;
//n:树的总数。 m:小码君需要的木材, ans:刀片高度
long long a[N],n,m;

//判断刀片在h米处,得到的木材是否满足>=m
bool isOk(int h){//h:刀片高度
long long sum=0;
//遍历n棵树
for(int i=1;i<=n;i++){
sum+=(a[i]>=h?a[i]-h:0);
}
return sum>=m; //能够满足小码君需要的木材总数
}

int main(){
long long ans,maxntree=0;//保存当前满足条件下的刀片高度
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]; //输入第i棵树的高度
maxntree = maxntree>a[i]?maxntree:a[i];
}
//刀片高度在: [0, maxntree]
int l = 0, r = maxntree;
while(l<=r){
int mid = (l+r)/2;
//判断mid是否满足砍树>=m条件
if(isOk(mid)){//满足条件,
ans = mid; //
l = mid+1; //刀片需要往上抬
}
else{//刀片需要往下降
r = mid-1;
}
}
cout<<ans;
return 0;
}

Day04: 栈和队列。 经典入土名言 "程序 = 算法+数据结构"
数据结构是个好东西, 老师的理解 - 计算机组织和管理数据的内存模型。 变量, 数组, 结构体对象, 栈, 队列, 图, 二叉树等都属于"数据结构", 俗称存储数据的"容器"。

栈: 先进后出, 后进先出的一种内存模型, 本质上还是"容器", 只不过存储数据有点特殊。 直接看成"弹夹"即可,先装载的子弹后打出去, 后装载的子弹先打出去。
stack<T> st; T就是泛型, 表示栈存储数据的类型。

st.size()
st.pop();
st.top();
st.empty();

while(!st.empty()){ //只要栈不为空
cout<<st.top(); //就打印栈顶元素
st.pop(); //栈顶元素出栈
}

队列: 先进先出,后进后出中的一种内存模型, 本质还是容器。 "无法理解的话建议会议做核酸时候排队的情景"。 队列最大的好处就是维护了顺序, 在bfs()广度搜索中经常使用。
queue<T> q;
q.size();
q.front();
q.pop();
q.empty();
q.clear();
while(!q.empty()){ //只要队列不为空
cout<<q.front(); //就打印队头元素
q.pop(); //队头出队。 如果忘记写 - 直接GG，自己思考为神马。
}

一般数组可以模拟栈和队列。参考如下
#include <iostream>
using namespace std;
int stack[110], top=0; //创建了一个栈
//入栈
void push(int x){
top++;
stack[top] = x; //入栈
}
//出栈
void pop(){
if(top>=1){ //不为空栈,才能出栈
top--;
}
}

//获取栈顶元素
int getTop(){
return stack[top];
}

//判断栈是否为空
bool empty(){
return top==0;
}

//返回栈中元素个数, size()长度
int size(){
return top-0; //栈中元素的个数
}

//写一个函数: 显示栈中所有的元素
//写一个函数:输出栈中的内容
void show(){
//i=1: 栈顶元素的指针
for(int i=1;i<=top;i++){
cout<<stack[i]<<" ";
}
cout<<endl;
}

int main(){
int n; cin>>n;
while(n--){//执行n次操作
string op; cin>>op;
if(op=="push"){
int val; cin>>val;
push(val); //入栈之后立马显示栈中的元素
show();
}
else{
//pop()
if(empty()){
cout<<"pop fail"<<endl;
}
else{
pop();
}
}
}

return 0;

}

数组模拟队列:
#include <bits/stdc++.h>
using namespace std;
//溢出。 head或者tail一旦上移,空间无法再次利用
string q[110];
int head=0,tail=0;
//把参数x入队到队列q中
void push(string x){
q[tail++]=x;//tail:指向了队尾
}
void pop(){
if(head<tail){//队列不为空
head++; //head指向下一个元素
}
}
int size(){
return tail - head;
}
bool empty(){
//return size()0;
return headtail;
}
string front(){
return q[head]; //head:指向队头元素的下标
}
string back(){
return q[tail-1]; //返回队尾元素, tail-1是因为tail++, 后加加
}

int main(){
while(true){
string s; cin>>s;
if(s=="end") {//若队伍中还有群众，则一次性被叫走去办理业务。
while(!empty()){
cout<<front()<<" ";
pop();
}
break;
}
if(s[0]'1'){
push(s);
}
else if(s"out"){
int k; cin>>k;
if(!empty()){ //有k个人去办理业务
while(!empty() && k>0){
cout<<front()<<" ";
pop();
k--;
}
}
else{
cout<<"empty";
}
cout<<endl;
}
}

return  0;

}

Day05: 递归和递推

递归是一种思想 - 就是函数自己调用自己。
无限递归 - 没有递归出口。 多米诺骨牌 其中的骨牌数量无限,一直倒下去怎么办?
有限递归 - 有递归出口。 从前有座山,山里有个庙, 庙里有个老和尚,老和尚给小和尚讲故事, 讲: 从前有座山.......; (TM的, 这个老和尚是第100个了吗? 拜拜不听了, 开始回退99个，98个....1个)

                      递进阶段。 --- 解决问题

递归的核心 -
回溯阶段。--- 解决问题。 极难, ，老师唯一觉得有深度的编程内容。
(回溯和DP能通透, 水平绝对牛逼, 基本上代码没啥难度了)

参考只有递进阶段:
#include <bits/stdc++.h>
using namespace std;
//函数: 返回第n个月的兔子数量
int getRabbit(int n){
if(n1 || n2) return 1;
//从第三个月开始
return getRabbit(n-1) + getRabbit(n-2);
}
int main(){
int n; cin>>n;
cout<<getRabbit(n);
return 0;
}

参考回溯:

#include <bits/stdc++.h>
using namespace std;
//输出n的二进制
void change(int n){
if(n0) return; //商为0, 除尽了, 没必要继续
change(n/2); //n/20, 就开始回溯
cout<<n%2; //这里就是: 回溯。但分支的回溯还好, 多分支的回溯直接暴毙。
}
int main(){
/*
18 18%2 = 0 9 change(18) [ cout<<18%2; ?] 还没得及执行 0
9 9%2 = 1 4 change(9) [ cout<<9%2; ?] 还没得及执行 1
4 4%2 = 0 2 change(4) [ cout<<4%2; ?] 还没得及执行 0
2 2%2 = 0 1 change(2) [ cout<<2%2; ?] 还没得及执行 0
1 1%2 = 1 0 change(1) [ cout<<1%2; ?] 还没得及执行 1
change(0)
*/
int n; cin>>n;
change(n);
return 0;
}

Day06: DFS()深度搜索, 核心思想 - 能进则进, 不能进则退。 走迷宫, 涉及到递归。
#include <bits/stdc++.h>
using namespace std;
/*
1.定义地图. 定义方向,n,m地图的宽度,高
*/
char mp[49][49];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//右,下,左,上
int n,m; //地图的行数和列数
//定义函数当前的位置是否越界
bool isIn(int x,int y){//在地图内部true, 否则返回false
return x>=1 && x<=n && y>=1 && y<=m;
}
//标记地图上的当前点之前是否被访问过,如果被访问过,下次就不能再次访问
bool vis[49][49];
bool flag=false; //找到了终点flag置为true

//从当前点(x,y)开始搜索
void dfs(int x,int y){
if(xn && ym){ //(x,y)就是终点
flag = true; //找到了终点就结束返回
return;
}
vis[x][y] = true; //将点(x,y)标记为已经搜索过
for(int i=0;i<4;i++){ //(x,y)右,下,左,上四个方向展开搜索
int xx = x+dir[i][0]; //(xx,yy)从坐标(x,y)过来的
int yy = y+dir[i][1];
if(isIn(xx,yy) && vis[xx][yy]==0 && mp[xx][yy]!='#'){
//(xx,yy)位置可以抵达
dfs(xx,yy);
}
}
}

int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
dfs(1,1);//执行完: 说明地图已经每个角落都已经搜索完
if(flag) cout<<"YES";
else
cout<<"NO";
return 0;
}

dfs()的核心: 每一步都可以作为当前的位置试一下能否行走, 具有相同的问题子结构。 一般dfs()效率比较低， 极其消耗内存开销,。

Day07: BFS()广度搜索。 核心思想 - 借助队列维护访问的顺序, 起点入队， 起点像是波纹的中心点，层层扩散搜索, 广度简单的原因 - 比较直接。
#include <iostream>
#include <queue>
using namespace std;
int a[101][101], vis[101][101];
int n,dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
//每个位置: row,col,val
struct point{
int x,y;
};
queue<point> q;

int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
//起点入队
point start = {1,1};
q.push(start);
vis[start.x][start.y] = 1; //标记起点已经被搜索过
while(!q.empty()){
point temp = q.front();
cout<<a[temp.x][temp.y]<<" ";
q.pop();
//temp:上下左右四个方向搜索
for(int i=0;i<4;i++){
int xx = temp.x+dir[i][0];
int yy = temp.y+dir[i][1];
//(xx,yy)能否到达
if(xx>=1 && xx<=n && yy>=1 && yy<=n
&& vis[xx][yy]==0){
vis[xx][yy] = 1;
q.push({xx,yy});
}
}
}

return 0;

}

Day08: 链表 - list
不想多说, 结构体指针要会用. -->符号。

数据域:
指针域:

struct node{
char val; //数据域:
node *next; //指针域: 后驱
node *pre; //指针域: 前驱
}

单链表: 添加，删除，插入，修改节点的操作。
双链表: 添加，删除，插入，修改节点的操作。
//删除step节点
point[point[step].pre].next = point[step].next;
point[point[step].next].pre = point[step].pre;

a.next.next.next.next 像是链式编程, 下一个的下一个的下一个的下一个的节点。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
//创建节点
struct node{
int ch,pre,next; //ch:当前节点的编号。 pre:顺时针上一个节点的编号
};
node point[N]; //结构体数组
int main(){
//初始化: flag 为0表示逆时针, 为1表示顺时针
int head = 1,n,m,sum=1,flag=0;//n:人数。 m:数到第m个人,转变方向
cin>>n>>m;
//n个数字插入链表
for(int i=1;i<=n;i++){
point[i].ch = i;
point[i].next = i+1;
point[i].pre = i-1;
}
point[n].next = 1; //n:最后节点, 1:第一个节点
point[1].pre = n; //构成环

//从头开始游戏
int step = head;		//step:移动的节点
for(int i=1;i<n;i++){	//1 ~ n-1轮游戏 
	if(flag==0){		//逆时针 
		for(int j=1;j<=m-1;j++){//前m-1个人 
			step = point[step].next;
		}
		//删除第m个人
		point[point[step].pre].next = point[step].next;
		point[point[step].next].pre = point[step].pre;
		flag = 1;		//逆时针 --> 顺时针 
		step = point[step].pre;//step的左边第一个人开始下一轮游戏 
	}
	else{				//顺时针 
		for(int j=1;j<=m-1;j++){
			step = point[step].pre;
		}
		//删除step节点
		point[point[step].pre].next = point[step].next;
		point[point[step].next].pre = point[step].pre;
		flag = 0;
		step = point[step].next;	//step:的右边第一人开始下一轮游戏 
	} 
} 
 cout<<point[step].ch; 
return 0;

}

Day09: 二叉树和图论
二叉树: 先序(根左右)，中序(左根右),后序(左右根) 遍历。
n0 = n1+1;
叶子节点 - 度为0的节点。 n0
度为2的节点: n1
根据前序，中序； 确定二叉树, 进而计算后序。
二叉树的创建， 遍历。
二叉树: 孩子表示法,父亲表示法

节点的度:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+9;
vector<int> ve[maxn]; //ve[1]:表示父节点1所有的子节点存在ve[1]中
//v[1] = {2,3}: 节点2,3都是节点1的孩子
int main(){
int n; cin>>n; //n:节点的个数
for(int i=1;i<n;i++){//输入n-1个父子关系
int fa,son;
cin>>fa>>son;
ve[fa].push_back(son); //son就是fa的子节点, fa可能多个子节点
}
int q; cin>>q;
while(q--){ //q次询问
int x;cin>>x; //x输出节点x的度
//x节点有几个孩子,x的度就是几
cout<<ve[x].size()<<endl;
}
return 0;
}

二叉树后序遍历:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],n; //数组a存储的是二叉树的每个节点编号,n:节点个数

//先序遍历: 根左右
void preorder(int x){ //x:当前访问的节点的编号
cout<<a[x]<<" "; //先访问根节点
if(2x<=n) preorder(2x); //左孩子
if(2x+1<=n) preorder(2x+1); //右孩子
}
//中序遍历: 左根右
void inorder(int x){ //x:当前访问的节点
if(2x<=n) inorder(2x); //左子树
cout<<a[x]<<" "; //输出根节点
if(2x+1<=n) inorder(2x+1); //再访问问右子树
}
//后续遍历: 左右根
void postorder(int x){
if(2x<=n) postorder(2x); //如果有左子树,递归处理左子树
if(2x+1<=n) postorder(2x+1); //如果有右子树,递归处理右子树
cout << a[x]<<" "; //这里是回溯算法
}

int main(){
cin>>n;
//输入n个节点的编号
for(int i=1;i<=n;i++){
cin>>a[i];
}
//调用preorder(1)
//preorder(1);
//inorder(1); //中序遍历了二叉树
postorder(1); //后序遍历: 传入的是根节点1
return 0;
}

图论: 重点。

1.分类 - 有向图，无向图，带权图
2.分类 - 稀疏图，稠密图

图其实就是一种网状的数据结构， 参考地铁交通图

图的连接关系: 1. 邻接矩阵。 2. vector<int>
图的搜索: dfs()和bfs()搜索
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> v[N];
int vis[N]; //标记当前的点是否被搜索过
int n,m,a,b; //n个顶点, m条边; 判断a能否到达b

int main(){
cin>>n>>m>>a>>b; //输入顶点个数和边数
//输入m条边的信息
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
v[x].push_back(y); //有向图, 边: x-->y 顶点x指向y
}
//开始判断a能否到达b
queue<int> q; //广度搜索
q.push(a); //a是搜索的起点
vis[a] = 1; //标记a已经被搜索过了

while(!q.empty()){
	int t = q.front();	
	if(t==b){//能走到b 
		cout<<"Yes";
		return 0; 
	}
	q.pop();
	//t是队头元素,看t能否到达哪些顶点, 将能到达的顶点入队 
	for(int i=0;i<v[t].size();i++){
		int x = v[t][i];	//x就是顶点t能到达的所有点 
		if(vis[x]==0){		//如果顶点x没有被访问过,就需要入队 
			q.push(x);
			vis[x] = 1;		//标记顶点x,已经搜索的状态 
		}
	}
} 
cout<<"No"; 
return 0;

}

//邻接矩阵存储图
#include <bits/stdc++.h>
using namespace std;
//邻接矩阵描述有向图
int mp[101][101]; //二维数组作为邻接矩阵,存储有向图的指向关系
int n,m; //n:顶点的个数, m:边数
int main(){
cin>>n>>m;
//输入m条边
for(int i=1;i<=m;i++){
int sx,sy; //sx-->sy: 顶点sx指向顶点sy
cin>>sx>>sy; //输入顶点的指向
mp[sx][sy] = 1; //顶点的指向关系
}
//输出邻接矩阵即可
for(int i=1;i<=n;i++){//矩阵有多少个顶点,就有多少行
for(int j=1;j<=n;j++){
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
/*
输入
5 6
1 2
3 2
2 4
5 4
4 1
4 3
输出
0 1 0 0 0
0 0 0 1 0
0 1 0 0 0
1 0 1 0 0
0 0 0 1 0
*/