语录心得

• 你想过一个平凡又无趣的生活太容易了。你可以不读书，不冒险，不外出，不写作，不折腾…但是，人生最后悔的事情就是：我本可以。

算法心得

输入输出技巧

输入输出重定向

#include<stdio.h>
freopen("data.in","r",stdin);  
freopen("data.out","w",stdout);

四舍五入问题

浮点数转整形–向下取整,直接忽略掉小数部分

double p1=3.5;
int p2=(int)(p1+0.5); //四舍五入

浮点数保留n位小数,四舍五入

double p1=3.14159;//保留n=4位小数
p1=p1*pow(10,4);
long long p2=(long long)(p1+0.5);
p1 =p2/pow(10,4);
printf("%.4llf",p1);

注意

• pow()函数使用的时候转换为整形也需要+0.5再取整避免浮点误差

数组初始化问题

void *memset( void *buffer, int ch, size_t count );

• 该函数只能赋值是按照字节依次赋值的,所以对于int数组只能赋值0和-1

类型的转换

stringstream类

• 引入#include<sstream>
• 主要方法:
  • str():返回一个当前流的字符串对象的副本
  • str(""):流清空的内存
  • clear():清空该流的错误标记

#include <string>
#include <sstream>
#include <iostream>
using namespace std;
int main()
{stringstream sstream;string str1,str2="10086";int number1= 1000,number2;sstream << number1;sstream >> str1;cout<<str;sstream.clear();sstream.str("");sstream << str2;sstream >> number2;cout<<number2;return 0;
}

运算符重载

• 在自定义的结构体类型的时候,会进行比较操作
• 定义方式–重载小于 < 运算符
  • 结构体内容定义
  • 结构体外部定义

#include<iostream>
#include<queue>
#include<string>
using namespace std;struct Node{int number;string name;Node(int x,string y){number=x;name=y;}
};
//重载运算符 
//函数参数  const Node &n1 或者 Node n1 
bool operator < (const Node &n1,const Node &n2){if(n1.name<n2.name){return true;}else {return false;}
}
int main(){Node n1(1,"hello"),n2(2,"world");cout<<(n1<n2); return 0;
}

算法设计工具STL

STL的组成

• 容器(container)
• 算法(algorithm)
• 迭代器(iterator)

算法

• 引用:#include<algorithm>

排序

• sort(<firstindex>,<lastindex>,<comparator>)
• 排序范围：[firstindex,lastindex),前闭后开
• 比较函数：
  • 递增排序：less<T>() —默认；
  • 递减排序：greater<T>;
  • 自定义函数

#include<algorithm>
#include<vector>
#include<string> 
#include<iostream>
using namespace std;
struct Stu{int number;string name;Stu(int number1,string name1){number=number1;name=name1;}
};
//运算符重载
bool operator < (const Stu &s1,const Stu &s2){return s1.number<s2.number;
}int main(){//数组使用char str[]={'4','2','3','1'};for(int i=0;i<sizeof(str)/sizeof(str[0]);i++){cout<<str[i]<<" ";}sort(str,str+sizeof(str)/sizeof(str[0]),less<char>());cout<<endl;for(int i=0;i<sizeof(str)/sizeof(str[0]);i++){cout<<str[i]<<" ";}cout<<endl;//vector使用vector<Stu> s;s.push_back(Stu(2,"number2"));s.push_back(Stu(1,"number1"));s.push_back(Stu(3,"number3"));for(int i=0;i<s.size();i++){cout<<s[i].number<<":"<<s[i].name<<endl; }sort(s.begin(),s.end());for(int i=0;i<s.size();i++){cout<<s[i].number<<":"<<s[i].name<<endl; }return 0;
}

比较

• 比较数字:max(),min(),abs()–浮点数取绝对值是使用math.h库里的fabs()
• 比较容器:max_element(),min_elemet()–返回的是迭代器,求最大值需要使用*获得其值

其他

• 交换值:swap()

• 翻转容器:reverse()

#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){int a=-1,b=2;cout<<max(a,b);cout<<abs(a);double c=-3.14;cout<<fabs(c);swap(a,b);cout<<a<<" "<<b;vector<int> s;s.push_back(2);s.push_back(1);s.push_back(3);cout<<*max_element(s.begin(),s.end(),less<int>());//使用*获取其最大值for(int i=0;i<s.size();i++){cout<<s[i]<<" ";}reverse(s.begin(),s.end());for(int i=0;i<s.size();i++){cout<<s[i]<<" ";}return 0;
}

迭代器

• iterator/const_iterator:(常量)正向迭代器

vector<int> vec;
vec.push_back(1);vec.push_back(2);vec.push_back(3);vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();++it){printf("%d ",*it); //输出:1 2 3
}

• reverse_iterator/const_iterator:(常量)反向迭代器

vector<int> vec;
vec.push_back(1);vec.push_back(2);vec.push_back(3);vector<int>::reverse_iterator it;
for(it=vec.rbegin();it!=vec.rend();++it){printf("%d ",*it);//输出:3 2 1
}

顺序容器

向量容器vector

• 引用:include<vector>
• 主要函数:
  • empty():判断当前向量容器是否为空
  • size():返回当前向量容器中实际元素个数
  • [index]:返回指定下标的元素
  • push_back( 元素):在当前向量容器尾部添加一个元素
  • pop_back():删除当前容器中最末的一个元素
  • clear():删除容器中所有元素
  • insert(迭代器,元素):在迭代器位置的前面插入元素
  • erase(迭代器1[,迭代器2]):删除向量容器中某个迭代器或迭代器区间的元素
  • front():获取当前向量容器的第一个元素
  • back():获取当前向量容器的最后一个元素
  • begin():返回正向迭代器iterator或const_iterator,引用容器中的第一个元素
  • end():返回正向迭代器iterator或const_iterator,引用容器的中最后一个元素后一个位置
  • rbegin():返回正向迭代器reverse_iterator或reverse-const_iterator,引用容器中的最后一个元素
  • rend():返回正向迭代器reverse_iterator或reverse_const_iterator,引用容器的中第一个元素前一个位置

//定义
vector<int> v1; //定义元素为int的向量v1
vectot<int> v2(10); //初始大小为10个int元素
vector<int> v3(10,0); //指定v3的10个初始元素的初值为0

字符串容器string

• 引用:#include<string>
• 主要函数:
  • empty():判断当前字符串是否为空串
  • size():返回当前字符串中实际字符个数
  • lengh():返回当前字符串中实际字符的个数
  • [index]:返回当前字符串位于index位置的字符
  • compare(str):返回当前字符串与字符串str的比较结果
  • append(str):末尾追加一个字符串
  • insert(index,str):在指定索引位置index处插入字符串str
  • find(str,pos):在指定pos位置处开始查找字符串str的第一个位置，找不到返回string:npos(即-1)
  • replace(index,length,str):在起始与index的length个字符用字符串str替换
  • substr(index[,lenth]):截取字串
  • clear():删除当前字符串中的所有字符
  • erase(index,length):删除当前字符串从index开始的length个字符

//定义
char cstr[]="hello world";
string s1(cstr);
string s2(s1);

双端队列容器deque

• 引用:#include<deque>
• 主要函数:
  • empty():判断空队
  • size():元素个数
  • front():返回第一个元素
  • back():返回最后一个元素
  • push_front(elem):头部插入
  • push_back(elem):尾部插入
  • pop_front():头部删除
  • pop_back():尾部删除
  • at(index):返回一个引用，指向位置index上的元素
  • begin():返回正向迭代器iterator或const_iterator,引用容器中的第一个元素
  • end():返回正向迭代器iterator或const_iterator,引用容器的中最后一个元素后一个位置
  • rbegin():返回正向迭代器reverse_iterator或reverse-const_iterator,引用容器中的最后一个元素
  • rend():返回正向迭代器reverse_iterator或reverse_const_iterator,引用容器的中第一个元素前一个位置

链表容器list

• 引用#include<list>
• 主要函数:
  • empty():判断空链表
  • size():元素个数
  • front():返回第一个元素
  • back():返回最后一个元素
  • push_front(elem):头部插入
  • push_back(elem):尾部插入
  • pop_front():头部删除
  • pop_back():尾部删除
  • sort():对链表容器中的元素排序
  • insert(迭代器,元素):在迭代器所指的元素前插入元素
  • begin():返回正向迭代器iterator或const_iterator,引用容器中的第一个元素
  • end():返回正向迭代器iterator或const_iterator,引用容器的中最后一个元素后一个位置
  • rbegin():返回正向迭代器reverse_iterator或reverse-const_iterator,引用容器中的最后一个元素
  • rend():返回正向迭代器reverse_iterator或reverse_const_iterator,引用容器的中第一个元素前一个位置

关联容器

集合容器set

• 引用:#include<set>

• 主要函数:

  • empty():判断是否为空
  • size():元素个数
  • insert(key):插入key元素
  • find(key):返回key元素的迭代器,没有的key元素,返回end()值
  • clear():删除所有元素
  • erase(key):删除等于key值的元素
  • begin():返回正向迭代器iterator或const_iterator,引用容器中的第一个元素
  • end():返回正向迭代器iterator或const_iterator,引用容器的中最后一个元素后一个位置
  • rbegin():返回正向迭代器reverse_iterator或reverse-const_iterator,引用容器中的最后一个元素
  • rend():返回正向迭代器reverse_iterator或reverse_const_iterator,引用容器的中第一个元素前一个位置

映射容器map

• 引用:#include<map>

• 主要函数:

  • empty():判断是否为空
  • size():元素个数
  • [key]:返回key元素的引用,若没有key,则以该key作为关键字进行插入
  • insert(pair<key,value>):插入<key,value>键值对
  • clear():删除所有元素
  • erase(key):删除键等于key值的元素对
  • find(key):返回key元素的迭代器,没有的key元素,返回end()值
  • begin():返回正向迭代器iterator或const_iterator,引用容器中的第一个元素
  • end():返回正向迭代器iterator或const_iterator,引用容器的中最后一个元素后一个位置
  • rbegin():返回正向迭代器reverse_iterator或reverse-const_iterator,引用容器中的最后一个元素
  • rend():返回正向迭代器reverse_iterator或reverse_const_iterator,引用容器的中第一个元素前一个位置

#include<map>
#include<cstdio>
using namespace std;
int main(){map<char,int> mymap;mymap.insert(pair<char,int>('a',1));mymap.insert(map<char,int>::value_type('b',2));mymap.insert(make_pair('a',1));mymap['d']=4;map<char,int>::iterator it;for(it=mymap.begin();it!=mymap.end();++it){printf("[%c,%d]",it->first,it->second);}return 0;
}
//pair类型的使用
pair<T1, T2> p1;           //创建一个空的pair对象
pair<T1, T2> p1(v1, v2);   //创建一个pair对象，其中first成员初始化为v1，second成员初始化为v2
make_pair(v1, v2);         // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1.first;                  // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

适配器容器

栈容器stack

• 引用:#include<stack>

• 主要方法：

  • empty():判断栈是否为空
  • size():栈容器中元素个数
  • push(elem):元素进栈
  • top():返回栈顶元素
  • pop():出栈

队列容器queue

• 引用#include<queue>
• 主要方法：
  • empty():判断栈是否为空
  • size():栈容器中元素个数
  • push(elem):元素进栈
  • pop():出栈
  • front():队头元素
  • back():队尾元素

优先队列priority queue

• 引用:#include<queue>
• 定义:priority_queue<Type,Container,Functional>
  • 自己定义的类型,不使用function,还是老老实实的的运算符重载吧
  • Type:数据类型
  • Container:容器类型(数组实现的容器,因为优先队列的本质是堆!!)
  • Functional:比较方式(传入基本数据类型的时候,默认为大顶堆)
• 主要方法:
  • empty():判断优先队列是否为空
  • pop():删除堆顶的第一个元素
  • push():加入一个元素
  • size():返回优先队列中拥有的元素个数
  • top():返回优先队列中拥有最高优先级的元素
• 使用:

#include<iostream>
#include<queue>
#include<string>
using namespace std;struct Node{int number;string name;
};
//重载运算符 
bool operator < (const Node &n1,const Node &n2){if(n1.number>n2.number||(n1.number==n2.number&&n1.name>n2.name)){return true;}else {return false;}
}
int main(){//基本类型//priority_queue<int,vector<int>,less<int> > a;priority_queue<int> a;//默认大顶堆//priority_queue<int,vector<int>,greater<int> > b;a.push(2);a.push(4);a.push(3);while(!a.empty()){cout<<a.top()<<" ";a.pop();}cout<<endl;//自定义类型priority_queue<Node> c;Node n1,n2,n3;n1.number=2;n1.name="hello";n2.number=1;n2.name="hello";n3.number=2;n3.name="bye";c.push(n1);c.push(n2);c.push(n3);while(!c.empty()){cout<<c.top().number<<c.top().name<<" ";c.pop();}return 0;
}

• 运算符重载

  • 结构体内部重载–运算符重载+友元

    struct fruit{string name;double price;friend bool operator < (fruit f1,fruit f2){return f1.price<f2.price; //相当于less,大顶堆}
    }
    

  • 结构体外部重载

    struct fruit{string name;double price;
    }
    bool operator < (fruit f1,fruit f2){return f1.price<f2.price; 
    }

  • 注意问题:上例中函数的参数const fruit &f1或者 fruit f1都可以

排序

桶排序法

优点:时间复杂度低

缺点:当排序的数的范围较大时,会浪费很大的资源空间;有些情况下(如小数),不能将所有的情况例举出来

//桶排序 
#include<iostream> 
#include<cstring>
using namespace std;
//对范围在0-1000的数据进行排序
int main(){int a[1001]; 
//函数声明:void *memset(void *str, int c, size_t n)memset(a,0,sizeof(a));int n;//需要排序的数据的个数 cin>>n; for(int i=0,t;i<n;i++){cin>>t;a[t]++;}for(int i=0;i<1001;i++){for(int j=0;j<a[i];j++)cout<<i<<" ";}return 0;
} 

冒泡排序法

优点:能基本弥补桶排序法的缺点

缺点:时间复杂度较高O(N^2)

//冒泡排序 
#include<iostream> 
#include<cstring>
using namespace std;int main(){int a[1001]; memset(a,0,sizeof(a));int n;//需要排序的数据的个数 cin>>n; for(int i=0,t;i<n;i++){cin>>a[i]; }for(int i=0,t;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(a[j+1]<a[j]){t=a[j+1];a[j+1]=a[j];a[j]=t;}}	}for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
} 

快速排序法

优点:平均时间复杂度NlogN相对于冒泡排序降低了很多

缺点:编写起来还是有点费时间

//快速排序法 
#include<iostream> 
#include<cstring>
using namespace std;int a[1001],n;
void quicksort(int left,int right){int i,j,temp,t;if(left>=right)return;temp=a[left];i=left;j=right;/*注意事项: 1.使左边的数小与temp,右边的数大于temp:在左右两边的while语句中使用的是小于等于和大于等于 2.基准数复位的时候,保证a[left]<a[i]:先进行右边的移动,在进行左边的移动 */while(i!=j){while(a[j]>=temp&&i<j)j--;while(a[i]<=temp&&i<j)i++;if(i<j){t=a[i];a[i]=a[j];a[j]=t;}}a[left]=a[i];a[i]=temp;quicksort(left,i-1);quicksort(i+1,right);return ;
} 
int main(){memset(a,0,sizeof(a));cin>>n; for(int i=0,t;i<n;i++){cin>>a[i]; }quicksort(0,n-1);for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
} 

---

练习:前k高频元素–桶排序

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

• 示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

• 示例 2:

输入: nums = [1], k = 1
输出: [1]

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
//桶排序方法
class Solution {public int[] topKFrequent(int[] nums, int k) {List<Integer> res=new ArrayList();HashMap<Integer,Integer> map=new HashMap();for(int num :nums){if(map.containsKey(num)){map.put(num,map.get(num)+1);}else{map.put(num,1);}}List<Integer>[] list=new List[nums.length+1];for(int key:map.keySet()){int i=map.get(key);if(list[i]==null){list[i]=new ArrayList();}list[i].add(key);}for(int i=list.length-1;i>=0&&res.size()<k;i--){if(list[i]==null) continue;res.addAll(list[i]);}int [] reslut=new int[res.size()];for(int i=0;i<res.size();i++){reslut[i]=res.get(i);}return reslut;}
}

栈,队列,链表

队列

FIFO–先进先出原则

//数据结构类型
struct queue
{int data[1001];//队列的主体int head;//队首(记录队首位)int tail;//队尾(记录队尾的下一位)
};
//STL中队列容器
#include<queue>
#include<iostream>
using namespace std;
int main(){queue<int> que;//元素入队que.push(1);que.push(2);que.push(3);//队头元素cout<<que.front();//队尾元素cout<<que.back();//元素的个数coutque.size();//判断队列容器是否为空(实质:head==tail)while(!que.empty()){//元素出队que.pop();}return 0;
}

栈

FILO–先进后出原则

//数据结构
struct stack
{int data[1001];//栈的主体int top;//栈顶元素
}
//STL中栈容器
#include<stack>
using namespace std;
int main(){stack<int> st;//入栈st.push(1);st.push(2);st.push(3);//栈顶元素st.top();//判断栈容器是否为空(实质:top==-1)while(!st.empty()){//出栈    st.pop();}return 0;
}

练习:纸牌游戏-小猫钓鱼

#include<iostream>
#include<cstring>using namespace std;struct stack{int data[10];int top=-1;};struct queue{int data[1000];int head=0;int tail=0;};int main(){freopen("../in.txt","r",stdin);struct queue q1,q2;struct stack s;for(int i=0;i<6;i++){cin>>q1.data[q1.tail++];}for(int i=0;i<6;i++){cin>>q2.data[q2.tail++];}int book[10];memset(book,0,sizeof(book));int temp;while(q1.head<q1.tail&&q2.head<q2.tail){//q1出队temp=q1.data[q1.head++];if(book[temp]==0){book[temp]=1;s.data[++s.top]=temp;}else{book[temp]=0;q1.data[q1.tail++]=temp;while(s.data[s.top]!=temp){int t=s.data[s.top--];q1.data[q1.tail++]=t;book[t]=0;}q1.data[q1.tail++]=s.data[s.top--];}if(q1.tail==q1.head) break;//q2出队temp=q2.data[q2.head++];if(book[temp]==0){book[temp]=1;s.data[++s.top]=temp;}else{book[temp]=0;q2.data[q2.tail++]=temp;while(s.data[s.top]!=temp){int t=s.data[s.top--];q2.data[q2.tail++]=t;book[t]=0;}q2.data[q2.tail++]=s.data[s.top--];}}if(q2.head==q2.tail){cout<<"q1的牌是";while(q1.head<q1.tail){cout<<q1.data[q1.head++];}}else{cout<<"q2的牌是:";while(q2.head<q2.tail){cout<<q2.data[q2.head++];}}cout<<"桌面上的牌为:";while(s.top>=0){cout<<s.data[s.top--];}return 0;}

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;int main(){freopen("../in.txt","r",stdin);queue<int> q1,q2;int temp;for(int i=0;i<6;i++){cin>>temp;q1.push(temp);}for(int i=0;i<6;i++){cin>>temp;q2.push(temp);}stack<int> s;int book[10];memset(book,0,sizeof(book));while(!q1.empty()&&!q2.empty()){//q1出牌temp=q1.front();q1.pop();if(book[temp]==0){s.push(temp);book[temp]=1;}else{book[temp]=0;q1.push(temp);while(s.top()!=temp){q1.push(s.top());book[s.top()]=0;s.pop();}q1.push(temp);s.pop();}if(q1.empty()) break;//q2出牌temp=q2.front();q2.pop();if(book[temp]==0){s.push(temp);book[temp]=1;}else{book[temp]=0;q2.push(temp);while(s.top()!=temp){q2.push(s.top());book[s.top()]=0;s.pop();}q2.push(temp);s.pop();}}if(q1.empty()){cout<<"q2的牌为:";while(!q2.empty()){cout<<q2.front()<<" ";q2.pop();}}else{cout<<"q1的牌为:";while(!q1.empty()){cout<<q1.front()<<" ";q1.pop();}}cout<<"桌面上的牌为:";while(!s.empty()){cout<<s.top()<<" ";s.pop();}return 0;
}

链表

优点:方便插入和删除

#include<iostream>
#include<cstdlib>
using namespace std;struct node
{	int data;struct node *next;
};
int main(){struct node *head,*p,*q,*t;head=NULL;int temp;for(int i=0;i<5;i++){cin>>temp;p=(struct node *)malloc(sizeof(struct node));p->data=temp;p->next=NULL;if(head==NULL){head=p;q=head;}else{q->next=p;q=p;}}//插入数据cin>>temp;t=head;while(t!=NULL){if(t->next==NULL||t->next->data>temp){p=(struct node *)malloc(sizeof(struct node));p->data=temp;p->next=t->next;t->next=p;break;}t=t->next;}t=head;while(t!=NULL){cout<<(t->data);t=t->next;}return 0;}  

模拟链表

使用两个数组,分别记录数据和下一个数据存放的位置

#include<iostream>
using namespace std;int main(){int len;cin>>len;int data[101],right[101];for(int i=0;i<len;i++){cin>>data[i];if(i!=len-1){right[i]=i+1;}else{right[i]=-1;}}   //插入一个数cin>>data[++len];int t=0;while(t!=-1){if(data[right[t]]>data[len]){right[len]=right[t];right[t]=len;break;}t=right[t];}t=0;while(t!=-1){cout<<data[t]<<" ";t=right[t];}return 0;
}

搜索

枚举

填数游戏 xxx+xxx=xxx

 #include<iostream>#include<cstring>using namespace std;int main(){//使用book[10]作标记,确保9个数各不相同 int a[10],book[10],total=0;for(a[1]=1;a[1]<=9;a[1]++)for(a[2]=1;a[2]<=9;a[2]++)for(a[3]=1;a[3]<=9;a[3]++)for(a[4]=1;a[4]<=9;a[4]++)for(a[5]=1;a[5]<=9;a[5]++)for(a[6]=1;a[6]<=9;a[6]++)for(a[7]=1;a[7]<=9;a[7]++)for(a[8]=1;a[8]<=9;a[8]++)for(a[9]=1;a[9]<=9;a[9]++){memset(book,0,sizeof(book));for(int i=1;i<=9;i++){book[a[i]]=1;}for(int i=1;i<=9;i++)if(book[i]==1)book[0]++;if(book[0]!=9) break;if(((a[1]+a[4])*100+(a[2]+a[5])*10+a[3]+a[6])==a[7]*100+a[8]*10+a[9]){for(int i=1;i<=9;i++)cout<<a[i]<<" ";total++;cout<<endl;} 		}cout<<total;return 0;} 

火柴棍等式

#include<iostream>
#include<cstring>
using namespace std;int f[10]={6,2,5,5,4,5,6,3,7,6};
int fun(int number){int num=0;while(number/10!=0){num+=f[number%10];number/=10;}num+=f[number];return num;
}
int main(){int n,sum=0;cin>>n;for(int i=0;i<=1111;i++)for(int j=0;j<=1111;j++){int k=i+j;if(fun(i)+fun(j)+fun(k)==n-4){cout<<i<<"+"<<j<<"="<<k<<endl;sum++;}}	cout<<sum;	return 0;
}

深度优先搜索

/*
dfs模型:
void dfs(int step){判断边界;for(int i=1;i<=n;i++){尝试每一种可能;继续下一步: dfs(step+1);}返回;
}
*/

数的全排列

#include<iostream>
#include<cstring>
using namespace std;int a[10],book[10],total=0; void dfs(int step){//边界判断 if(step==10){if(((a[1]+a[4])*100+(a[2]+a[5])*10+a[3]+a[6])==a[7]*100+a[8]*10+a[9]){for(int i=1;i<10;i++)cout<<a[i]<<" ";cout<<endl;total++; }return ;}for(int i=1;i<10;i++){if(book[i]==0){a[step]=i;book[i]=1;dfs(step+1);book[i]=0;}}return;
}
int main(){memset(book,0,sizeof(book));dfs(1);cout<<total/2; return 0;
} 

广度优先搜索

解救小哈

#include<queue>
#include<iostream>
#include<cstring> 
#include<cstdio>
using namespace std;typedef struct {int x;int y;int s;	
} Node;
int main(){queue<Node> que;int a[51][51],book[51][51];memset(book,0,sizeof(book));memset(a,0,sizeof(a));int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];} }int startx,starty,endx,endy;cin>>startx>>starty>>endx>>endy;Node node;node.x=startx;node.y=starty;node.s=0;int flag=0;que.push(node);int tx,ty;while(!que.empty()){for(int k=0;k<=3;k++){tx=que.front().x+next[k][0];ty=que.front().y+next[k][1];if(tx<1||ty<1||tx>n||ty>m){continue;}if(a[tx][ty]==0&&book[tx][ty]==0){book[tx][ty]=1;node.x=tx;node.y=ty;node.s=que.front().s+1;que.push(node);}if(tx==endx&&ty==endy){flag==1;break;}	}if(flag==1){break;}que.pop();}cout<<que.back().s;return 0;
}

炸弹人

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char a[50][50];
int book[50][50];typedef struct{int x;int y;
} Node;
int findBoom(int x,int y){if(a[x][y]=='#'||a[x][y]=='G'){cout<<"wrong!"<<x<<" "<<y;return 0;}int count=0,tx=x,ty=y;while(a[--tx][ty]!='#'){if(a[tx][ty]=='G')count++;}tx=x,ty=y;while(a[tx++][ty]!='#'){if(a[tx][ty]=='G')count++;}tx=x,ty=y;while(a[tx][--ty]!='#'){if(a[tx][ty]=='G')count++;}tx=x,ty=y;while(a[tx][++ty]!='#'){if(a[tx][ty]=='G')count++;}return count; 
}
int main(){freopen("input.txt","r",stdin);int maxBoom=0;queue<Node> que;memset(a,'#',sizeof(a));memset(book,0,sizeof(book));int m,n,startx,starty;cin>>m>>n>>startx>>starty;for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}Node node;node.x=startx;node.y=starty;book[startx][starty]=1;que.push(node);int tx,ty;int flagx,flagy;while(!que.empty()){int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};for(int k=0;k<=3;k++){tx=que.front().x+next[k][0];ty=que.front().y+next[k][1];if(a[tx][ty]=='G'||a[tx][ty]=='#')continue;if(book[tx][ty]==0&&a[tx][ty]=='.'){node.x=tx;node.y=ty;que.push(node);book[tx][ty]=1;}}if(maxBoom<findBoom(que.front().x,que.front().y)){maxBoom=findBoom(que.front().x,que.front().y);flagx=que.front().x;flagy=que.front().y;}que.pop();	}cout<<maxBoom<<endl;cout<<flagx<<" "<<flagy;return 0;
}
输入:
13 13 3 3
#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############
输出:
10
7 11

图的遍历

深搜和广搜

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;int a[101][101],n,book[101],sum=0;//图的遍历:深度优先遍历
void dfs(int cur){cout<<cur<<" ";sum++;if(sum==n)return ;for(int i=1;i<=n;i++){if(a[cur][i]==1&&book[i]==0){book[i]=1;dfs(i);}}	return ;
} 
int main(){freopen("input.txt","r",stdin);memset(a,999,sizeof(a));memset(book,0,sizeof(book));int m;cin>>n>>m;for(int i=0;i<m;i++){int j,k;cin>>j>>k;a[j][k]=1;a[k][j]=1;}for(int i=1;i<=n;i++){a[i][i]=0;}book[1]=1;dfs(1);return 0;
}

图的广度优先遍历

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;int a[101][101],n,book[101];//图的遍历:广度优先遍历int main(){freopen("input.txt","r",stdin);memset(a,999,sizeof(a));memset(book,0,sizeof(book));int m;cin>>n>>m;for(int i=0;i<m;i++){int j,k;cin>>j>>k;a[j][k]=1;a[k][j]=1;}for(int i=1;i<=n;i++){a[i][i]=0;}int que[101],head=1,tail=1;que[tail]=1;tail++;book[1]=1;while(head!=tail){int temp=que[head];head++;cout<<temp<<" ";for(int i=1;i<=n;i++){if(a[temp][i]==1&&book[i]==0){que[tail]=i;tail++;book[i]=1;}}}return 0;
}

图的深度优先遍历

城市地图

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,dis[101][101],book[101];
int mindis=9999,nowdis=0;void dfs(int cur){if(nowdis>mindis){return;}else if(cur==n){mindis=nowdis;return ;}for(int i=1;i<=n;i++){if(book[i]==0&&dis[cur][i]!=9999&&i!=cur){nowdis+=dis[cur][i];book[i]=1;dfs(i);book[i]=0;nowdis-=dis[cur][i];}}return;
}
int main(){freopen("input.txt","r",stdin);cin>>n>>m;memset(book,0,sizeof(book));memset(dis,9999,sizeof(dis));for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;dis[x][y]=z;}for(int i=1;i<=n;i++){dis[i][i]=0;}dfs(1);cout<<mindis;return 0;
}

图的广度优先遍历

最小转机

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;typedef struct{int number;int s;
}Node;int main(){freopen("input.txt","r",stdin);int n,m,x,y;cin>>n>>m>>x>>y;int book[n+1],a[n+1][n+1];memset(book,0,sizeof(book));memset(a,-1,sizeof(a));for(int i=0;i<m;i++){int j,k;cin>>j>>k;a[j][k]=1;a[k][j]=1;}for(int i=0;i<=n;i++){a[i][i]=0;}queue<Node> que;Node node;node.number=x;node.s=0; que.push(node);book[x]=1;int flag=0;while(!que.empty()&&flag==0){Node temp=que.front();for(int i=1;i<=n;i++){if(book[i]==0&&a[temp.number][i]==1){node.number=i;node.s=temp.s+1;que.push(node);book[i]=1;if(i==y){ flag=1;break;} }}que.pop();}cout<<que.back().s;return 0;
}

最短路径

Floyd-Warshall算法

• 时间复杂度O(N^3)
• 任意两点之间的最短路径
• 思想:比较任意两点允许通个更多的点来更新两点的最短路径

//核心代码:
for(int k=1;k<=n;k++){ //允许任意两点之间可以通过点1~点K时,两点之间的最短路径for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(e[i][j]>e[i][k]+e[k][j]){e[i][j]=e[i][k]+e[k][j];}}}
}  

Dijkstra算法

• 时间复杂度O(N^2)
• 指定一个点到其余各个顶点的最短路径
• 思想:每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展(松弛),最终得到源点到其余所有点的最短路径

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 99999
using namespace std;int array[15][15],book[15],dis[15];
void dfs(int step,int total){if(step==total){return ;}int min=inf,temp=-1;for(int i=1;i<=total;i++){if(book[i]==0&&dis[i]<min){min=dis[i];temp=i;}}//无法到达if(temp=-1){return ;}book[temp]=1;for(int i=1;i<=total;i++){if(book[i]==0&&dis[temp]+array[temp][i]<dis[i]){dis[i]=dis[temp]+array[temp][i];}}dfs(step+1,total);
}int main(){freopen("input.txt","r",stdin);int n,m;cin>>n>>m;memset(book,0,sizeof(book));memset(dis,0,sizeof(dis));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) array[i][j]=0;else array[i][j]=inf;}}int x,y,z;for(int i=1;i<=m;i++){cin>>x>>y>>z;array[x][y]=z;}for(int i=1;i<=n;i++){dis[i]=array[1][i];}book[1]=1;dfs(1,n);	for(int i=1;i<=n;i++){if(dis[i]==inf){cout<<"x"<<" ";}else{cout<<dis[i]<<" ";} }return 0;
} 

Bellman-Ford算法

• 时间复杂度:O(MN)
• 优点:可以解决负权

#include<iostream>
#include<cstdio>
#define inf 999999using namespace std;int main(){freopen("input.txt","r",stdin);int dis[10],u[10],v[10],w[10],m,n;cin>>n>>m;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}for(int i=1;i<=n;i++){dis[i]=inf;}dis[1]=0;//最短路径中最多含有n-1for(int i=1;i<=n-1;i++){int flag=0;for(int j=1;j<=m;j++){if(dis[u[j]]+w[j]<dis[v[j]]){dis[v[j]]=dis[u[j]]+w[j];flag=1;}}if(flag==0)break;}int flag=0;for(int i=1;i<=m;i++){if(dis[u[i]]+w[i]<dis[v[i]]){flag=1;}}if(flag=1){cout<<"含有负权回路"<<endl;} for(int i=1;i<=n;i++){cout<<dis[i]<<" ";}return 0;
}

Bellman-Ford队列优化

• 时间复杂度:最坏的情况为O(NM)
• 本质:用队列来记录每一次松弛成功后的点,在下一个周期中(bellman-ford中的k++),只对以松弛过的点为起点的边才继续操作,所以判断总的边数会小于等于M,同时队列中没有元素,也会停止执行,则遍历周期数小于等于N-1
• 困难点:需要使用邻接表存储,自己还不是很熟练

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define inf 999999using namespace std;int main(){//初始化 freopen("input.txt","r",stdin);int n,m,i,j,k;cin>>n>>m;//邻接表存储 int u[m+1],v[m+1],w[m+1],first[n+1],second[m+1],dis[n+1],book[n+1];memset(first,-1,sizeof(first));memset(book,0,sizeof(book));for(i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];second[i]=first[u[i]];first[u[i]]=i;}for(i=1;i<=n;i++){dis[i]=inf;}queue<int> que;que.push(1);book[1]=1;dis[1]=0;while(!que.empty()){int temp=first[que.front()];while(temp!=-1){if(dis[v[temp]]>dis[u[temp]]+w[temp]){dis[v[temp]]=dis[u[temp]]+w[temp];if(book[v[temp]]==0){que.push(v[temp]);book[v[temp]]=1;}}temp=second[temp];}book[temp]=0;que.pop();}for(i=1;i<=n;i++){cout<<dis[i]<<" ";}return 0;
}

树

二叉树

• 满二叉树:深度为h且有2^h-1个节点的二叉树

• 完全二叉树:高度为h,除h层以外,其他各层的节点数达到最大个数,第h层从右往左连续缺若干个节点的二叉树

• 二叉树性质:

  • 父节点编号为k,左边儿子编号为2k,右儿子编号为2k+1;
  • 子节点编号为k,父亲节点编号为k/2(自动向下取整)

堆–优先队列

优先队列

• 支持插入元素,寻找最大最小值元素的数据结构称为优先队列

#include<iostream>
#include<string>
#include<algorithm> 
using namespace std;
//建立大顶堆 
int array[101],n; //n记录大小//向下调整:堆创建,堆排序 
void siftdown(int i){int flag=0,t;while(i*2<=n&&flag==0){if(array[i*2]>array[i]){t=i*2;}else{t=i;}if(i*2<=n+1&&array[i*2+1]>array[t]){t=2*i+1;}if(t!=i){swap(array[i],array[t]);i=t;}else{flag=1;}}
} 
//向上调整:堆创建(不建议使用,时间复杂度更高) 
void siftup(int i){int flag=0;while(flag==0&&i>1){if(array[i/2]<array[i]){swap(array[2*i],array[i]);i=i/2;}else{flag=1;}}
}
void creat(){for(int i=n/2;i>=1;i--){siftdown(i);} return ;
} 
int  deletemin(){swap(array[1],array[n]);n--;siftdown(1);return array[n+1];
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>array[i];}creat();for(int i=0;i<=n;i++){cout<<deletemin()<<" ";}return 0;
}

并查集

• 作用:找图中连通区间数

#include<iostream>using namespace std;
int array[1000],n,m,sum=0; int getf(int v){if(array[v]==v){return v;}else{array[v]=getf(array[v]);return array[v];}
}
void merge(int v,int u){int t1,t2;t1=getf(v);t2=getf(u);if(t1!=t2){array[t2]=t1;} return ;
}
int main(){int i,x,y;cin>>n>>m;for(i=1;i<=n;i++){f[i]=i;}for(i=1;i<=;i++){cin>>x>>y;merge(x,y); }for(i=1;i<=n;i++){if(array[i]=i){sum++;}} cout<<sum;	
}

最小生成树

• 问题:有n座城市,m条路,以及每条路过路的代价k,需要找出最小的总代价使这写城市连通

Kruskal算法

解法1:快排+并查

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;struct Edge{int u;int v;int w;
};
bool operator < (Edge e1,Edge e2){if(e1.w<e2.w){return true;}else{return false;}
}int n,m,book[100];
Edge edges[100];int getf(int v){if(book[v]!=v){book[v]=getf(book[v]);}return book[v];}
void merge(int u,int v){int t1,t2;t1=getf(u);t2=getf(v);if(t2!=t1){book[t2]=t1;} return ;
}
int main(){freopen("input.txt","r",stdin);int i,count=0;cin>>n>>m;for(i=1;i<=m;i++){cin>>edges[i].u>>edges[i].v>>edges[i].w;}		sort(edges+1,edges+1+m);for(i=1;i<=n;i++){book[i]=i;}for(i=1;i<=m;i++){if(getf(edges[i].u)!=getf(edges[i].v)){merge(edges[i].u,edges[i].v);count+=edges[i].w;cout<<edges[i].u<<edges[i].v<<edges[i].w<<endl;} } cout<<count<<endl;return 0;
} 

Prim算法

最短边+松弛(可以采用堆排序降低时间复杂度)

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 9999
using namespace std;
//最小生成树 
int array[15][15],dis[15],book[15],n,m,count=0;void dfs(int step){//最多n-1条边 if(step>n-1){return ; }//找最小disint min=inf,index=-1;for(int i=1;i<=n;i++){if(book[i]==0&&dis[i]<min){min=dis[i];index=i;} } if(index==-1){cout<<"无法生成树"; return ;}else{book[index]=1;count+=dis[index];} //松弛for(int i=1;i<=n;i++){if(dis[i]>dis[index]+array[index][i]&&book[i]==0){dis[i]=dis[index]+array[index][i];}} dfs(step+1);
} 
int main(){freopen("input.txt","r",stdin);int i,j,x,y;cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=n;j++){array[i][j]=inf;if(i==j){array[i][j]=0;}}}	 for(i=1;i<=m;i++){cin>>x>>y>>j;array[x][y]=j;array[y][x]=j;}memset(book,0,sizeof(book));//以点1开始生成树for(i=1;i<=n;i++){dis[i]=array[1][i];}book[1]=1;dfs(1);cout<<count<<endl;return 0;
} 

图的割点

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,array[15][15],root;
int num[15],low[15],flag[15],index=0;
//num[]指时间戳,low[]指不经过父顶点能回到的最小时间戳void dfs(int cur,int father){int child=0,i;index++;num[cur]=index;low[cur]=index;for(i=1;i<=n;i++){if(array[cur][i]==1){if(num[i]==0){child++;dfs(i,cur);low[cur]=min(low[cur],low[i]);if(cur!=root&&low[i]>=num[cur]){//可以回到父亲节点flag[cur]=1;}if(cur==root&&child==2){flag[cur]=1;}}else if(i!=father){low[cur]=min(low[cur],num[i]);}	}}return ;
}
int main(){freopen("input.txt","r",stdin);int i,j,x,y;cin>>n>>m;memset(flag,0,sizeof(flag));memset(array,0,sizeof(array));for(i=1;i<=m;i++){cin>>x>>y;array[x][y]=1;array[y][x]=1;}root=1;dfs(1,root);for(i=1;i<=n;i++){if(flag[i]==1){cout<<i<<" ";}}return 0;
} 

图的割边

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,array[15][15],root;
int num[15],low[15],index=0;
//num[]指时间戳,low[]指不经过父顶点能回到的最小时间戳
void dfs(int cur,int father){int child=0,i;index++;num[cur]=index;low[cur]=index;for(i=1;i<=n;i++){if(array[cur][i]==1){if(num[i]==0){child++;dfs(i,cur);low[cur]=min(low[cur],low[i]);if(cur!=root&&low[i]>num[cur]){//同时不能回到父亲节点cout<<cur<<"-"<<i<<endl;}}else if(i!=father){low[cur]=min(low[cur],num[i]);}	}}return ;
}
int main(){freopen("input.txt","r",stdin);int i,j,x,y;cin>>n>>m;memset(array,0,sizeof(array));for(i=1;i<=m;i++){cin>>x>>y;array[x][y]=1;array[y][x]=1;}root=1;dfs(1,root);return 0;
} 

二分图最大匹配

#include<iostream>
#include<cstring>
#include<cstdio>
//二分图最大匹配
using namespace std;
/*
注明:本实验只能解决男女之间最大配对问题,同性恋构成的就不是二分图了
*/int n,m,count=0,relationship[15][15],love[15],match[15];
//n表示总人数,m表示恋爱关系的数量,count表示配对人数 bool dfs(int man){for(int woman=1;woman<=n;woman++){ //如果该男生和该女生有暧昧关系且女生没有分手经历 if(relationship[man][woman]==1&&love[woman]==0){//该男生对女生表白 love[woman]=1; /*情况1:女生还没有男朋友情况2:和男朋友和平分手(但是要确保男朋友能找到新的女朋友哦) */ if(match[woman]==0||dfs(match[woman])){match[man]=woman;match[woman]=man;//女生答应和男生在一起 return true; }else{//女生拒接了男生 (这个地方是空语句,剧情需要) }}}//还是单身吧,单身多爽啊 return false; 
} int main(){
//	freopen("input.txt","r",stdin);cin>>n>>m;memset(relationship,0,sizeof(relationship));memset(match,0,sizeof(match));int x,y;for(int i=1;i<=m;i++){cin>>x>>y;relationship[x][y]=1;relationship[y][x]=1; }for(int man=1;man<=n;man++){//所有女生喝下忘情水--所有的恋爱经历清零 memset(love,0,sizeof(love)); if(dfs(man)) count++;}	cout<<count;return 0;
}