第十篇博客——图论 并查集 图论中我认为最好玩的算法就是并查集了，基本上常用的并查集算法如下：  初始化 void init(int n){ for(int i=0;i<=n;i++){ fa[i]=i;//每个节点的父亲都是自己 he[i]=0;//每个节点的高度是0 } } 查找并压缩路径（这样可以更好地获得菊花图） int find(int x){ if(x!=fa[x]) fa[x]=find(fa[x]); //路径压缩，一般的方法只是返回fa[x]，这里还压缩了路径，让树不至于退化成链表 else return fa[x]; } 合并 //合并要保证矮树作为高树的子树 voi...

第九篇博客——数据结构二 二叉树 一般地，二叉树的定义： struct TreeNode{ char data; TreeNode *lc; TreeNode *rc; TreeNode(char c):data(c),lc(NULL),rc(NULL){} }; //构造函数不可以少 深度优先遍历方法有前序、中序和后序之分。其中知道中序遍历次序和前/后序遍历次序是可以还原出二叉树的形状的。一般构建二叉树使用x序和#符号来建立。 例题1：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中...

第八篇博客——搜索 宽度搜索 BFS BFS的核心的数据结构是队列，访问完当前的数据(myqueue.front())后将其子状态压入队列中，每次访问都是访问队列头部的数据。下面是模版。 bool visit[MAXN]; struct status{ int n,k; status(int n,int k):n(n),k(k){} }; int BFS(int n,int k){ queue<int> myq; myq.push(status(n,0)); visit[n]=true; while(!myq.empty()){ status cur=myq.front(); my...

第七篇博客——递归与分治 递归策略 汉诺塔 在普通的汉诺塔中func(n)=2*func(n-1)+1，但是如果只允许一次只能移到相邻的杆子上只能func(n)=3*func(n-1)+1 分治法 将问题分解成数个小问题，分别解决多个小问题然后再将其相加起来就可以获得总共的结果。 斐波那契数列 int fibonacci(int n){ if(n==1||n==0) return 0; else return fibonacci(n-1)+fibonacci(n-2); }

第六篇博客——贪心策略 简单贪心 鸡兔同笼 🤔如果已知动物的头和腿的数量，如果要求最多动物数量的时候就优先考虑脚少的🐔，如果要求最少数量的时候优先考虑脚多的🐰。 FatMouse’ s Trade 在遇到类似于购物问题时，优先购买性价比高的东西，等到买不下来了再选择买部分（如果可以的话，实际上这也是能够简单贪心的前提——能够部分购买）。 Senior’ s Gun 题目大意：一个人有若干支枪，面对若干个怪物。枪有攻击力，怪物有防御力，一把枪只能最多干掉一只怪物，杀死怪物后，这个人可以获得攻击力-防御力的奖赏，请问最多的奖赏是多少（不必干掉所有怪物）。 🤔既然一支枪只能干掉一只怪物，所以...

进制转换 不用字符串模拟的情况 #include<iostream> #include<cstdio> #include<vector> using namespace std; int main(){ unsigned int n; while (cin>>n) { vector<int> arr; while(n){ arr.push_back(n%2); n/=2; } for(int i=arr.size()-1;i>=0;i--){ cout<<arr[i]; } cout<<endl; } r...

vector的一些补充 #include <iostream> #include <vector> using namespace std; int main(int argc, const char * argv[]) { // insert code here... vector<int> myvector; for(int i=0;i<10;i++){ myvector.push_back(i); } vector<int>::iterator it; cout<<"初始情况的向量"<<en...

加油

有的城市，我这辈子都不想来了。

希望能够在腊月十五之前把这本书干完！！😊

给昨天补打卡😂

字符串 字符串是一个我大一大二就没学好的知识点，现在要补回来，有的知识点还不是特别清楚，比如操作啥的，后续要增添操作。 字符串的基本知识 构造函数 字符串有几种常见的构造函数，包括默认构造函数和复制构造函数。  默认构造函数string str; 一般构造方法string str("abc")和拷贝构造string str(str1).   除此之外还有一些不常见但是可能会很有用的版本.  将构造的对象初始化为s的前n个字符，s不够n个时将相邻的内存单元的内容当作s的一部分继续复制： string(const char *s, size_type n, const Allo...