Geekerstar 极客笔记 《数据结构笔记总结》导航页 导航目录 第一章:数组 数据结构笔记总结(1.1)使用Java中的数组 数据结构笔记总结(1.2)二次封装属于我们自己的数组 数据结构笔记总结(1.3)向数组中添加元素 数据结构笔记总结(1.4)数组中查询元素和 …
Geekerstar 极客笔记 数据结构笔记总结(8.3)创建线段树 创建线段树 我们已经了解了什么是线段树,并且想把线段树看成满的二叉树,这种情况下用数组就可以存储线段树。 如果要考虑的区间有n个元素,数组开4*n的空间就可以承载整个线段树了,下面我们就具体的对这 …
Geekerstar 极客笔记 数据结构笔记总结(4.5)递归算法的调试 递归算法的调试 上一小节我们学习了递归实现的底层机理,这一小节我们来学习一下递归算法的调试。 其实这个方法也没有什么特别之处,就是打印输出,通过打印输出能清楚的看出我们程序是怎样一步一步获得最 …
Geekerstar 极客笔记 数据结构笔记总结(8.5)Leetcode上线段树相关的问题 303. 区域和检索 – 数组不可变 给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。 示例: 给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为sumRange() s …
Geekerstar 极客笔记 数据结构笔记总结(1.8)简单的时间复杂度分析 简单的时间复杂度分析 我们经常能看到用下面这些方式描述时间复杂度 什么是运行时间和输入数据之间的关系呢? 我们可以看一个非常简单的代码:下面是对一个数组中所有数字求和的代码,逻辑很简单。 通常这 …
Geekerstar 极客笔记 数据结构笔记总结(5.8)深入理解二分搜索树的前中后序遍历 再看二分搜索树的遍历 虽然这三种遍历方式在程序的实现上是非常容易的,可是我们有没有办法能够快速的写出前中后序遍历的结果呢?这一小节最后我们介绍一个简单的方法。 二分搜索树的遍历 对于二分搜索树来 …
Geekerstar 极客笔记 数据结构笔记总结(7.3)向堆中添加元素和Sift Up 向堆中添加元素 这个过程从用户的角度看是添加元素,不过从堆的角度看涉及一个非常基础的内部操作,相应的英文叫Sift up(堆中的元素上浮的过程),下面我们来看一下如果想向堆中添加元素应该怎么做。 首 …
Geekerstar 极客笔记 数据结构笔记总结(5.1)为什么要研究树结构 树结构 之前我们一直在研究线性数据结构,从这一章开始,我们将学习计算机领域极其重要的树结构,这一节我们学习二分搜索树。 如上图所示就是一种树结构,和线性结构不同的是,线性数据结构是把所有的数据 …
Geekerstar 极客笔记 数据结构笔记总结(9.4)Trie字典树的前缀查询 Trie字典树的前缀查询 Trie中文名称叫“字典树”,字典树很好理解,它是一个树结构,存储的是一个个字符串。 把它合在一起就像一个字典,同时它又叫前缀树,就是因为我们可以非常容易在Trie中搜索某个单词对 …
Geekerstar 极客笔记 数据结构笔记总结(1.9)均摊复杂度和防止复杂度的震荡 resize的复杂度分析 之前的时间复杂度分析我们都是分析最坏的情况。 在最坏的情况下,我们addLast了,添加一个元素的同时也要进行扩容。 由于扩容是个O(n)级别的复杂度,这就使得整个操作的复杂度依然是O( …
Geekerstar 极客笔记 数据结构笔记总结(6.4)Leetcode中的集合问题和更多集合相关问题 804. 唯一摩尔斯密码词 国际摩尔斯密码定义一种标准编码方式,将每个字母对应于一个由一系列点和短线组成的字符串, 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。 为了方便,所有26个 …
Geekerstar 极客笔记 数据结构笔记总结(1.2)二次封装属于我们自己的数组 数组基础回顾 数组最大的优点:快速查询。比如:scores[2] 数组最好应用于“索引有语意”的情况。 但是并非所有有语意的索引都适用于数组 比如:身份证号:111492198512210111 虽然看起来像一个数,但不能 …