Freedom Coding

C++_STL vector初始化 vector<int> v;vector<int> v(10); 定义长度为10的数组vector<int> v(10,3); 定义长度为10的数组，并且每一个值都是3 获取数组长度 v.size() 判断数组是否为空 v.empty(); 清空 v.clear(); 获取首尾元素 v.front();v.end(); 添加/删除 v.push_back();v.pop_back(); 首尾迭代器 v.begin();v.end(); 遍历方式 vector<int> v;for(int i = 0;i < v.size();i++) cout << v[i] << " ";for(auto it = v.begin();i != v.end();i++) cout << *i << " ";for(auto it : v) cout << it ...

C++成长之旅 前提：万能头文件为什么我们需要万能头文件？ 万能头文件可以帮助我们不用像C语言一样挨个引入库 C++万能头文件的引入 Window: https://blog.csdn.net/weixin_52985599/article/details/112301569 MacOS: C++基础打印HelloWorld Hello，WorldC++代码 #include <bits/stdc++.h>using namespace std;int main(){ cout << "Hello,World" << endl; return 0; } 基本数据类型 数据类型 代码 整形 Int 长整形 Long 长长整形 long long 短整形 Short 字符型 Char 单精度浮点型 Float 双精度浮点型 Double 变量名 变量名必须以字母或下划线开头。 变量名可以包含字母、数字和下划线。 变量名 ...

BST二叉搜索树(BST)，也可以叫做二叉排序树 BST树始终满足四个要求 左结点的值小于父结点 右结点的值大于右结点 没有权值相同的结点 每一个结点的左右子树也满足二叉排序树 BST暴力搜索最坏的情况时间复杂度是O(n ^ 2) 接下来讲的主要是最普遍的二叉搜索树 初始化先定义一个全局遍历nnum代表每一个结点的下标 在开始之前我们需要为每一个结点定义属性 每一个结点需要值(val) 左孩子(ls) 右孩子(rs) 重复情况使用记录出现次数(cnt) 用来记录排名(siz) struct node{ int ls;int rs;int val;int cnt;int siz;}; 插入结点参数部分我们既然想要插入一定需要将跟结点传入 从根结点出发去查找合适的位置 接着传入插入的值 判断三种情况 插入的结点等于当前结点 插入结点大于当前结点 插入结点小于当前结点 完整代码 void add(int now,int v) { t[now].siz++; if(t[now].val == v) { t[now].c ...

本篇博客用来分享自定义方法实现某些功能，可以用来出题 同一棵树枝上的蚂蚱题目描述设有一个二叉树 我们想要在其中实现一个功能，他的目的是为了判断两个结点是否处于二叉树根节点的同一边(跟节点默认是1) 输入格式输入n，代表n组关系 接下来n + 1行，每一行输入两个数a，b 分别代表上一个结点的左右子结点 接着输入你想要判断的两个结点 输出格式如果处于同一侧，输出 Yes 否则输出 No 输入输出样例输入 #1 5 13 2 34 0 012 4 520 0 040 0 02 3 输出 #1 No 说明/提示解释：假如第一次输入两个数34，说明了1的左结点是3，右结点是4；第二次输入67代表2的左结点是6，右结点是7，如果输入左右结点都是0 和 0代表是根结点 数据规模与约定对于 100%100% 的数据，只需要保证1 <= n <= 100，0 < a,b < n AC模版 #include <bits/stdc++.h>using namespace std;struct node{ int le ...

Floyed(插点法) Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。 在开始之前我们需要对一些图进行分类 图按照权值可以分为有权和无权 什么是有无权？ 权值代表了图中任意两个结点之间的距离 无权说明两点之间的距离为1，而有权距离因题而议 按照方向可以定义为无向图和有向图 无向代表了从图上某一点到达另一点和往返到达距离都是相同的 而有向则恰恰相反，a -> b 和 b -> a之间的距离是不同的 优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单 缺点：时间复杂度比较高，不适合计算大量数据。 步骤 第一步首先我们需要对二维数组进行初始化 初始化的值为无穷代表任意两个点之间是无法到达的，需要特殊处理对角线上的值即g[i][i]为0，因为自己到自己之间没有距离 第二步根据输入的值，构建树的结构，将从a - > b即g[a][b]和g[b][a]进行填充二维数组 第三部参考大佬已经画好的 ...

Hash Hash(哈希)，是用来将很多数据分开来存储到数据容量小于本身的一种容器，可以达到减少时间的目的 当然Hash表我们可以通过数组来进行模拟 主要分为两种方法 拉链法 开放寻址法 拉链法拉链法顾名思义，我们在摆放数据的时候，会出现某两条数据或者更多数据位于同一位置的情况，我们可以在该位置上拉一条链，将这些数据进行捆绑形存储 初始化 N：往往是一个质数(数学推理出来的结论) e[N] 用来存储值，ne[N]用来存储链表中下一位，hs[N]哈希表 插入 插入的值很可能是负数，所以我们应该保证结果是正数 我们需要让x + N，但是这并不正确因为x的取最小值范围远小于N，所以我们应该先去对N进行取模，缩小一下N的范围接着再加上N，最后取模N，才能获取到插入位置的下标 (x % N + N) % N 后面的过程就是向链表头结点插入元素 查找 同理先找到x在哈希表中的下标，然后遍历链表，判断是否出现与x相同的情况，如果有，返回true，否则false #include <bits/stdc++.h>using namespace std;const int N = 100 ...

Map map是C++STL中提供的容器，由红黑树构成，我们可以通过map创建所谓的键值映射的功能 map的基本使用创建map map<int,int> maps; //数据类型自己定义 map中添加键值 maps[1] = 2; maps[2] = 3;maps["hello"] = 1; map中遵循初始化的时候前面的数据类型，后面的值遵循初始化后面的数据类型 map访问 //由于上面已经创建了几个案例，我们就对他们进行访问cout << maps[1] << endl; 通过键为1，去访问对应的valuecout << maps[2] << endl; // 3 map遍历 //通过迭代器进行访问for (auto it = mp.begin(); it != mp.end(); it++) { cout << it -> first << " " << it -> second << e ...

Trie树 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。 功能 Trie树主要使用来构建树形结构去存储字符串的每一位 方便我们后期对字符串进行查询 构建Trie树如何对字符串的每一位进行存储呢？ 我们可以使用二维数组son[N][26]来存储 N代表的是第N个结点 26代表的是N结点下有26个分支(因为都是单词，所以我们可以将结果映射到(0 - 25) son[N][26]代表的就是N结点的儿子结点 同时我们需要创建一个新的数组tail[N] 对字符串的尾部结点进行收集，方便我们对出现的单词个数进行统计 根结点的值默认设置为0 插入我们如何将一个字符串插入到Trie树中呢？ 我们可以对每一位进行遍历，判断这一位是否出现过 如果出现过了那么就接着判断下一个字符 如果没有出现过就进行插入，创建出一条新的分支 void insert() { int p = 0; // ...

图一分为二解决匹配问题

折半查找