数据结构笔记总结

导航目录 第一章：数组 数据结构笔记总结（1.1）使用Java中的数组 数据结构笔记总结（1.2）二次封装属于我们自己的数组 数据结构笔记总结（1.3）向数组中添加元素 数据结构笔记总结（1.4）数组中查询元素和 …

递归算法的调试 上一小节我们学习了递归实现的底层机理，这一小节我们来学习一下递归算法的调试。 其实这个方法也没有什么特别之处，就是打印输出，通过打印输出能清楚的看出我们程序是怎样一步一步获得最 …

树结构 之前我们一直在研究线性数据结构，从这一章开始，我们将学习计算机领域极其重要的树结构，这一节我们学习二分搜索树。 如上图所示就是一种树结构，和线性结构不同的是，线性数据结构是把所有的数据 …

创建线段树 我们已经了解了什么是线段树，并且想把线段树看成满的二叉树，这种情况下用数组就可以存储线段树。 如果要考虑的区间有n个元素，数组开4*n的空间就可以承载整个线段树了，下面我们就具体的对这 …

再看二分搜索树的遍历 虽然这三种遍历方式在程序的实现上是非常容易的，可是我们有没有办法能够快速的写出前中后序遍历的结果呢？这一小节最后我们介绍一个简单的方法。 二分搜索树的遍历 对于二分搜索树来 …

简单的时间复杂度分析 我们经常能看到用下面这些方式描述时间复杂度 什么是运行时间和输入数据之间的关系呢？ 我们可以看一个非常简单的代码：下面是对一个数组中所有数字求和的代码，逻辑很简单。 通常这 …

使用链表的虚拟头结点 上一节我们学习了如何为链表添加元素，但是在添加元素的过程中我们遇到了一个问题。 就是在向链表任意一个地方添加元素的时候，在链表头添加元素和在链表的其他位置添加元素逻辑上会 …

resize的复杂度分析 之前的时间复杂度分析我们都是分析最坏的情况。 在最坏的情况下，我们addLast了，添加一个元素的同时也要进行扩容。 由于扩容是个O(n)级别的复杂度，这就使得整个操作的复杂度依然是O(n …

从堆中取出元素 我们之所以管它叫“最大堆”就是因为我们从堆中只取出堆顶的元素，也就是二叉树根节点所在的元素，这个元素也是堆中最大的元素，取出操作只能取出这个元素而不能取出其他的元素。 那么这个过 …

Trie字典树的前缀查询 Trie中文名称叫“字典树”，字典树很好理解，它是一个树结构，存储的是一个个字符串。 把它合在一起就像一个字典，同时它又叫前缀树，就是因为我们可以非常容易在Trie中搜索某个单词对 …

303. 区域和检索 – 数组不可变 给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。 示例： 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为sumRange() sumRa …

向堆中添加元素 这个过程从用户的角度看是添加元素，不过从堆的角度看涉及一个非常基础的内部操作，相应的英文叫Sift up（堆中的元素上浮的过程），下面我们来看一下如果想向堆中添加元素应该怎么做。 首先 …