• 近期将进行后台系统升级,如有访问不畅,请稍后再试!
  • 极客文库-知识库上线!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 每日更新优质编程文章!
  • 更多功能模块开发中。。。

每天更新原创技术文章及教程,欢迎关注!

数据结构笔记总结(10.4)基于size的优化

数据结构笔记总结(10.4)基于size的优化
并查集的优化前两节我们实现了两种并查集,第一版的并查集其实就是使用数组来模拟每个数据所属的集合是谁,第二版虽然依然使用数组来进行数据关系的存储,但整体思路上和第一版的并查集是截然不同的,让数据形成了一种比较奇怪的树结构,或者说是森林结构。改进并查集这里我们先回忆一下第二版的 Quick Union 的过程,首先执行 union(0,1),结果如下下……继续阅读 »

Geekerstar 9个月前 (05-20) 304浏览 0评论0个赞

数据结构笔记总结(10.3)Quick Union

数据结构笔记总结(10.3)Quick Union
Quick Union上一节我们实现了并查集的一种思路,使用数组进行模拟得到一种结果,叫做 Quick Find,对于查找这种操作是非常快的。标准情况下并查集的实现是通过 Quick Union 这种实现思路。实现思路将每一个元素看做是一个节点,节点之间相连接形成一棵树的结构,不过这棵树结构和之前所学的树结构都是不同的,并查集中的树结构是孩子指向父亲……继续阅读 »

Geekerstar 9个月前 (05-20) 394浏览 0评论0个赞

数据结构笔记总结(10.2)Quick Find

数据结构笔记总结(10.2)Quick Find
并查集的基本数据表示在并查集内部我们可以直接给每个数据做一个编号,这里 0 到 9 就表示 10 个不同的数据当然这是一种抽象的表示,10 个编号可能是 10 个人或 10 辆车,但在并查集内部我们只存 0 到 9 这 10 个编号,它表示 10 个具体的元素。对于每一个元素并查集存储的是一个我们可以称之为叫做它所属于的集合的 ID,比如编号为 0……继续阅读 »

Geekerstar 9个月前 (05-20) 342浏览 0评论0个赞

数据结构笔记总结(10.1)什么是并查集

数据结构笔记总结(10.1)什么是并查集
并查集(Union Find)我们之前学习的所有树结构都是由父亲指向孩子,但是并查集却是一种由孩子指向父亲的树结构这样一种数据结构,它可以非常高效的来解决连接问题(Connectivity Problem)如上这个图有非常多的点,每两个点之间有的有一个连接,有的没有连接,使用并查集就可以高效的回答这样一个问题:给出图中任意两点,问两点之间是否可以根据一……继续阅读 »

Geekerstar 9个月前 (05-20) 303浏览 0评论0个赞

数据结构笔记总结(9.7)更多和Trie字典树相关的话题

数据结构笔记总结(9.7)更多和Trie字典树相关的话题
Trie 的删除操作我们并没有实现 Trie 的删除操作,在大多数情况下比如竞赛面试使用 Trie 的时候基本上都不会涉及删除操作的。但是如果在实际应用中使用 Trie 的话,很多时候是要涉及删除操作的。比如我们做一个通讯录,使用 Trie 创建通讯录的话,我们将通讯录中的每一个人名当做单词插入到 Trie 中,在单词最后一个字母的位置存储相应的通讯录……继续阅读 »

Geekerstar 9个月前 (05-20) 259浏览 0评论0个赞

数据结构笔记总结(9.6)Trie字典树和字符串映射

数据结构笔记总结(9.6)Trie字典树和字符串映射
Trie 字典树和字符串映射前面实现的 Trie 都是把它当成一个字符串的集合来使用,主要在 Trie 中添加或查询一个单词是否存在。在查询方面上一小节通过一个 LeetCode 问题知道了还可以进行一定的字符串模式匹配,这一小节我们具体来看看当我们把 Trie 当成一个映射来使用的情况是怎样的?677. 键值映射实现一个 MapSum 类里的两个……继续阅读 »

Geekerstar 9个月前 (05-20) 343浏览 0评论0个赞

数据结构笔记总结(9.4)Trie字典树的前缀查询

数据结构笔记总结(9.4)Trie字典树的前缀查询
Trie 字典树的前缀查询Trie 中文名称叫“字典树”,字典树很好理解,它是一个树结构,存储的是一个个字符串。把它合在一起就像一个字典,同时它又叫前缀树,就是因为我们可以非常容易在 Trie 中搜索某个单词对应的前缀其实这种搜索非常简单,可以想象一下 Trie 的结构,从根节点开始,向下搜索的过程其实都是在搜索单词的前缀。比如我在查找 cat 的……继续阅读 »

Geekerstar 9个月前 (05-20) 461浏览 0评论0个赞

数据结构笔记总结(9.1)什么是Trie字典树

数据结构笔记总结(9.1)什么是Trie字典树
什么是 Trie这种数据结构和我们之前介绍的所有树结构都不同的一种树,之前介绍的所有树结构,无论是二分搜素树还是堆还是线段树都是二叉树,但是 Trie 是一个多叉树,下面和字典来做一下比较Trie 是怎么做到查询的时间复杂度和条目数无关而只和单词中有多少个字符相关的呢?之前我们在考察字符串、单词这样一个数据的时候,我们会把整个字符串看成一个整体。……继续阅读 »

Geekerstar 9个月前 (05-20) 352浏览 0评论0个赞

数据结构笔记总结(8.4)线段树中的区间查询

数据结构笔记总结(8.4)线段树中的区间查询
线段树中的区间查询比如我们要在这个线段树中查询[2,5]这个区间相应的信息,相当于是查询这个区间的和。从根节点开始出发在根节点包含了[0,7]区间的信息,显然我们要查询的是其子集,所以我们要向下去左右子树查找。由于我们要查询的[2,5]分别落在了左右子树,所以我们需要分别查询,如图接下来继续往下查询,如图所示,我们要查询的最终结果只需要获取图中两……继续阅读 »

Geekerstar 9个月前 (05-20) 322浏览 0评论0个赞

数据结构笔记总结(8.3)创建线段树

数据结构笔记总结(8.3)创建线段树
创建线段树我们已经了解了什么是线段树,并且想把线段树看成满的二叉树,这种情况下用数组就可以存储线段树。如果要考虑的区间有 n 个元素,数组开 4*n 的空间就可以承载整个线段树了,下面我们就具体的对这个 4*n 个空间里到底要存储什么才能构建线段树相应的逻辑进行介绍。比如我们处理求和这个线段树,也就是说我们线段树的目的是为了查询区间中的元素和的操作,……继续阅读 »

Geekerstar 9个月前 (05-20) 346浏览 0评论1个赞

数据结构笔记总结(8.2)线段树基础表示

数据结构笔记总结(8.2)线段树基础表示
线段树基础线段树不一定是一棵满的二叉树,也不是完全二叉树(从上往下码放,如果一排不够从下一排左边排起),但是线段树是平衡二叉树(对于整棵树来说,最大的深度和最小的深度之间的差最多只有可能为 1),堆也是平衡二叉树(优势是不会像二分搜素树一样退化成链表)。所以线段树依然可以用数组来表示,可以将其看做满二叉树,最后一层不存在的节点看成是空节点。下面思考一……继续阅读 »

Geekerstar 9个月前 (05-20) 229浏览 0评论0个赞

数据结构笔记总结(8.1)什么是线段树(区间数)

数据结构笔记总结(8.1)什么是线段树(区间数)
为什么要使用线段树(Segment Tree)最经典的问题:区间染色。现在进行很多的操作:从 4 到 9 这段绘制成橙色,从 7 到 15 这段墙绘制成绿色,原来橙色的部分被最近一次的绿色给覆盖住了。正是因为有这种覆盖情况让问题复杂了一些,继续对从 1 到 5 的这段墙绘制成蓝色,对从 6 到 12 这段墙绘制成红色。m 次操作后,我们可以看见多少种……继续阅读 »

Geekerstar 9个月前 (05-19) 364浏览 0评论0个赞

数据结构笔记总结(7.7)Leetcode上优先队列相关问题

数据结构笔记总结(7.7)Leetcode上优先队列相关问题
347. 前 K 个高频元素给定一个非空的整数数组,返回其中出现频率前 k 高的元素。例如,给定数组 [1,1,1,2,2,3] , 和 k = 2,返回 [1,2]。注意:你可以假设给定的 k 总是合理的,1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。代码演示使用我……继续阅读 »

Geekerstar 9个月前 (05-19) 321浏览 0评论0个赞

数据结构笔记总结(7.6)基于堆的优先队列

数据结构笔记总结(7.6)基于堆的优先队列
基于堆的优先队列之前我们已经实现了最大堆,对于优先队列其底层可以使用最大堆来实现,通过最大堆这种数据结构的底层去实现优先队列是及其容易的,近乎所有接口都可以直接复用来完成优先队列这种数据结构。代码演示我们复用队列的接口,创建一个新的 class,叫做 PriorityQueuepublic class PriorityQueue> imple……继续阅读 »

Geekerstar 9个月前 (05-19) 222浏览 0评论0个赞

数据结构笔记总结(7.4)从堆中取出元素和Sift Down

数据结构笔记总结(7.4)从堆中取出元素和Sift Down
从堆中取出元素我们之所以管它叫“最大堆”就是因为我们从堆中只取出堆顶的元素,也就是二叉树根节点所在的元素,这个元素也是堆中最大的元素,取出操作只能取出这个元素而不能取出其他的元素。那么这个过程怎么实现呢?将索引为 0 的元素拿出去之后,现在对于整个堆可以看成有两棵子树。将这两棵子树再融成堆比较复杂,所以在这里我们使用一个小技巧,小技巧就是我们把堆中……继续阅读 »

Geekerstar 9个月前 (05-19) 278浏览 0评论0个赞

数据结构笔记总结(7.3)向堆中添加元素和Sift Up

数据结构笔记总结(7.3)向堆中添加元素和Sift Up
向堆中添加元素这个过程从用户的角度看是添加元素,不过从堆的角度看涉及一个非常基础的内部操作,相应的英文叫 Sift up(堆中的元素上浮的过程),下面我们来看一下如果想向堆中添加元素应该怎么做。首先由于我们堆中的数据是使用数组排列的,添加元素相当于是在层序遍历最右端,也就是最下面一层的最后再添加一个元素。当然如果最下面一层已经没有位置再添加新的元素了……继续阅读 »

Geekerstar 9个月前 (05-19) 503浏览 0评论0个赞

数据结构笔记总结(7.2)堆的基础表示

数据结构笔记总结(7.2)堆的基础表示
堆的基本结构在计算机的世界中,通常 O(logn)时间复杂度几乎都和树这种数据结构有关。当然不一定我们要显式的构造一棵树,比如排序算法中归并排序、快速排序都是 O(nlogn)级别的,排序过程中没有使用树这种数据结构,但是这个递归的过程其实形成了一个隐形的递归树。二叉堆(Binary Heap)一个堆本身也是一棵树,堆也有很多种。我们主要学习使用二叉树……继续阅读 »

Geekerstar 9个月前 (05-19) 253浏览 0评论0个赞

数据结构笔记总结(7.1)什么是优先队列

数据结构笔记总结(7.1)什么是优先队列
树这种数据结构本身在计算机科学领域占有重要的地位,不仅仅是因为二分搜索树这样一种结构,而是树这种形状本身可以产生非得多的拓展。面对不同的问题的时候,我们可以稍微改变或限制树这种数据结构的性质,从而产生不同的数据结构,高效的解决不同的问题。堆和优先队列普通队列:先进先出;后进后出优先队列:出队顺序和入队顺序无关;和优先级相关具体应用:操作系统根……继续阅读 »

Geekerstar 9个月前 (05-19) 356浏览 0评论0个赞

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00