开始刷Leetcode之前你需要知道的 - The basic is all you need

数据结构：列表，哈希表，集合，栈，堆，链表，二叉树，图
入门算法：递归，排序算法，二分法，bfs，dfs

list/array

列表常见操作，以及相关的时间复杂度。
append 一个元素、pop 末尾元素均为 O（1）
查找某个元素的索引 O（n）

new_list = []
# add
new_list.append(1) # add 1 to the end of list, O(1)
new_list.insert(0, 3) # add 3 to the beginning of list, O(n)

# remove
list1 = [1, 2, 3, 2, 3, 4, 5, 6]
list1.pop() # remove the last element of list, O(1)
list1.pop(0) # remove the first element of list, O(n)
list1.remove(2) # remove the first match element in the list

# access
new_list[1] # output: 1, access by index # O(1)
# list1: [2, 3, 2, 3, 4, 5]
list1[start:end] # the length of slice is k, O(k) 
# list1[1:4] is [3, 2, 3]

# search
res = 2 in list1 # O(n)
res # true

# get the length of list
len(list1) # O(1)

# sort
list1.sort() # O(nlogn)

# reverse the list
list1.reverse() # O(n)

# check if is empty
not list1 # False

hash

什么是哈希，哈希函数是什么，最常见的哈希表数据结构是什么（集合与哈希表）?
什么是哈希
哈希（Hashing）是一种将输入（或者称为“键”）转换成固定大小的值的过程，这个值通常是一个整数，被称为哈希值。哈希的目的主要是为了实现快速的数据查找和存取，因为通过哈希值（通常是一个较小的索引）来访问数据要比通过其他方式（比如遍历）快得多。
哈希函数是什么
哈希函数是实现哈希的具体方法，它接受输入，并返回一个通常是固定大小的数值（哈希值）。好的哈希函数应具备以下特性：
快速计算：能够快速地计算出任意输入的哈希值。
哈希值均匀分布：对于不同的输入，哈希值应该均匀地分布在所有可能的哈希值中，以减少碰撞（不同的输入得到相同的哈希值）。
碰撞最小化：尽管理论上任何哈希函数都会有碰撞，好的哈希函数会尽可能地减少碰撞的概率。
哈希表（Hash Table）：是一种实现了映射（键与值的对应关系）的数据结构，它使用哈希函数将键转换为数组的索引，这个索引决定了值的存放位置。因为这个转换过程几乎是即时的，哈希表在平均情况下为各种操作提供了快速的时间复杂度。
集合（Set）：特别的哈希表，它仅存储键，不存储值。集合通常用于快速地检查一个元素是否存在于集合中。

Hashmap/ dict/ unordered_map

哈希表一般用于干什么？
哈希表有哪些常见操作？对应的时间复杂度，空间复杂度分别是什么？

哈希表的实现：字典（Dictionary）
在Python中字典是基于哈希表实现的

my_dict = {}
# add
my_dict["apple"] = "A fruit"
my_dict["python"] = "A programming language"
my_dict # {'apple': 'A fruit', 'python': 'A programming language'}

# remove
del my_dict["apple"]

# search
if "python" in my_dict:
    print(my_dict["python"] # A programming language

set/ hashset

对于集合，操作和时间复杂度类似，因为它通常就是一个没有“值”的哈希表。
集合一般用于干什么？
集合的常见操作有哪些？每个常见操作的时间复杂度是什么？

my_set = set()

# add
my_set.add(1)
my_set.add(2)
my_set.add(3)
my_set # {1, 2, 3}
# remove
my_set.remove(2)  # 如果元素不存在，remove会引发错误
# 或者使用discard，不会引发错误
my_set.discard(3)  # 如果元素不存在，什么也不会发生
my_set # {1}

# check existance
1 in my_set # True

stack

什么是栈？什么是后进先出？
栈一般用于解决什么问题？
什么是程序栈？
你所熟悉的语言当中栈是用什么数据结构实现的？（在Python中，栈通常使用列表（List）数据结构来实现）

栈一般用于解决什么问题？

函数调用：在任何现代编程语言中，函数调用的实现都是使用栈来完成的，这个栈被称为调用栈或程序栈。
括号匹配问题：例如，编译器在编译时用栈来处理括号匹配。
撤销操作：许多应用程序使用栈来跟踪用户的操作，以便用户可以撤销它们。
表达式求值：栈可以用来对后缀表达式进行求值，以及将中缀表达式转换为后缀表达式。

程序栈，也称为调用栈，是一种特殊类型的栈，用于存储活跃的子程序的信息。这包括局部变量、返回地址、参数等。当一个函数被调用时，它的上下文被推入程序栈，当函数返回时，它的上下文被弹出。
一个栈示例：
Push (元素入栈): O(1)
Pop (元素出栈): O(1)
Peek (获取栈顶元素，但不弹出): O(1)
IsEmpty (检查栈是否为空): O(1)

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return not self.items

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("Pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("Peek from empty stack")

    def size(self):
        return len(self.items)

# 使用栈
my_stack = Stack()
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)

print(my_stack.pop())  # 输出 3
print(my_stack.peek())  # 输出 2
print(my_stack.is_empty())  # 输出 False

queue

什么是队列？什么是先进先出？
队列一般应用在哪些场景当中？
什么是消息队列？
你所熟悉的语言当中栈是用什么数据结构实现的？（Python 当中可以用 deque 或者 queue）

队列一般应用在哪些场景当中？

操作系统的任务调度：操作系统使用队列来管理多个进程的执行。
打印队列管理：在办公环境中，打印任务被添加到队列中，并按顺序执行。
实时系统的请求处理：如银行或票务系统，客户的请求按照到达的顺序处理。
网络中的数据包传输：数据包按顺序发送和接收。

什么是消息队列？

消息队列是一种应用程序间通信方法，应用程序通过读写出入队列的消息来通信，从而实现异步处理。消息队列提供了一种跨进程通信机制，用于在不同的进程中传递消息或数据。这种结构广泛应用于服务器和客户端之间的通信，以及在微服务架构中各服务间的消息传递。

Python中队列的实现

在Python中，队列通常使用collections.deque或者queue.Queue来实现。

常见操作及其时间复杂度：
Enqueue (元素入队): O(1)
Dequeue (元素出队): O(1)
IsEmpty (检查队列是否为空): O(1)
Peek/Front (查看队列的头部元素): O(1)

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def is_empty(self):
        return not self.items

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        raise IndexError("Dequeue from empty queue")

    def front(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("Front from empty queue")

    def size(self):
        return len(self.items)

# 使用队列
my_queue = Queue()
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)

print(my_queue.dequeue())  # 输出 1
print(my_queue.front())  # 输出 2
print(my_queue.is_empty())  # 输出 False

heap

什么是堆？什么是最大堆、最小堆？
堆一般用于解决什么问题？
你所熟悉的语言当中堆是用什么数据结构实现的？（Python 当中堆用的是列表实现的，并且 Python 只有最小堆没有最大堆）
一般语言不自带的数据结构：（需要自己手工创建）

什么是堆？

堆（Heap）是一种特殊的完全二叉树。所有的节点都大于等于（最大堆）或小于等于（最小堆）它们的子节点。堆常常被用作优先队列，因为它允许快速访问到最大值或最小值。

什么是最大堆、最小堆？

最大堆：在最大堆中，任何一个父节点的值都大于或等于它的子节点的值。根节点是最大的值，即堆顶是所有节点中最大的节点。
最小堆：在最小堆中，任何一个父节点的值都小于或等于它的子节点的值。根节点是最小的值，即堆顶是所有节点中最小的节点。

堆一般用于解决什么问题？

优先队列：堆是实现优先队列的常用数据结构，用于管理一组有优先级的对象。
堆排序：利用堆可以高效地进行排序，称为堆排序。
选择问题：如找出一组数中的最大k个数或最小k个数。

Python中堆的实现

在Python中，堆通常使用列表实现，并通过标准库heapq提供的函数来操作这些列表作为堆。注意，Python的heapq模块提供的是最小堆的实现。

常见操作及其时间复杂度

插入（heapq.heappush）: O(log n) - 向堆中添加一个新元素。
删除最小值（heapq.heappop）: O(log n) - 从堆中弹出最小元素。
查找最小值: O(1) - 查看堆顶元素（最小值）。
创建堆（heapq.heapify）: O(n) - 将一个列表转换成堆结构。

用Python实现堆的操作示例

import heapq

# 创建一个空堆
heap = []

# 插入元素
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

# 查看最小值，但不删除
print(heap[0])

# 删除并返回最小值
print(heapq.heappop(heap))

# 将列表转换为堆
list_for_heap = [3, 1, 4, 1, 5, 9, 2, 6, 5]
heapq.heapify(list_for_heap)
print(list_for_heap) # [1, 1, 2, 3, 5, 9, 4, 6, 5]

linked list

链表的节点（node）是如何实现的？
如何创建一个链表？
如何遍历一个链表？
如何在链表中查找一个元素是否存在？
如何在链表中添加/删除一个元素？

链表节点的实现

链表的节点通常包含两个部分：一个是存储的数据，另一个是指向下一个节点的引用（在双向链表中可能还包含指向前一个节点的引用）。在Python中，节点通常通过创建一个类来实现。

如何创建一个链表？

创建一个链表通常包括两个步骤：定义节点类，然后创建节点并将它们链接起来形成链表。

如何遍历一个链表？

遍历链表通常使用一个循环，从头节点开始，访问每个节点直到到达链表尾部的None指针。

如何在链表中查找一个元素是否存在？

查找一个元素通常需要遍历链表，比较每个节点的数据域，直到找到相应的元素或者遍历完整个链表。

如何在链表中添加/删除一个元素？

添加元素可以有多种方式，常见的有在链表头部添加（头插法），在链表尾部添加（尾插法），或者在指定节点后添加。
删除元素通常涉及到找到该元素所在的节点，然后更改前一个节点的指针来排除该节点。

常见操作及其时间复杂度

遍历: O(n) - 需要遍历每个节点。
搜索: O(n) - 最坏情况下需要遍历每个节点。
插入: O(1) - 如果知道目标位置，插入操作本身是常数时间，但如果需要在特定位置插入，可能需要O(n)时间找到位置。
删除: O(1) - 如果知道目标节点，删除操作本身是常数时间，但通常需要O(n)时间来找到要删除的节点。

用Python实现链表的操作示例

下面是如何在Python中实现简单的单向链表及其基本操作：

class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = ListNode(data)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = ListNode(data)

    def find(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def delete(self, key):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        
        if previous is None:
            self.head = current.next
        elif current:
            previous.next = current.next
            current.next = None

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用链表
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)

ll.display()  # 打印链表
print("2 is in the list:", ll.find(2))  # 查找元素
ll.delete(2)  # 删除元素
ll.display()  # 再次打印链表

以上代码演示了如何实现一个简单的单向链表，以及如何进行插入、查找和删除操作。链表的每个节点是通过ListNode类实现的，而链表的操作则是通过LinkedList类进行管理。

binary tree

二叉树的节点（node）是如何实现的？
如何创建一个二叉树？
如何遍历一个链表？何谓二叉树的层序、前序、中序、后序遍历？
二叉搜索树（二叉查找树、binary search tree、BST）
与普通的二叉树相比，二叉搜索树特点是什么？如何证明一棵二叉树是/不是一课二叉搜索树？
一个二叉树是二叉搜索树 <-> 该二叉树的中序遍历是单调递增的

二叉树的节点实现

二叉树的节点通常包含三个部分：一个是存储的数据，另外两个是指向左子节点和右子节点的引用。在Python中，节点通常通过创建一个类来实现。

创建二叉树

创建一个二叉树通常包括定义节点类，并通过连接这些节点来形成树结构。

二叉树的遍历

遍历二叉树是指按照某种顺序访问树中的每个节点一次且仅一次。

1. 层序遍历：按照树的层次从上到下访问每个节点。
2. 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。
3. 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。
4. 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。

二叉搜索树（BST）

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它具有以下特性：

• 每个节点的值都大于其左子树上任意节点的值。
• 每个节点的值都小于其右子树上任意节点的值。
• 左右子树也分别是二叉搜索树。

如何证明一棵树是二叉搜索树

一个二叉树是二叉搜索树当且仅当其中序遍历的结果是单调递增的。这是因为在中序遍历中，左子树（较小的值）先被访问，接着是根节点，然后是右子树（较大的值）。

常见操作及其时间复杂度

• 搜索: O(h) - h为树的高度。
• 插入: O(h) - 插入新节点。
• 删除: O(h) - 删除存在的节点。
• 最大/最小值查找: O(h) - 查找最大或最小值节点。

用Python实现BST的操作示例

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)

    def inorder_traversal(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder_traversal(node.left, result)
            result.append(node.value)
            self.inorder_traversal(node.right, result)
        return result

# 使用BST
bst = BinarySearchTree()
bst.insert(3)
bst.insert(1)
bst.insert(4)
bst.insert(2)

# 中序遍历BST
print(bst.inorder_traversal(bst.root))  # 输出应为[1, 2, 3, 4]，一个单调递增序列

以上代码演示了如何在Python中实现一个基本的二叉搜索树，包括插入节点和中序遍历。中序遍历的结果是单调递增的，这也验证了二叉搜索树的性质。

graph

什么是图？什么是有向图（directed graph）？什么是无向图（undirected graph）？
图与树的关系是？如何知道一个图是不是一课树？
如何实现一个简单图？

什么是图？

图（Graph）是由节点（或称为顶点，vertices）以及连接这些顶点的边（edges）组成的结构。它可以用来表示任何二元关系，如网络模型、路径寻找、社交网络等。

有向图与无向图

• 有向图（Directed Graph）：图中的边有方向，表示从一个顶点指向另一个顶点。用箭头表示边的方向。
• 无向图（Undirected Graph）：图中的边没有方向，表示两个顶点互相连接。通常用一条普通的线表示边。

图与树的关系

树是一种特殊的图。具体来说：

• 树（Tree）：是一个无环连通的无向图，也就是说，任意两个顶点之间有且仅有一条路径，且没有回路。
• 图（Graph）：可以有环，可以不连通，边可以有方向（有向图）或没有方向（无向图）。

如何知道一个图是不是一棵树？

一个图是树的充分必要条件是：

1. 无环：图中没有环。
2. 连通：图中任意两个顶点都是连通的。
3. 边数：对于n个顶点的图，恰好有n-1条边。

实现一个简单的图

图通常可以通过邻接矩阵或邻接列表来实现。邻接列表是一种空间效率更高的实现方式，尤其是对于稀疏图而言。

常见操作及其时间复杂度

• 添加顶点: O(1) - 添加一个顶点。
• 添加边: O(1) - 在邻接列表中，添加一条边。
• 搜索顶点: O(V) - 在顶点列表中搜索顶点。
• 搜索边: O(V) - 在邻接列表中搜索边。

用Python实现图的操作示例

以下是使用邻接列表来实现一个无向图的示例：

class Graph:
    def __init__(self):
        self.adj_list = {}  # 邻接列表

    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []

    def add_edge(self, v1, v2):
        if v1 in self.adj_list and v2 in self.adj_list:
            self.adj_list[v1].append(v2)  # 添加边v1->v2
            self.adj_list[v2].append(v1)  # 对于无向图，同时添加边v2->v1

    def display(self):
        for vertex in self.adj_list:
            print(f"{vertex}: {self.adj_list[vertex]}")

# 创建图实例
graph = Graph()

# 添加顶点
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')

# 添加边
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')

# 显示图
graph.display()

这段代码展示了如何创建顶点和边，并将它们添加到图中。display() 方法用于打印图的邻接列表，展示了图的结构。这个简单的例子实现的是无向图，有向图的实现只需在add_edge时不添加反向边即可。

应该掌握的入门算法：

递归：

什么是递归？
递归的优势、劣势是什么？
递归三要素是什么？

排序算法：

快速排序如何实现？时间/空间复杂度是多少？
归并排序如何实现？时间/空间复杂度是多少？

二分法：

二分法的基本原理是什么？
二分法一般用于解决什么问题？
二分法的时间复杂度是什么？

宽度优先遍历（宽度优先搜索、Breadth first search、BFS）：

宽度优先遍历的模板是什么？
宽度优先遍历的时间/空间复杂度是什么？
宽度优先遍历一颗二叉树与一个图的区别在哪？
宽度优先遍历一般用于解决什么问题？

深度优先遍历（深度优先搜索、Depth first search、DFS）：

深度优先遍历的模板是什么？
深度优先遍历的时间/空间复杂度是什么？
深度优先遍历一颗二叉树与一个图的区别在哪？
深度优先遍历一般用于解决什么问题？