SmallMatch

拓扑排序一、定义拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。 二、代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576class Solution {private: vector<vector<int>> edges; vector<int> visited; bool valid = true;public: void dfs(int u) { visited[u] = 1; for (int v: edges[u]) { if (visited[v] == 0) { dfs(v); if (!valid)  ...

线段树一、算法描述二、算法实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <bits/stdc++.h>using namespace std;/* 参数说明： tree下标为node的点应该存放arr[start:end]的点的总和*/void build_tree(vector<int> &tree, vector<int> &arr, int node, int start, int end){ if (start == end) tree[node] = arr[start]; else { int mid = (start + end) >> 1; // mid为向下取整，所有mid值为左边区间的右端点 int ...

并查集一、算法用途二、算法实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <cstdio>#define MAXN 5005int fa[MAXN], rank[MAXN];vector<int>fa1;inline void init(int n){ for (int i = 1; i <= n; ++i) { fa[i] = i;//父节点，或者说所在的集合的标志 //rank[i] = 1;记录深度 }}void init(n):fa1(n){ iota(fa1.begin(),fa1.end(),0);}int find(int x)//查询x所在哪个集合{ if (fa[x]==x) ret ...

字典树 一、类的实现请你实现 Trie 类： Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。 二、代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243class Trie{ private: vector<Trie*>children;//存他的下一个字母 bool isEnd; Trie *searchPrefix(string prefix)//搜索该前缀是否存在。 { Trie*node = t ...

二分查找模板123456789101112131415161718192021222324252627282930313233#include<iostearm>using namespace std;int main(){ vector<int> nums(n); int target; int left = 0 , right = n -1; //关于满足条件的左右区间变换问题 // 两端区间为左闭右闭 // 0 1 2 3 4 5 // 当 left = 0 , right = 5 ; while(left < right) { //mid = (0 + 5) / 2 = 2 , mid为 {0,1,2} , {3,4,5}; int mid = (left + mid)/2;// if (nums[mid] == target) return mid; if ( ...

嵌套查询 1.带有EXISTS谓词的子查询(重点难点)EXISTS代表存在量词，带有的EXISTS谓词的子查询不返回任何的数据，只产生逻辑值”true”或逻辑值”false” [1] 查询所有选修了1号课程的学生姓名 123456SELECT snameFROM studentWHERE EXISTS (SELECT * FROM sc WHERE sc.sno = student.sno and sc.cno = 1) 解读：先在student依次取每个元组的sno与sc表中的sno比较是否相等，在相等的同时，再检查这个元组的cno属性是否为1 [2]查询选修了全部课程的学生姓名 sql中没有表示全称量词的关键字，因此我们需要将全部课程中的全部转换成存在量词的形式 记：”选修课程 x “ 这一事件 为 P (\forall x)P \equiv \neg(\exists x(\neg P))转换后的问题转化为： 不存在1门课，没有被他选修 将此问题分为两部分： 1.有门课没有被他选修。 2.不存在满足1条件的课 123456789101112select ...

一、题目详情原题目链接 二、题目解读给定一组整数一共n个，同时这些整数中会重复存在找出某些数字，它在这组数据中重复的次数超过n/3个示例三 : [1,1,1,3,3,2,2,2]，n = 8, n/3 = 2 ，找出出现次数超过2的数字(8/3=2.67,向下取整为2)其中1出现次数3次，3出现次数2次，2出现次数3次满足条件的数字为1和3 三、解题 暴力解法 定义一个unordered_map集合，统计所有数字出现的个数统计完成后，遍历所有键，将值与n/3比较，取大于n/3的键，返回结果时间复杂度O(n),空间复杂度O(n) 12345678910111213141516class Solution{public: vector<int> majorityElement(vector<int> &nums) { vector<int> ans; int k = nums.size() / 3; unordered_map<int, int> map_; ...

第一篇测试文章 列表的使用 列表1 列表2 a 字符串ab 字符串b 列表3 一个链接我是一行斜体字 我是一行粗体字 12我是一行代码cout << "hello world" << end; 我是一行引用 \begin{equation} e=mc^2 \end{equation}123$$\begin{equation}e=mc^2\end{equation}$$

MarkDown公式格式