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

2024-01-07 20:21:47

数据结构:列表,哈希表,集合,栈,堆,链表,二叉树,图
入门算法:递归,排序算法,二分法,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):

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

文章来源:https://blog.csdn.net/weixin_43561635/article/details/135435503
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。