Leetcode|数据结构

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

[TOC]

数组⁍

可变数组⁍

// 初始化可变数组
List<Integer> array = new ArrayList<>();

// 向尾部添加元素
array.add(2);
array.add(3);
array.add(1);
array.add(0);
array.add(2);

链表⁍

class ListNode {
    int val;       // 节点值
    ListNode next; // 后继节点引用
    ListNode(int x) { // 初始化节点
        val = x;
    }
}

// 实例化节点
ListNode n1 = new ListNode(4); // 节点 head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);

// 构建引用指向
n1.next = n2;
n2.next = n3;

栈⁍

先入后出

注意：通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack ，而一般将 LinkedList 作为栈来使用。详细说明请见：Stack，ArrayDeque，LinkedList 的区别


LinkedList<Integer> stack = new LinkedList<>();

stack.addLast(1);   // 元素 1 入栈
stack.addLast(2);   // 元素 2 入栈
stack.add(element); // 入栈并返回true
stack.offer(element); // 常用


2=stack.removeLast(); // 出栈 -> 元素 2
1=stack.removeLast(); // 出栈 -> 元素 1
element=stack.pollLast(); //如果此列表为空，则返回null。
e = stack.poll(); // 常用
//element=stack.pop();是去出第一个数 

//取栈顶
top=stack.getLast(); //出错会抛出异常
top=stack.peekLast();

（更常用）另一种写法：用Deque（都是从List第一个元素开始进行操作，和上面的是倒着的）

Deque<Integer> mono_stack = new ArrayDeque<Integer>();

e=mono_stack.pop();//出栈
mono_stack.push(e);//入栈
e=mono_stack.peek();//取栈顶

队列⁍

先入先出

Queue<Integer> queue = new LinkedList<>();

queue.offer(1); // 元素 1 入队
queue.offer(2); // 元素 2 入队
queue.poll();   // 出队 -> 元素 1
queue.poll();   // 出队 -> 元素 2

树⁍

树是一种非线性数据结构，根据子节点数量可分为「二叉树」和「多叉树」

class TreeNode {
    int val;        // 节点值
    TreeNode left;  // 左子节点
    TreeNode right; // 右子节点
    TreeNode(int x) {
        val = x;
    }
}

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

// 初始化节点
TreeNode n1 = new TreeNode(3); // 根节点 root
TreeNode 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;

图⁍

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

无向图⁍

邻接矩阵

$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}};

邻接表

$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^2$，其中 $N$ 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。因此， 邻接矩阵 适合存储稠密图（顶点较少、边较多）；邻接表 适合存储稀疏图（顶点较多、边较少）。

散列表⁍

非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，

// 初始化散列表
Map<String, Integer> dic = new HashMap<>();

// 添加 key -> value 键值对
dic.put("小力", 10001);
dic.put("小特", 10002);
dic.put("小扣", 10003);

// 从姓名查找学号
dic.get("小力"); // -> 10001
dic.get("小特"); // -> 10002
dic.get("小扣"); // -> 10003

// 常用判断是否存在键的同时更新键
int k = dic.getOrDefault(key,0);
dic.put(key, k+1);

堆⁍

堆是一种基于「完全二叉树」的数据结构，可使用数组实现。

以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。

堆分为「大顶堆」和「小顶堆」，

大顶堆就是根节点最大小顶堆就是根节点最小

完全二叉树定义： 设二叉树深度为 $k$

除第 $k$ 层外的其它各层（第 $1$ 至 $k-1$ 层）的节点达到最大个数

处于第 $k$ 层的节点都连续集中在最左边，

则称此二叉树为完全二叉树。

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

// 初始化小顶堆
Queue<Integer> heap = new PriorityQueue<>();

// 元素入堆
heap.offer(1);
heap.offer(4);
heap.offer(2);
heap.offer(6);
heap.offer(8);

// 元素出堆（从小到大）
heap.poll(); // -> 1
heap.poll(); // -> 2
heap.poll(); // -> 4
heap.poll(); // -> 6
heap.poll(); // -> 8