问题描述 采样问题经常会涉及到，简单地，有如下形式： 1.从1000000份调查报告中抽1000份进行统计 2.从一本很厚的电话簿中抽1000人进行姓氏统计 3.从Google搜索"AI"的结果中抽100个进行分析 分析： 问题1我们很容易想到生成1至1000000的随机数，抽取1000个，用算法去重保证采样结果不重复即可。问题2与问题3的性质与问题1不同，由于数据规模N可能十分巨大，没有办法将其一次全部读入内存，所以存储所有数据再遍历一次来获取其规模这一做法不可取。 采样问题最重要的是保证公平，即对于总样本集合中的所有元素来说，每个元素需具有相等的概率被选择。这里，我们需...

堆的定义及性质 堆是一棵完全二叉树，以大顶堆为例，每个节点的值不小于其左右孩子节点。用数组实现堆，下标为i的节点其左右孩子节点的小标为2i和2i+1。 相关操作 建堆：从最后一个有孩子的节点开始，逆序枚举，每个节点向下调整 插入元素：将新增元素插入堆尾，向上调整 删除（堆顶）元素：将最后一个元素覆盖堆顶，从堆顶向下调整 #include <bits/stdc++.h> using namespace std; const int maxn = 100; // 堆的总容量 int n; // 堆内元素个数 vector<int>heap(100,0); // 以大顶...

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。 一、Trie树的介绍 一个例子，如下图所示：上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：1.根结点不包含字符，除根结点外每个结点包含一个字符。2.从根结点到某一个结点，路径上经过的字符连接起来，为该结点对应的字符串。3.每个结点的所有子节点包含的字符互不相同。通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。（或者是设置一...

思路：判定所给图是否为有向无环图。(即是否能够进行拓扑排序) DFS、BFS实现 广度优先遍历 class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { if(prerequisites.empty()) return true; // 采用邻接表法 vector<vector<int>>v(numCourses,vector<int>());...

并查集是一种维护集合的数据结构。它支持以下两个操作： 1.合并两个集合 2.判断两个元素是否在一个集合 初始化：一开始，每个元素都是一个独立的集合查找：规定一个集合中只有一个根节点。查找操作就是反复寻找根节点，直至找到根节点。合并：一般给出两个元素，要求把这两个元素所在集合合并。具体实现上先判断两个元素是否属于同一个集合，两个元素属于不同集合时才合并。(如给定元素A,B 合并操作Father[A]=B 或 Father[B]=A) 例题1 #include<bits/stdc++.h> using namespace std; #define N 100 int father[...

单调栈 理解：栈内元素的大小按照它们在栈内的位置，满足一定的单调性。这种数据结构通常运用在一维数组上。如果遇到问题与前后元素之间的大小关系有联系的话(如leetcode 84/85/42)，我们可以试图用单调栈来解决。使用单调栈，关键在于每个元素出栈的意义。由于每个元素都出栈入栈一次，时间复杂度O(n)。 例1： #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; vector<int>v(n); for(int i=0;i&lt...

- 关于字符串s的next数组的求解,next数组本质是当j+1位匹配失败时j应当回退到的位置1.初始化next数组，令j = next[0] = -1;2.令 i = 1，2，... len-1(len为s的长度)，对每个i,通过步骤3和4求解next[i]3.s[i] == s[j+1] 成立 或者令j = next[j],直至j回退至-14.如果s[i]==s[j+1], 则令next[i]=j+1,否则next[i] = j. KMP算法:判断pattern串是否为text串的子串。 求出pattern串的next数组 初始化j = -1,j表示pattern串中已经匹配的最后位。 ...

华为2021实习招聘笔试题 输入输出示例:5 5 103 5 4 2 34 5 3 4 34 3 5 3 22 5 3 3 55 3 4 4 1 输出：-1 （无论走哪条路线，都会超过可游玩时间t，所以输出-1） 5 5 303 5 4 2 34 5 3 4 34 3 5 3 22 5 3 3 55 3 4 4 1 输出：30 思路：此题是leetcode64题的改编题。https://leetcode-cn.com/problems/minimum-path-sum/ 最大（小）路径和本题在此基础上对最值进行了限制。第一想法，为每个位置维护一个列表，记录到达该位置的所有可能的取值（对本题来说...

1.c++ STL中set与unordered_set区别和map与unordered_map区别类似：set基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。unordered_set基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存，无自动排序功能。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。