皮蛋秀柚秋

分类

笔记(31) 读书笔记(2) 题解(1)

/ 注册

全部文章（共33篇）

堆

堆的定义及性质堆是一棵完全二叉树，以大顶堆为例，每个节点的值不小于其左右孩子节点。用数组实现堆，下标为i的节点其左右孩子节点的小标为2i和2i+1。相关操作建堆：从最后一个有孩子的节点开始，逆序枚举，每个节点向下调整插入元素：将新增元素插入堆尾，向上调整删除（堆顶）元素：将最后一个元素覆盖...

堆

2020-01-10

0 807

Trie树(前缀树、字典树)

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。一、Trie树的介绍一个例子，如下图所示：上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳...

字典树

2019-12-25

0 1744

拓扑排序

思路：判定所给图是否为有向无环图。(即是否能够进行拓扑排序) DFS、BFS实现广度优先遍历 class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prere...

拓扑排序

2019-12-24

0 585

并查集

并查集是一种维护集合的数据结构。它支持以下两个操作： 1.合并两个集合 2.判断两个元素是否在一个集合初始化：一开始，每个元素都是一个独立的集合查找：规定一个集合中只有一个根节点。查找操作就是反复寻找根节点，直至找到根节点。合并：一般给出两个元素，要求把这两个元素所在集合合并。具体实现上先判断两个...

并查集

2019-12-24

0 599

栈与队列

单调栈理解：栈内元素的大小按照它们在栈内的位置，满足一定的单调性。这种数据结构通常运用在一维数组上。如果遇到问题与前后元素之间的大小关系有联系的话(如leetcode 84/85/42)，我们可以试图用单调栈来解决。使用单调栈，关键在于每个元素出栈的意义。由于每个元素都出栈入栈一次，时间复杂度O(...

单调栈

2019-11-30

0 657

KMP与有限状态自动机

- 关于字符串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] 成立 ...

kmp DFA

2019-11-22

0 693

动态规划

华为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...

dp

2019-11-19

0 822

C++ STL

1.c++ STL中set与unordered_set区别和map与unordered_map区别类似：set基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。unordered_set基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗...

2019-11-17

0 1059

算法解题笔记

1.两数之和问题描述：在一个数列中找出两个数使他们的和等于给定的值target。除暴力外的一般思路：1.哈希表法。遍历数列，对每个元素a[i]判定target-a[i]是否在哈希表中。O(n)2.双指针法。要先将该数列排序。O(n)拓展：三数之和求a[i]+a[j]+a[k]==target。一...

2019-11-13

0 641

全排列

整数1~n的全排列 #include<bits/stdc++.h> using namespace std; int per[n+1]; bool hashTable[n+1]; int n; void fun(...

DFS

2019-09-07

0 546