刷题前您应该知道的数据结构代码块
刷题前您应该知道的数据结构代码块
简介
刷题中，我们最常用的数据结构莫过于线性数据结构以及树、堆以及图。在面试时，面试官有可能让我们手写树、图这些结构，故有必要对这些结构的构建代码熟悉。同样地，若有误，希望大家批评指正！（注：图片是我在LeetCode上的截图，不知道侵权没有，若侵权，请联系我删除！）
数组(Array)
相较于其他结构，数组应该算比较简单的，我们直接上代码。
// java版(固定长度)
// 初始化一个长度为5的数组array
int[] array = new int[5];
// 元素赋值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;
// or
int[] array = {
2, 3, 1, 0, 2};
// java版(可变长度)
// 初始化可变数组（注：非常推荐使用ArrayList）
List<Integer> array = new ArrayList<>();
// 向尾部添加元素
array.add(2);
array.add(3);
array.add(1);
array.add(0);
array.add(2);
# python(版本1)
array = [2, 3, 1, 0, 2]
# python(版本2)
array = []
array.append(2)
array.append(3)
array.append(1)
array.append(0)
array.append(2)
链表(Linked List)
// java版本
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;
# python
class ListNode:
def __init__(self, x):
self.val = x # 节点值
self.next = None # 后继节点引用
# 实例化节点
n1 = ListNode(4) # 节点head
n2 = ListNode(5)
n3 = ListNode(1)
# 构建引用指向
n1.next = n2
n2.next = n3
栈(Stack)
可通过数组或链表实现
// java(版本1(不推荐))
Stack<Integer> stack = new Stack<>();
// 常用操作,入栈和出栈,展示栈的先入后出特性.
stack.push(1); // 元素1 入栈
stack.push(2); // 元素2 入栈
stack.pop(); // 出栈 -> 元素2
stack.pop(); // 出栈 -> 元素1
// java(版本2(推荐))
LinkedList<Integer> stack = new LinkedList<>();
stack.addLast(1); // 元素1 入栈
stack.addLast(2); // 元素2 入栈
stack.removeLast(); // 出栈 -> 元素2
stack.removeLast(); // 出栈 -> 元素1
通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack ，而一般将 LinkedList 作为栈来使用。根本原因就是Vector是线程安全的，因此效率会很低。详情见链接: 原因.
# python
stack = [] # Python可将列表作为栈使用
stack.append(1) # 元素1 入栈
stack.append(2) # 元素2 入栈
stack.pop() # 出栈 -> 元素2
stack.pop() # 出栈 -> 元素1
队列(Queue)
// java版
Queue<Integer> queue = new LinkedList<>();
// 常用操作: 入队和出队,展示栈的先入先出特性.
queue.offer(1); // 元素1 入队
queue.offer(2); // 元素2 入队
queue.poll(); // 出队 -> 元素1
queue.poll(); // 出队 -> 元素2
# python(通常使用双端队列collections.deque)
from collections import deque
queue = deque()
queue.append(1) # 元素1 入队
queue.append(2) # 元素2 入队
queue.popleft() # 出队 -> 元素1
queue.popleft() # 出队 -> 元素2
树(Tree)
根据子节点数量分为二叉树和多叉树
// java版
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;
# python版
class TreeNode:
def __init__(self, x):
self.val = x # 节点值
self.left = None # 左子节点
self.right = None # 右子节点
# 初始化节点
n1 = TreeNode(3) # 根节点 root
n2 = TreeNode(4)
n3 = TreeNode(5)
n4 = TreeNode(1)
n5 = 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)}
# python(构建无向图)
""" :type edges: List[List[int]] """
connect = collections.defaultdict(list)
for i, (a, b) in enumerate(edges):
connect[a].append(b)
connect[b].append(a)
散列表(Hashing)
通过利用Hash函数将指定的[ 键 key] 映射至对应的 [值 value], 以实现高效的元素查找。
// java
// 初始化散列表
Map<String, Integer> dic = new HashMap<>();
// 添加 key -> value 键值对
dic.put("C",10001);
dic.put("S",10002);
dic.put("D",10003);
dic.put("N",10004);
// 从姓名查找学号
dic.get("C"); // -> 10001
dic.get("S"); // -> 10002
dic.get("D"); // -> 10003
dic.get("N"); // -> 10004
# python
# 初始化散列表
dic = {
}
# 添加key -> value 键值对
dic["C"] = 10001
dic["S"] = 10002
dic["D"] = 10003
dic["N"] = 10004
# 从姓名查找学号
dic["C"] # -> 10001
dic["S"] # -> 10002
dic["D"] # -> 10003
dic["N"] # -> 10004
自行设计Hash函数(有可能会考查)
// java
String[] names = {
"C", "S", "D", "N"};
// 构造简单Hash函数
int hash(int id) {
int index = (id - 1) % 10000;
return index;
}
// 在O(1)时间复杂度下通过学号查找到对应姓名, 即:
names[hash(10001)] // C
names[hash(10002)] // S
names[hash(10003)] // D
names[hash(10004)] // N
# python
names = ["C", "S", "D","N"]
# 构造简单Hash函数
def hash(id):
index = (id - 1) % 10000
return index
# 在O(1)时间复杂度下通过学号查找到对应姓名, 即:
names[hash(10001)] # C
names[hash(10002)] # S
names[hash(10003)] # D
names[hash(10004)] # N
堆(heap)
堆是一种基于 [ 完全二叉树 ] 的数据结构, 可使用数组实现, 以堆为原理的排序算法称为 [ 堆排序]
基于堆实现的数据结构为 [ 优先队列 ] 。堆分为 [ 大顶堆 ] 和 [ 小顶堆 ], 大 ( 小 ) 顶堆: 任意节点的值不大于 (小于) 其父节点的值。
// java
// 初始化小顶堆
Queue<Integer> heap = new PriorityQueue<>();
// 元素入堆
heap.add(1);
heap.add(4);
heap.add(2);
heap.add(6);
heap.add(8);
// 元素出堆 (从小到大)
heap.poll(); /-> 1
heap.poll(); /-> 2
heap.poll(); /-> 4
heap.poll(); /-> 5
heap.poll(); /-> 8
# python
from heapq import heappush, heappop
# 初始化小顶堆
heap = []
# 元素入堆
heappush(heap, 1)
heappush(heap, 4)
heappush(heap, 2)
heappush(heap, 6)
heappush(heap, 8)
# 元素出堆(从小到大)
heappop(heap) # -> 1
heappop(heap) # -> 2
heappop(heap) # -> 4
heappop(heap) # -> 6
heappop(heap) # -> 8
