小奏

二叉树 二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子 重要的二叉树结构 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1 存储 存储方式分为两种 定义树节点与左、右孩子引用（TreeNode） 使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算 父 = floor((子 - 1) / 2) 左孩子 = 父 * 2 + 1 右孩子 = 父 * 2 + 2 遍历 遍历也分为两种 广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历 深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点） pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树 in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是 ...

堆 以大顶堆为例，相对于之前的优先级队列，增加了堆化等方法 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136public class MaxHeap { int[] array; int size; public MaxHeap(int capacity) { this.array = new int[capacity]; } /** * 获取堆顶元素 * ...

阻塞队列 之前的队列在很多场景下都不能很好地工作，例如 大部分场景要求分离向队列放入（生产者）、从队列拿出（消费者）两个角色、它们得由不同的线程来担当，而之前的实现根本没有考虑线程安全问题 队列为空，那么在之前的实现里会返回 null，如果就是硬要拿到一个元素呢？只能不断循环尝试 队列为满，那么再之前的实现里会返回 false，如果就是硬要塞入一个元素呢？只能不断循环尝试 因此我们需要解决的问题有 用锁保证线程安全 用条件变量让等待非空线程与等待不满线程进入等待状态，而不是不断循环尝试，让 CPU 空转 有同学对线程安全还没有足够的认识，下面举一个反例，两个线程都要执行入队操作（几乎在同一时刻） 1234567891011121314151617181920public class TestThreadUnsafe { private final String[] array = new String[10]; private int tail = 0; public void offer(String e) { array[ ...

优先级队列 无序数组实现 要点 入队保持顺序 出队前找到优先级最高的出队，相当于一次选择排序 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667public class PriorityQueue1<E extends Priority> implements Queue<E> { Priority[] array; int size; public PriorityQueue1(int capacity) { array = new Priority[capacity]; } @Override // O(1) public boolean offer(E e) { if (isFull()) { return false; ...

双端队列 概述 双端队列、队列、栈对比 定义 特点 队列 一端删除（头）另一端添加（尾） First In First Out 栈 一端删除和添加（顶） Last In First Out 双端队列 两端都可以删除、添加 优先级队列 优先级高者先出队 延时队列 根据延时时间确定优先级 并发非阻塞队列 队列空或满时不阻塞 并发阻塞队列 队列空时删除阻塞、队列满时添加阻塞 注1： Java 中 LinkedList 即为典型双端队列实现，不过它同时实现了 Queue 接口，也提供了栈的 push pop 等方法 注2： 不同语言，操作双端队列的方法命名有所不同，参见下表 操作 Java JavaScript C++ leetCode 641 尾部插入 offerLast push push_back insertLast 头部插入 offerFirst unshift push_front insertFront 尾部移除 pollLast pop pop_back deleteLast 头部移除 ...

栈 概述 计算机科学中，stack 是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书 先提供一个栈接口 1234567891011121314151617181920212223242526272829303132public interface Stack<E> { /** * 向栈顶压入元素 * @param value 待压入值 * @return 压入成功返回 true, 否则返回 false */ boolean push(E value); /** * 从栈顶弹出元素 * @return 栈非空返回栈顶元素, 栈为空返回 null */ E pop(); /** * 返回栈顶元素, 不弹出 * @return 栈非空返回栈顶元素, 栈为空返回 null */ E peek(); /** * 判断栈是否为空 * @return 空返回 ...

队列 概述 计算机科学中，queue 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品 In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence 先定义一个简化的队列接口 123456789101112131415161718192021222324252627282930313233public interface Queue<E> { /** * 向队列尾插入值 * @param value 待插入值 * @return 插入成功返回 tru ...

递归 概述 定义 计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集 In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. 比如单链表递归遍历的例子： 12345678void f(Node node) { if(node == null) { return; } println("before:" + node.value) f(node.next); println("after:" + node.value)} 说明： 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的） 每次调用，函数处理的数据会较上次缩减（子集）， ...

链表 概述 定义 在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. 可以分类为 单向链表，每个元素只知道其下一个元素是谁 双向链表，每个元素知道其上一个元素和下一个元素 循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head 链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示 随机访问性能 根据 index 查找，时间复杂度 O(n)O(n)O(n) 插入或删除性能 起始位置：O(1)O(1)O(1) 结束位置：如果已 ...

数组 概述 定义 在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识 In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key 因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如： 1int[] array = {1,2,3,4,5} 知道了数组的数据起始地址 BaseAddressBaseAddressBaseAddress，就可以由公式 BaseAddress+i∗sizeBaseAddress + i * sizeBaseAddress+i∗size 计算出索引 iii 元素的地址 iii 即索引，在 Java、C 等语言都是从 0 开始 sizesizesize 是每个元素占用字节，例如 intintint 占 444 ...