设计制作小车,wix网站做seo如何,网站移动端开发公司,科技创新作文数据结构#xff1a;列表#xff0c;哈希表#xff0c;集合#xff0c;栈#xff0c;堆#xff0c;链表#xff0c;二叉树#xff0c;图 入门算法#xff1a;递归#xff0c;排序算法#xff0c;二分法#xff0c;bfs#xff0c;dfs
list/array
列表常见操作列表哈希表集合栈堆链表二叉树图 入门算法递归排序算法二分法bfsdfs
list/array
列表常见操作以及相关的时间复杂度。 append 一个元素、pop 末尾元素均为 O1 查找某个元素的索引 On
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 # Falsehash
什么是哈希哈希函数是什么最常见的哈希表数据结构是什么集合与哈希表? 什么是哈希 哈希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 languageset/ 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 # Truestack
什么是栈什么是后进先出 栈一般用于解决什么问题 什么是程序栈 你所熟悉的语言当中栈是用什么数据结构实现的在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.itemsdef 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()) # 输出 Falsequeue
什么是队列什么是先进先出 队列一般应用在哪些场景当中 什么是消息队列 你所熟悉的语言当中栈是用什么数据结构实现的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 dequeclass Queue:def __init__(self):self.items deque()def is_empty(self):return not self.itemsdef 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 dataself.next Noneclass LinkedList:def __init__(self):self.head Nonedef append(self, data):if not self.head:self.head ListNode(data)else:current self.headwhile current.next:current current.nextcurrent.next ListNode(data)def find(self, key):current self.headwhile current:if current.data key:return Truecurrent current.nextreturn Falsedef delete(self, key):current self.headprevious Nonewhile current and current.data ! key:previous currentcurrent current.nextif previous is None:self.head current.nextelif current:previous.next current.nextcurrent.next Nonedef display(self):current self.headwhile current:print(current.data, end - )current current.nextprint(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中节点通常通过创建一个类来实现。
创建二叉树
创建一个二叉树通常包括定义节点类并通过连接这些节点来形成树结构。
二叉树的遍历
遍历二叉树是指按照某种顺序访问树中的每个节点一次且仅一次。
层序遍历按照树的层次从上到下访问每个节点。前序遍历先访问根节点然后遍历左子树最后遍历右子树。中序遍历先遍历左子树然后访问根节点最后遍历右子树。后序遍历先遍历左子树然后遍历右子树最后访问根节点。
二叉搜索树BST
二叉搜索树Binary Search TreeBST是一种特殊的二叉树它具有以下特性
每个节点的值都大于其左子树上任意节点的值。每个节点的值都小于其右子树上任意节点的值。左右子树也分别是二叉搜索树。
如何证明一棵树是二叉搜索树
一个二叉树是二叉搜索树当且仅当其中序遍历的结果是单调递增的。这是因为在中序遍历中左子树较小的值先被访问接着是根节点然后是右子树较大的值。
常见操作及其时间复杂度
搜索: O(h) - h为树的高度。插入: O(h) - 插入新节点。删除: O(h) - 删除存在的节点。最大/最小值查找: O(h) - 查找最大或最小值节点。
用Python实现BST的操作示例
class TreeNode:def __init__(self, value):self.value valueself.left Noneself.right Noneclass BinarySearchTree:def __init__(self):self.root Nonedef 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, resultNone):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可以有环可以不连通边可以有方向有向图或没有方向无向图。
如何知道一个图是不是一棵树
一个图是树的充分必要条件是
无环图中没有环。连通图中任意两个顶点都是连通的。边数对于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-v2self.adj_list[v2].append(v1) # 对于无向图同时添加边v2-v1def 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
深度优先遍历的模板是什么 深度优先遍历的时间/空间复杂度是什么 深度优先遍历一颗二叉树与一个图的区别在哪 深度优先遍历一般用于解决什么问题
