算法与数据结构--待更

数据结构

常见数据结构包括：
数组（Array）与可变数组（ArrayList），链表（LinkedList），栈（Stack），队列（Queue），树（Tree），图（Graph），散列表（Hash），堆（Heap）

数组:Array
数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。

int[] ：int型数组 初始化：默认初始化：int[] array=new int[3] 静态初始化：int[] array={1,2,3} 或int [] array = new int [] {1,2,3} 动态初始化：int[] array=new int[3] array[0]=1;array[1]=2;array[2]=3;

可变数组:ArrayList
基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素。

初始化List<Integer> array=new ArrayList<>(); 向尾部添加元素：array.add(1);   array.add(3);

链表:LinkedList
链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」

如下图所示，建立此链表需要实例化每个节点，并构建各节点的引用指向。

class ListNode {    int val;// 节点值    ListNode next; // 后继节点引用    ListNode(int x) { val = x; }}// 实例化节点ListNode n1 = new ListNode(4); // 节点 headListNode n2 = new ListNode(5);ListNode n3 = new ListNode(1);// 构建引用指向n1.next = n2;n2.next = n3;

栈:stack
栈是一种具有 「先入后出」 特点的抽象数据结构，可使用数组或链表实现。

Stack<Integer> stack = new Stack<>();stack.push(1); // 元素 1 入栈stack.push(2); // 元素 2 入栈stack.pop();   // 出栈 -> 元素 2stack.pop();   // 出栈 -> 元素 1

注意：通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack ，而一般将 LinkedList 作为栈来使用。

LinkedList<Integer> stack = new LinkedList<>();stack.addLast(1);   // 元素 1 入栈stack.addLast(2);   // 元素 2 入栈stack.removeLast(); // 出栈 -> 元素 2stack.removeLast(); // 出栈 -> 元素 1

队列:Queue
队列是一种具有 「先入先出」 特点的抽象数据结构，可使用链表实现。

如下图所示，通过常用操作「入队 push()」,「出队 pop()」，展示了队列的先入先出特性。

Queue<Integer> queue = new LinkedList<>();queue.offer(1); // 元素 1 入队queue.offer(2); // 元素 2 入队queue.poll();   // 出队 -> 元素 1queue.poll();   // 出队 -> 元素 2

树:Tree
树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」

如下图所示，建立此二叉树需要实例化每个节点，并构建各节点的引用指向。

class TreeNode {    int val; // 节点值    TreeNode left;  // 左子节点    TreeNode right; // 右子节点    TreeNode(int x) { val = x; }}// 初始化节点TreeNode n1 = new TreeNode(3); // 根节点 rootTreeNode n2 = new TreeNode(4);TreeNode n3 = new TreeNode(5);TreeNode n4 = new TreeNode(1);TreeNode n5 = new TreeNode(2);// 构建引用指向n1.left = n2;n1.right = n3;n2.left = n4;n2.right = n5;

图：Graph
图是一种非线性数据结构，由「节点（顶点）vertex」和「边 edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。本文 以无向图为例 开展介绍。

如下图所示，此无向图的 顶点 和 边 集合分别为：
顶点集合： vertices = {1, 2, 3, 4, 5}
边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

表示图的方法通常有两种：
1.邻接矩阵： 使用数组 vertices 存储顶点，邻接矩阵 edges存储边； edges[i][j] 代表节点 i + 1 和 节点 j + 1 之间是否有边。

int[] vertices = {1, 2, 3, 4, 5};int[][] edges = {{0, 1, 1, 1, 1},   {1, 0, 0, 1, 0},   {1, 0, 0, 0, 1},   {1, 1, 0, 0, 1},   {1, 0, 1, 1, 0}};

2.邻接表： 使用数组 vertices 存储顶点，邻接表 edges 存储边。 edges 为一个二维容器，第一维 i 代表顶点索引，第二维 edges[i] 存储此顶点对应的边集和；例如 edges[0] = [1, 2, 3, 4] 代表 vertices[0] 的边集合为 [1, 2, 3, 4]。

int[] vertices = {1, 2, 3, 4, 5};List<List<Integer>> edges = new ArrayList<>();List<Integer> edge_1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));List<Integer> edge_2 = new ArrayList<>(Arrays.asList(0, 3));List<Integer> edge_3 = new ArrayList<>(Arrays.asList(0, 4));List<Integer> edge_4 = new ArrayList<>(Arrays.asList(0, 1, 4));List<Integer> edge_5 = new ArrayList<>(Arrays.asList(0, 2, 3));edges.add(edge_1);edges.add(edge_2);edges.add(edge_3);edges.add(edge_4);edges.add(edge_5);

邻接矩阵 VS 邻接表 ：
邻接矩阵的大小只与节点数量有关，即 N² ，其中 N 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。
因此，邻接表 适合存储稀疏图（顶点较多、边较少）； 邻接矩阵 适合存储稠密图（顶点较少、边较多）。

散列表:Map
散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。

设想一个简单场景：小力、小特、小扣的学号分别为 10001, 10002, 10003 现需求从「姓名」查找「学号」。

则可通过建立姓名为 key ，学号为 value 的散列表实现此需求，代码如下

// 初始化散列表Map<String, Integer> dic = new HashMap<>();// 添加 key -> value 键值对dic.put("小力", 10001);dic.put("小特", 10002);dic.put("小扣", 10003);// 从姓名查找学号dic.get("小力"); // -> 10001dic.get("小特"); // -> 10002dic.get("小扣"); // -> 10003

堆:Heap
堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。

完全二叉树定义： 设二叉树深度为 kk ，若二叉树除第 kk 层外的其它各层（第 11 至 k-1k−1 层）的节点达到最大个数，且处于第kk 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。

通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序，实现代码如下：

// 初始化小顶堆Queue<Integer> heap = new PriorityQueue<>();// 元素入堆heap.add(1);heap.add(4);heap.add(2);heap.add(6);heap.add(8);// 元素出堆（从小到大）heap.poll(); // -> 1heap.poll(); // -> 2heap.poll(); // -> 4heap.poll(); // -> 6heap.poll(); // -> 8

算法

时间复杂度O(1) < O(logN) < O(N) < O(N logN) < O(N²) < O(N³) < O(2^N)<O(N!)
经典算法
​递归：函数在运行时调用自己

动态规划：

搜索与回溯：

分治：

双指针：

位预算：

数学：

模拟：

查找算法

排序算法
冒泡排序：

选择排序：

插入排序：

希尔排序：

归并排序：

快速排序：

堆排序：

计数排序：

桶排序：

基数排序：

参考：作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。