数据结构与算法

[TOC]

复杂性分析

常用表示方法

Big O Notation 算法运行时间的上界。因此，给出了算法的最坏情况复杂度。

O(g(n)) = { f(n): 存在正整数c 和 n0 使得 0 ≤ f(n) ≤ cg(n) 对于 n ≥ n0 }

时间复杂度

算法的时间复杂度定义为算法运行所需的时间量，作为输入长度的函数。请注意，运行时间是输入长度的函数，而不是算法运行所在机器的实际执行时间

为了估计时间复杂度，我们需要考虑每条基本指令的成本和指令执行的次数。

• 如果语句具有比较、返回语句、赋值和读取变量等基本操作。我们可以假设它们每O(1)花费常数时间

  T(n) = t(statement1) + t(statement2) + ... + t(statementN);
  总之 T(n) = O(1) 因为复杂度是恒定的

• 对于任何循环，我们找出其中的循环 内语句的运行时间（包括条件测试），并将其乘以迭代的次数

  for x in range(0,n):
       """这里有很多简单地执行语句"""
      print(x)

这个程序会执行n 次，所以 这个程序所花费的时间是(线性复杂度)：
T(n) = n * (t(statement1)...) = n* O(1) = O(n)
如果嵌套循环，比如第一个循环n 次，第二个循环m 次。 T(n) = nm(t(statement)..)==O(n*m)

空间复杂度

定义： 算法解决问题所需要的把内存量。
一个算法的空间复杂度是该算法相对于输入大小所占用的总空间。空间复杂度包括辅助空间和输入使用的空间。与时间复杂度是平行概念。

---

数组，链表

数组

链表

初始化

class ListNode:
    def __init__(self,val:int): 
        self.val : int = val  #值
        self.next :ListNode | None  = None #后继节点的引用
        self.prev : ListNode | None = None # 前驱节点引用
"""初始化链表"""
# 初始化链表 1 -> 3 -> 2 -> 5 -> 4
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 构建节点之间的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
        

插入操作

• 在 n0 n1 之间插入节点:

  def insert(n0:ListNode,p:ListNode):
      n1 = n0.next    #保留一下被插入位置的后一个值
      p.next = n1     
      n0.next = p   

  别忘了保存一下占据所插入位置的原来的元素

• 插入头节点： 指向，更新头节点

  def insert_at_head(head:ListNode,p :ListNode) -> ListNode:
      p.next = head
      # head = p  这里隐含一步 把头结点更改为 p
      return p

• 插入尾节点: 遍历找到尾节点，然后将当前尾节点指向真正的尾节点

  def insert_at_tail(head:ListNode,p:ListNode) -> ListNode:
      # 如果头节点是空的，将p节点直接作为头节点
      if head == None:
          return p 
      #头节点非空，遍历找到尾节点
      current = head
      while current.next is not  None:
          current = current.next 
      # p.next = None   这一步是多余操作，因为新节点创建的时候默认的next 就是指向 None
      current.next = p
      return head

删除操作

• 删除中间节点 这里假设删除 n0 后的第一个节点 p ( n0 -> p -> n1)

  只是更改指向

  def remove(n0 : ListNode):
      if not n0.next :
          return
      #先要找到后面两个节点 才能进行删除
      p = n0.next
      n1 = p.next
      n0.next = n1

  如果给定下标（index），删除指定索引的节点，我们应该通过遍历找到 下标index 前一个节点，以及这个节点，和它后一个节点。

• 删除头节点 更新新的头节点即可

  def remove_head(head : ListNode) -> ListNode:
      #如果链表是空的，直接返回空
      if not head:
          return None
      # 非空，返回head的下一个节点
      # head(新) = head.next
      return head.next 

  后面也可以写成 head = head.next return head

• 删除尾节点 需要遍历到倒数第二个节点，然后更新指向

  def removr_tail(head : ListNode) -> ListNode:
      
      # 为空，返回None
      if not head:
          return None
      # 只有一个值，删除完尾节点之后为空
      if not head.next :
          return None 
      # 循环找到倒数第二个节点，然后将其指针指向None
      current = head
      while current.next.next :
          current = current.next
      current.next = None  # 当前current 为倒数第二个节点
      return head  

访问操作

def access(head: ListNode, index: int) -> ListNode:
    code = head
    for _ in range(index):
        if not code:
            return None
        code = code.next
    return code

用临时变量 code 避免对原来head 的修改。

下面会对head 进行修改

def access(head, index: int) :
for _ in range(index):
if not head:
return None
head = head.next
return head

查找操作

返回该节点在链表中的索引

def find(head : ListNode ,target : int) -> int :
    index = 0
    # 非空 的时候执行 当为none 的时候，全查找或者没有数值的时候直接返回-1 即可
    while head :
        if head.val == target :
            return index
        head = head.next
        index +=1
    return -1

---

栈，队列

栈

栈的常用操作

方法	描述
push()	元素入栈，从顶部 o(1)
pop()	栈顶元素出栈（确保stack 不为空）o(1)
peek()	访问栈顶元素 o(1)

基于链表实现栈

push (val) : 将元素添加到有头节点的位置

pop(): 将头节点删除

使用链表的头节点作为栈顶

在pop(),与 push() 别忘了更新头节点

• 一些简单的初始化

  设置栈顶元素为头节点，以及栈的大小

  class LinkedListStack:
      
      def __init__(self):
          self._peek : ListNode | None = None 
          self._size : int = 0
          
      def size(self):
          return self._size
      
      def is_empty(self):
          return self._size == 0
     

• push 函数实现 将元素插入到头节点的位置 ,指向+更新头节点。

    
  def push(self,val):
      node = ListNode(val)  #  node 自动指向 None
      node.next = self._peek
      self._peek = node 
      self._size +=1
    

• pop （） 删除头节点 ，不指向，直接更新头节点

  def pop(self):
      num = self.peek()  # 获取当前的栈顶元素
      self._peek = self._peek.next
      self._size -= 1
      return num

• peek () 头节点非空，返回节点的值

    
  def peek(self):
      # 当头节点不是空的时候返回 值
      if not self._peek:
          return None
      return self._peek.val
      

• to_list () 转换成列表

    
  def to_list(self):
     # 1->2->3->4 ->none
      newlist = []
      node = self._peek
      for _ in range(self._size):   # 这里也可以用 while self._peek 来进行循环
          newlist.append(node.val)
          node = node.next 
      return newlist
    
    
    

  这里引用 临时节点 node 避免对其破坏

基于数组实现栈

前缀表示法，后缀表示法，前传后 都是数字放栈，操作完入栈

中转后，操作符入栈，数字储存列表。

常见题型：

  # Q1 在python 中设计 stack()
class Stack:
    def __init__(self):
        self.__items = []
# is_empty 用于检查是否为空，返回一个布尔值        
    def is_empty(self):
        return len(self.__items) == 0
    
    def size(self):
        return len(self.__items)
    
    def push(self,item):
        self.__items.append(item)
        
    def pop(self):
        return self.__items.pop()
    
    def peek(self):
        return self.__items[-1]
    
    
#Q2 get_min 函数 

"""我们要实现的功能
push(x)  ——> none ;push x on the stack
top()  ——> x   ; see the top element  and  return it 
pop()  ——> x   ; 删除顶部元素并且返回该值
get_min()  ——> x ; 返回栈里最小的元素
这里通过用两个栈,一个栈用于保持栈顶为最小的元素,另一个正常的进行栈的操作

"""


class MinStack():
    
    def __init__(self):
        self.stack = []
        self.minstack = []
        
    def push(self,x):
        self.stack.append(x)
        
        if self.minstack :
            self.minstack.append(min(x,self.minstack[-1]))    
        else:
            self.minstack.append(x)
            
    def pop(self):
        if self.stack:
            self.stack.pop()
            self.minstack.pop()
        else:
            pass
    def top(self):
        if self.stack:
            return self.stack[-1]
        else:
            return -1
        
    def getMin(self):
        if self.minstack:
            return self.minstack[-1]
        else:
            return -1

#Q3 关于符号

"""得到任何类型的打开括号就将其放入栈中，然后检测到闭合括号，通过弹出栈顶元素查看是否匹配
if open : add
else : check
"""
class Solution:
    def isValid(self,s:str)-> bool :     # 进行注解 
        stack = []
        
        mapping = {
            "{":"}",
            "(":")",
            "[":"]",
            }
        
            
        for char in s :
            if char in "({[":
                stack.append(char)
            else:
                if stack:
                    if char == mapping.get(stack[-1]):
                        stack.pop()
                    return  False 
                return False   # 如果只有闭合括号没有开括号也返回false
        return len(stack) == 0    # 当检查完所有的闭合括号，看栈里是否还有剩余


# Q4 按照software 讲解的过程

def validate_braces(input_str):
    stack = Stack()
    for char in input_str:
        if char== "{":
            stack.push(char)
        elif char == "}":
            if stack.pop() != "{" or stack.is_empty():
                return "ERROR"
    if not stack.is_empty():
        return "ERROR"
    return "correct" 




# 计算机计算方法  infix -> 中缀转化成后缀
class Solution:
    
    def calculate(self,s:str)-> int:
        def read(s):
            infix = []
    
    
        def infix_to_postfix(infix):
            postfix = []
            stack = []
            
            for i in infix :
                if i == "(":
                    stack.append(i)
                elif i == ")":
                    while stack[-1]!= "(":
                        postfix.append(stack.pop())
                    stack.pop()
                elif i not in operators:
                    postfix.append(i)
                else:
                    while stack and priority[stack[-1]] >= priority[i]:
                        postfix.append(stack.pop())
                    stack.append(i)
            while stack:
                postfix.append(stack.pop())
            
            return postfix 
        import operator
        
        def evaluate_postfix(postfix):
            stack = []
            ops = {
                "+" : operator.add,
                "-" : operator.sub,
                "*" : operator.mul,
                "/" : operator.truediv
            }
            
            for i in postfix :
                if i not in ops :
                    stack.append(int(i))
                else:
                    n1 = stack.pop()
                    n2 = stack.pop()
                    result = ops[i](n1,n2)
                    stack.append(int(result))
                    
            return stack[0]
        
        
        operators = "()+-*/"
        priority = {
            "(" : -1,
            "*" : 1,
            "/" : 1,
            "+ ": 0,
            "-": 0
        }
        
  

---

队列

我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

队列常用操作与栈类似，只不过push 是入队，将元素添加至队尾

我们可以直接使用python 中的队列类

from collections import deque

#初始化队列
#在 Python 中，我们一般将双向队列类 deque 当作队列使用
#虽然 queue.Queue() 是纯正的队列类，但不太好用，因此不推荐
que: deque[int] = deque()

#元素入队
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)

#访问队首元素
front: int = que[0]

#元素出队
pop: int = que.popleft()

#获取队列的长度
size: int = len(que)

#判断队列是否为空
is_empty: bool = len(que) == 0

基于链表实现队列

入队 ： 将节点添加到链表尾部 。

出队： 链表头部删除操作

• 初始化操作

  class LinkedListQueue:
      
      def __init__(self):
          self._front  = None   # 初始化头节点front
          self._rear = None  # 初始化尾节点 rear
          self._size = 0
      def size(self):
          return self._size
      def is_empty(self):
          return self._size == 0

  这里初始化了头节点和尾节点！

• push() 把节点添加到链表尾部

  def push(self,num):
      node = ListNode(num)
      #如果链表是空的 将头节点尾节点都指向 node
      if self._front is None :
          self._front = node
          self._rear = node 
      # 非空，将尾节点指向，更新尾节点
      else:
          self._rear.next = node
          self._rear = node 
      
      self._size += 1

• pop() 删除头节点

  def pop(self):
      # 先要获取一下当前头节点的值 
      num = self.peek()
      self._front = self._front.next 
      
      self._size -=1

• peek()

      
  def peek(self):
      if self.is_empty():
          raise IndexError ("队列为空")
      return self._front.val 
  	
    

• to_list()

    
  def to_list(self):
      queue = []
      node = self._front 
      while node:
          queue.append(node.val)
          node = node.next 
          
      return queue
    

基于数组实现队列

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

数组中的下标为[0,capacity-1] 比如说，这个队列（环形数组为[none,2,4,5,none]） front 指向的是队首元素 2 rear 指向的是 最后面的 none .

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]

• 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。
• 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

在不断的入队与出队，我们是将front , rear 分别往下移动来实现的，所以当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”

• 初始化 。队列的容量，队列的长度，以及队首指针

  class ArrayQueue:
      
      def __init__(self,size):
          self._nums = [0]*size   #用于储存队列元素的数组
          self._front = 0  #队首指针
          self._size = 0 # 队列长度
      #获取队列的容量    
      def capacity (self):
          return len(self._nums)
          
      def size(self):
          return self._size
      
      def is_empty (self):
          
          return self._size == 0

• push() 计算尾指针rear ; 将元素添加到rear 处； 将 size 自增 1

    
  def push(self,num):
      """循环计算出现有队列的末尾需要插入的位置rear"""
      
      # 如果队列已将满，不能再进行插入操作
      if self._size == self.capacity :
          raise IndexError ("队列已满")
      
      rear = (self._front + self._size)% self.capacity
      self._nums [rear] = num
      self._size +=1
      
    

• pop() 将对首指针 front 自增1 size 自减1

  def pop(self):
      num = self.peek()
      self._front = (self._front + 1) % self.capacity
      self._size -=1
      return num
    

• peek () 非空就输出值

def peek(self):
    # 如果对列是空的，返回 none
    if self.is_empty:
        return IndexError ("队列为空")
    num = self._nums[self._front]
    return num
  

• to_list

      
  def to_list(self):
      res = [0]* self._size 
      i = self._front
      for j in range(self._size):
          res[j] = self._nums[i%self.capacity]
          i+=1
      return res 
      

  这里仍然用一个临时变量作为队伍首节点

另外一种写法

class CircularQueue:
    def __init__(self, capacity: int):
        """初始化循环队列"""
        self.capacity = capacity
        self.items = [None] * capacity  # 固定大小的数组
        self.front = 0  # 队首指针
        self.rear = 0   # 队尾指针
        self.size = 0   # 队列中元素的数量

    def is_empty(self) -> bool:
        """检查队列是否为空"""
        return self.size == 0

    def is_full(self) -> bool:
        """检查队列是否已满"""
        return self.size == self.capacity

    def enqueue(self, item):
        """入队操作"""
        if self.is_full():
            raise OverflowError("队列已满")
        self.items[self.rear] = item               # 在 rear 指针位置插入元素
        self.rear = (self.rear + 1) % self.capacity  # 更新 rear 指针
        self.size += 1

    def dequeue(self):
        """出队操作"""
        if self.is_empty():
            raise IndexError("队列为空")
        item = self.items[self.front]             # 取出 front 指针位置的元素
        self.items[self.front] = None             # 清空当前位置
        self.front = (self.front + 1) % self.capacity  # 更新 front 指针
        self.size -= 1
        return item

    def peek(self):
        """查看队首元素"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.items[self.front]

    def get_size(self) -> int:
        """获取队列中的元素数量"""
        return self.size

    def to_list(self) -> list:
        """返回当前队列的列表表示，方便查看内容"""
        result = []
        idx = self.front
        for _ in range(self.size):
            result.append(self.items[idx])
            idx = (idx + 1) % self.capacity
        return result

在环形队列的固定队首方案中，推荐使用 rear = (self._front + self._size) % self.capacity()，而在动态指针移动的队列方案中，可用 rear = (rear + 1) % capacity。

双向队列

双向列表的常用操作

方法名	描述	时间复杂度
push_first()	将元素添加至队首	O(1)
push_last()	将元素添加至队尾	O(1)
pop_first()	删除队首元素	O(1)
pop_last()	删除队尾元素	O(1)
peek_first()	访问队首元素	O(1)
peek_last()	访问队尾元素	O(1)

在python 中可以直接用内置的类实现

from collections import deque

# 初始化双向队列
deq: deque[int] = deque()

# 元素入队
deq.append(2)      # 添加至队尾
deq.append(5)
deq.append(4)
deq.appendleft(3)  # 添加至队首
deq.appendleft(1)

# 访问元素
front: int = deq[0]  # 队首元素
rear: int = deq[-1]  # 队尾元素

# 元素出队
pop_front: int = deq.popleft()  # 队首元素出队
pop_rear: int = deq.pop()       # 队尾元素出队

# 获取双向队列的长度
size: int = len(deq)

# 判断双向队列是否为空
is_empty: bool = len(deq) == 0

基于双向链表实现双向队列

哈希表

又称散列表，实现key 与 vvalue 的映射，实现高效元素查询。在哈希表中进行增删查改的时间复杂度都是 O(1) ，非常高效

哈希表常用操作

在python 中，哈希表就是我们所说的字典

#初始化
hmap = {}
#增加
hmap[1234] = "jdskal"
hmap[4324] = "jlfksdd"

#删除
hmap.pop(1234)

#查找
name =hmap[4324]

哈希表有三种遍历的方法： 遍历键值对，遍历值，遍历键

#键值对
for key,value in hmap.items():
    print(key,"->",value)
#键
for key in hmap.keys():
    print()
#值
for value in hmap.values():
    print()

哈希表的简单实现

什么是哈希函数？

哈希函数就是将输入的 键 映射为数组中的索引值

我们将数组中的每个空位置看成桶 ——包含key 和value

为了将数据（通常是键值对）存储到哈希表中，我们先计算该数据对应的“桶”的位置（索引），这就是哈希函数的作用。

通过这个索引，直接访问数组中的位置并存储或检索数据，这样可以做到常数时间复杂度 O(1)。

哈希函数

def hash_function(key, capacity):
    # 将 key 转换为整数（这里假设 key 是字符串），并取模数组的大小
    return hash(key) % capacity
 
  

哈希冲突，就是多个key 指向同一个储存位置的时候，为了让避免哈希冲突，通过阔容哈希表来实现。

另一种方法：中平方哈希方法是一种针对数字键的替代哈希技术

将数值平方，去平方的部分数字，将其进行取模运算。

对于字符串，我们用ascll 码获得数字总和，然后获得索引，那么如果出现两个单词的字母完全相同那么会对用相同的索引，所以通过每个字符乘以权重在进行相加

def hash_string(s,stringsize):
    	sum =0
    	for pos in range(len(s)):
        	sum = sum+(pos+1)*ord(s[pos])
    	return sum%stringsize

pos +1 是为了权重不为零

哈希冲突

为了提升效率，我们可以采用以下策略。

1. 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”

链式地址 ： 将单个元素转化成链表，将发生冲突的键值对储存在同一个链表中。

开放寻址：有三种方法，线性侦测，平方探测，多次哈希

线性侦测

• 插入元素：先通过哈希函数计算出索引，如果索引中有元素，就以步长为1 向后线性遍历，(这里也有可能是步长的平方)直到找到空元素，将其插入。

• 寻找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None

• 删除元素：不能直接进行删除操作，会对后续查找元素造成影响。

  一般使用TOMBSTONE进行标记

  懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着 TOMBSTONE 的增加，搜索时间也会增加，因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素。

  #线性探测    
      def get_new_hash_code_probing(self,index):
          return (index+1)%self.__size	
  #二次探测
      def get_new_hash_code_quadratic_probing(self, index, distance):
          return (index + distance**2)%self.__size    
  #双重哈希探测
  
      def get_new_hash_code_double_hashing(self,key):
          index = self.get_hash_code(key)
          return (index+(self.__second_hash_value - (key%self.__second_hash_value)))%self.__size
        

树

二叉树

二叉树是一种非线性的数据结构（分治逻辑）与链表相似，二叉树的基本单元是节点，每个节点包含值，左子节点引用和右子节点引用

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left : TreeNode= None  #定义左节点引用
        self.right : TreeNode = None #定义右节点引用                
#另一种方法        
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right
        

每个节点都有两个指针，指向左子节点和右子节点，该节点被称之为左子节点和右子节点的父节点。当给定一个二叉树的节点之后，我们将该节点的左子节点以及下面的节点形成的树称之为左子树

二叉树的一些概念

• 根节点 ： 位于二叉树的顶层，没有父节点

• 叶节点 ： 没有子节点的节点，两个指针指向None

• 边 ： 连接两个节点的线段，即节点引用（指针）

• 节点所在的层：递增，根节点的层数为1

• 节点的度： 节点的子节点的数量。 在二叉树中，度的取值范围为0，1，2

• 二叉树的高度： 从根节点到最远叶节点所经过的边的数量

• 节点的深度：从该根节点到该节点所经过的边的个数

• 节点的高度： 从距离该节点最远的叶节点到该节点做经过的边的数量

请注意，我们通常将“高度”和“深度”定义为“经过的边的数量”，但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下，高度和深度都需要加 1 。

基本操作

• 插入与删除

  #初始化二叉树
  #初始化节点
  n1 = TreeNode(val=1)
  n2 = TreeNode(val=2)
  n3 = TreeNode(val=3)
  n4 = TreeNode(val=4)
  n5 = TreeNode(val=5)
  #构建节点之间的引用（指针）
  n1.left = n2
  n1.right = n3
  n2.left = n4
  n2.right = n5      
        
  #插入与删除
  p = TreeNode(0)
  n1.left = p
  p.left = n2  #在n1 与n2 之间插入节点p
  
  #删除节点p
  n1.left = n2
  
  #另外一种方法，在类中创建方法

  学校版本

class TreeNode:
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right
        
    def insert_left(self,newval):
        if self.left== None:
            self.left = TreeNode(newval)    
        else:
            subtree = TreeNode(newval,left = self.left) #生成子树
            self.left = subtree #把子树作为整体添加进去  
    def insert_right(self,newval):
        if self.right == None:
            self.right = TreeNode(newval)
        else:
            subtree = TreeNode(newval,right = self.right)
            self.right = subtree
            
            
    def get_left(self):
        return self.left
    def get_right(self):
        return self.right
    def set_val(self,val):
        self.val = val        
    def get_val(self):
        return self.val
    

常见二叉树类型

• 完美二叉树(满二叉树)

  叶节点的度为0，其余所有节点的度都为2，如果树的高度是h，则节点总数为2^{h+1} -1

  完美二叉树

• 完全二叉树

  只有最底层的节点未被填满，且最底层节点尽量靠左填充。请注意，完美二叉树也是一棵完全二叉树。

  

• 完满二叉树

  除了叶节点之外，其余所有节点都有两个子节点。

  

• 平衡二叉树

  任何节点的左子树和右子树的高度之差的绝对值不超过1

  

二叉树遍历

二叉树是一种非线性的数据结构，所以遍历树一般要用到搜素算法

常见遍历方式： 层序遍历，前序遍历，中序遍历和后序遍历

• 层序遍历

  从顶部到底部逐层遍历二叉树，每一层按照从左到右的顺序遍历访问节点 本质上是 广度优先遍历 也是广度优先搜索

  def level_order(root):
      queue = deque()
      queue.append(root)
      
      result = []
      #队列非空就左端弹出，将值储存在列表中
      while queue:
          node = queue.popleft()
          result.append(node.val)
          
          #如果该节点有左子右子，则入队
          if node.left is not None:
              queue.append(node.left)
          if node.right is not  None:
              queue.append(node.right)
              
      return result

  

• 前序遍历，中序，后序遍历

  前序遍历： 根节点——> 左子树——> 右子树

  #递归实现前序遍   
  def preorder_traversal(root):
      if root is None:
          return []
      return [root.val]+ preorder_traversal(root.left)+preorder_traversal(root.right)
      
  def preorder_traversal_iterative(root):
      if root is None :
          return []
      #栈是用来存储东西的，先进后出，所以把根存入之后取出来，存有右节点，存左节点
      stack = [root]
      result = []
      
      while stack:
          node = stack.pop()
          result.append(node.val)
          
          if node.right :
              stack.append(node.right)
              
          if node.left:
              stack.append(node.left)
              
      return result

  中序遍历： 左子树——> 根节点——> 右子树

  左子树 -> 当前节点 -> 右子树

  def inorder_traversal(root):  
      if root is None:
          return []
      
      return inorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)
  
  
  def inorder_traversal_iterative(root):
      
      result=[]   #记录结果
      stack = []   #模拟递归的栈
      current = root      #当前节点
      
      #栈不为空或者当前节点存在
      while current or stack:
          #1.先将左子树入栈
          while current :
              stack.append(current)
              current = current.left
              
          #弹出栈顶节点，并访问
          current = stack.pop()
          result.append(current.val)
          #访问右子树
          current = current.right    
      return result      

  后序遍历： 左子树——>右子树——> 根节点

  def postorder_traversal(root): 
      if root is None :
          return []
      return postorder_traversal(root.left)+postorder_traversal(root.right) + [root.val]       
       
  def postorder_traversal_iterative(root):
      if root is None :
          return []
      
      stack = [root]
      result = []
      
      while stack :
          node = stack.pop() 
          result.append(node.val)
          
          
          if node.left :
              stack.append(node.left)
              
          if node.right:
              stack.append(node.right)
              
      return result[::-1]
          

  

前序遍历和后序遍历的区别

特性	前序遍历	后序遍历
遍历顺序	当前节点 -> 左子树 -> 右子树	左子树 -> 右子树 -> 当前节点
栈的入栈顺序	右子树先入栈，左子树后入栈	左子树先入栈，右子树后入栈
结果反转	不需要反转	需要反转结果，因为是先右后左入栈
访问顺序	访问根节点后先访问左子树，再访问右子树	访问左右子树后再访问根节点

二叉树的数组表示

表示完美二叉树

依照层序遍历，我们可以推导出父节点与子节点之间的关系：当前节点为 i ，左子节点为 2i +1 右子节点为 2i +2

表示任意的二叉树

在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None ，因此我们无法仅凭该序列来推测 None 的数量和分布位置。存在多种二叉树结构都符合该层序遍历序列

考虑在层序遍历序列中显式地写出所有 None

如图：

回顾完全二叉树的定义，None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾。

这意味着使用数组表示完全二叉树时，可以省略存储所有 None

如图：

"""1.给定某节点,获取它的值,左右子节点,父节点
   2.获取前序中序后序层序 序列的结果""" 
 
class ArrayBinaryTree:
    """数组表示下的二叉树类"""
    def __init__(self,arr):
        self._tree = list(arr)
    def size(self):
        return len(self._tree)
    #获取索引为i的元素
    def val(self,i):
            if i < 0 or i >= self.size():
                return None
            return self._tree[i]
        
    #获取索引为i的左子节点的索引
    def left(self,i):
        return 2*i+1
    #获取索引为i的右子节点的索引
    def right(self,i):
        return 2*i+2
    
    def parent(self,i):
        return (i-1)//2
    
    #层序遍历：
    def level_order(self):
        self.res = []
        for i in range(self.size()):
            if self.val(i) is not None:
                self.res.append(self.val(i)) 
        return self.res
       
    #深度优先遍历
    """i代表当前节点的索引,order代表遍历的顺,这里注意右子树的访问试下左子树递归完成之后自然发生的"""
    def dfs(self,i,order):
        #递归中止条件
        if self.val(i) is None:
            return 
        #前序遍历
        if order == "pre":
            self.res.append(self.val(i))
        self.dfs(self,self.left(i),order) #在递归访问左右子树之前,先访问根节点，而后递归访问左子树
        #中序遍历
        if order == "in":
            self.res.append(self.val(i))
        self.dfs(self,self.right(i),order) #在递归访问左子树之后、右子树之前将当前节点加入,而后递归访问右子树
        #后序遍历
        
        if order == "post":
            self.res.append(self.val(i))   #在递归访问左右子树之后将当前节点加入结果。
    def pre_order(self):
        self.res = []
        self.dfs(0,"pre")              
        return self.res
    def in_order(self):
        self.res = []
        self.dfs(0,"in")
        return self.res
    def post_order(self):
        self.res = []
        self.dfs(0,"post")
        return self.res
        

二叉搜索树

二叉搜索树满足以下条件

• 对于根节点，左子树的所有节点的值 < 根节点的值 <右子树的所有节点的值
• 任意节点的左右子树也是二叉搜索树，即同样满足上述条件

二叉树的操作

查找节点

与二分查找的原理类似

给定目标节点值 num ，可以根据二叉搜索树的性质来查找。如图 7-17 所示，我们声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。

若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。

若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。

若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点

def search(self,num):
    cur = self._root
    while cur : #直到越过叶子节点时候跳出循环
        if cur.val < num:
            cur = cur.right
            
        elif cur.val > num:
            cur = cur.left
        else:
            break 
    return cur   

插入节点

寻找节点插入位置，在该位置插入节点

#迭代方法

def insert(self,num):
    #如果树是空，初始化根节点
    if self._root is None:
        self._root = TreeNode(num)
        return
    #查找插入位置,我们还要保存cur的父节点
    cur,pre = self._root,None
    while cur:
       
        if cur.val == num :
            return 
        pre = cur
        if cur.val < num :
            cur  = cur.right
        else:
            cur = cur.left
    #插入节点
    node = TreeNode(num)
    if pre.val < num :
        pre.right = node
    else:
        pre.left = node
        
#递归方法
def insert(self,val):
    #插入节点主方法
    self._root = self.insert_helper(self._root,val)
def insert_helper(self,node,val):
    #插入节点辅助递归方法
    if node is None:
        return TreeNode(val)  #当前节点为空，找到位置，创建一个新节点
    if node.val == val:
        return node   #值相等不允许重复插入，直接返回
    if val < node.val:
        node.left = self.insert_helper(node.left,val)
    else:
        node.right = self.insert_helper(node.right,val) #递归插入左子树或者右子树
        
    return node 

删除节点

先查找再删除，需要注意该节点的子节点

没有子节点，直接删除；有一个子节点，该子节点直接代替父节点；有两个节点：

——>右子树的最小节点或者左子树的最大节点。

def remove(self,num):
    #如果树是空的，直接返回
    if self._root == None :
        return
    #查找待删节点cur和其父节点pre
    cur,pre = self._root,None
    while cur :
        if cur.val == num:
            break
        pre = cur
        if cur.val < num :
            cur = cur.right
        else:
            cur = cur.left
    #如果没有找到，直接返回
    if cur == None:
        return
    #开始分析cur 的子节点情况
    #如果有0/1个子节点
    if cur.left == None or cur.right == None:
        child = cur.left or cur.right
        #如果cur是根节点
        if cur == self._root:
            self._root = child
        else:
            if pre.left == cur:
                pre.left = child
            else:
                pre.right = child
    
    #如果是两个子节点
	else:
        #查找剩下右子树的最小节点
        tmp = cur.right
        while tmp.left:
            tmp = tmp.left   
        self.remove(tmp.val)
        cur.val = tmp.val

注意最后 self.remove(tmp.val)
cur.val = tmp.val 顺序不能更换。

中序遍历有序

二叉树的中序遍历：左——> 中——>右 , 而二叉搜索树满足“左子节点 < 根节点 < 右子节点”的大小关系。二叉搜索树的中序遍历序列是升序的。

	无序数组	二叉搜索树
查找元素	O(n)	O(log n)
插入元素	O(1)	O(log n)
删除元素	O(n)	O(log n)

一种更简单的实现

AVL树

需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能

是一种平衡二叉树。

常见术语

• 节点高度 （需要为节点类添加height变量）

  class TreeNode:
      def __init__(self,val):
          self.val = val
          self.height = 0
          self.left = None
          self.right = None 
  
  class AVLTree:
      def height(self,node):
          #空节点为-1，叶子节点为0
              if node :
                  return node.height  
              return -1    
              
              
      def update_height(self,node):
          #节点高度为最高子树高度 + 1
              node.height = max([self.height(node.left), self.height(node.right)]) + 1
              
              
         

  这里height 指的是该节点到最远的叶子节点的距离，也就是边的数量（有的定义不太一样) 叶节点的高度为 0 ，而空节点的高度为 -1.

  在 AVLTree 中 node.height 是直接用的属性

• 节点平衡因子

  定义为：节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0。

  class AVLTree:
      def balance_factor(self,node):
          return self.height(node.left)- self.height(self.right) 
             
         

  假设平衡因子为f ，那么一颗AVL树的任意节点的平衡因子都满足 -1 <= f <= 1

AVL 树旋转

旋转：是让其保持二叉搜索树的性质，也是将其变成平衡二叉树。

根据节点失衡情况分为四种 ： 右旋，左旋，右+左旋 左+右旋

插入所导致的多个祖先失衡，只需要调节距离插入节点最近的失衡节点，其他节点自会平衡

LL

插入位置为右孩子的右子树。该节点平衡因子与右孩子的平衡因子分别为 -2，-1

操作： 该节点右旋。

两个失衡节点，只需要看最近的一个，即节点3 ， 3 作为node ，左孩子child 为1

失衡节点想要右旋转的时候，如果左孩子还有右边孙子，需要添加一步骤，将grand_child 添加到node 左子节点。如下图

class AVLTree:
    #LL形式
    def right_rorate(self,node):
        child = node.left
        grand = child.right
        #以child 为原点将node 右边旋转
        child.right = node
        node.left = grand
        #更新高度
        self.update_height(node)
        self.update_height(child)
        #返回旋转后子树的新的根节点
        return child

更新高度时只需要更新旋转过程中受到影响的节点，即父节点（node）和子节点（child）。grand（子节点的右子树）本身在旋转中没有被移动或修改，因此无需更新其高度。

RR

插入位置为左孩子的左子树。该节点和左孩子的平衡因子分别是2，1

操作：该节点左旋。

class AVLTree:
    #RR形式
    def left_rotate(self,node):
        child = node.right
        grand = child.left
        #以child 为原点将node 左边旋转
        child.left = node
        node.right = grand
        #更新高度
        self.update_height(node)
        self.update_height(child)
        #返回旋转后子树的新的根节点
        return child

LR

插入位置为左孩子的右子树。该节点和左孩子的平衡因子分别是2，-1

操作：左孩子左旋，该节点右旋

RL

插入位置为右孩子的左子树。该节点和右孩子的平衡因子分别是-2，1

操作：右孩子右旋，该节点左旋

为了便于操作，我们可以将四种操作封装。

失衡节点的平衡因子	子节点的平衡因子	应采用的旋转方法
> 1（左偏树）	>=0	右旋
> 1 （左偏树）	<0	先左旋后右旋
< -1 （右偏树）	<= 0	左旋
< -1 （右偏树）	>0	先右旋后左旋

class AVLTree:
    def rotate(self,node):
        #获取失衡节点的平衡因子
        balance_factor = self.balance_factor(node)
        #l 左偏树
        if balance_factor > 1:
            #是LL 还是LR:
            if self.balance_factor(node.left) >= 0:
                return self.right_rorate(node)
            else:
                #左孩子左旋
                node.left = self.left_rotate(node.left)
                #该节点右旋
                return self.right_rorate(node)
        #r 右偏树
        elif balance_factor < -1:
            #是RR 还是RL:
            if self.balance_factor(node.right) <= 0:
                return self.left_rotate(node)
            else:
                #右孩子右旋
                node.right = self.right_rorate(node.right)
                #该节点左旋
                return self.left_rotate(node)
            
        return node

AVL树常用操作

插入节点

与二叉搜索树的操作类似，不过要处理失衡节点。我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡。

1. 递归遍历树，找到插入位置，插入新节点。
2. 递归返回时，更新当前节点的高度
3. 检查当前节点的平衡因子，执行适当的旋转
4. 平衡后的子树返回给父节点，最终返回新的根节点。

def insert(self,val):
    self._root = self.insert_helper(self._root,val)
def insert_helper(self,node,val):
    if node is None:
        return TreeNode(val)
    if node.val == val:    
        return node
    
    if node.val < val:
        node.right = self.insert_helper(node.right,val)
    else:
        node.left = self.insert_helper(node.left,val)
    #更新高度
    self.update_height(node)
    #旋转
    return self.rotate(node)

  

删除节点

def remove(self,val):
    self._root = self.remove_helper(self._root,val)
def remove_helper(self,node,val):
    if node is None:
        return None
    if node.val < val:
        node.right = self.remove_helper(node.right,val)
    elif node.val > val:
        node.left = self.remove_helper(node.left,val)
    else:
        #有0/1个子节点
        if node.left is None or node.right is None:
            child = node.left or node.right
            return child
        else:
            tmp = node.right
            while tmp.left :
                tmp = tmp.left
            node.right = self.remove_helper(node.right,tmp.val)    
            node.val = tmp.val
    self.update_height(node)
    return self.rotate(node)   

习题

def height(root):
    if root is None:
        return 0
    return max(height(root.left),height(root.right))+1

二叉树相同，对称，平衡，右视图

• 相同(p,q,为treenode)

  def is_same(p,q):
      if p is None or q is None:
          return p is q
      return p.val == q.val and self.is_same(p.left,q.left) and
  self.is_same(p.right,q.right)

• 对称（相较于相同，把最后改成对比左右）

  def is_same(p,q):
      if p is None or q is None:
          return p is q
      return p.val == q.val and self.is_same(p.left,q.right) and self.is_same(p.right,q.left)
  def is_symmetric(self,root):
      return is_same(root.left,root.right)

• 平衡

  def isblance(root):
      def get_height(node):
          if node is None :
              return 0 
          left_height = get_height(node.left)
          if left_height == -1:
              return -1
          right_height = get_height(node.right)
          if right_height == -1 or abs(left_height - right_height) >1:
              return -1
          return max(left_height,right_height) + 1
      return get_height(root) != -1

• 右视图（深度等于答案长度才添加进去,先递归调用右子树）

  左视图：先递归调用左子树

  def rightsideview(root):
      ans = []
      def f(node,depth):
          if node is None:
              return
          if depth==len(ans):
              ans.append(node.val)
          f(node.right,depth+1)
          f(node.left,depth+1)
      f(root,0)
      return ans

验证二叉树是不是二叉搜索树

• 前序遍历

  def isvalidbst(root,left= -inf,right = inf):
      if root is None :
          return True
      x = root.val
      return left < x < right and isvalidbst(root.left,left,x) and isvalidbst(root.right,x,right)

• 中序遍历（递增）

  def isvalidbst(root):
      pre = -inf
      if root is None:
          return True
      if not isvalidbst(root.left):
          return False
      if root.val < pre:
          return False
      pre = root.val
      
      return isvaildbst(root.right)

最近公共祖先

• 二叉树的公共祖先（公共许仙可以包含自己）

  

  def lowercommonancestor(root,p,q):
      if root is None or root is p or root is q:
          return root
      left = lowercommonancestor(root.left,p,q)
      right = lowercommonancestor(root.right,p,q)
      if left and right:
          return root
      if left :
          return left
      return right
   

  递归返回的结果的 p/q/none/最近公共祖先 返回谁代表着公共祖先在谁之上

• 二叉搜索树的最近公共祖先

  def  lowercommonancestor(root,p,q):
      x = root.val
      if p.val < x and q.val < x:
          return lowercommonancestor(root.left,p,q)
      if p.val > x and q.val > x:
          return lowercommonancestor(root.right,p,q)
      return root

---

堆

堆是一种满足特定条件的完全二叉树（只有底层节点未被排满）

• 小顶堆（min heap）：任意节点的值 ≤ 其子节点的值。
• 大顶堆（max heap）：任意节点的值 ≥ 其子节点的值。

特点：

• 最低层节点但靠左填充，其他层都是填满状态
• 二叉树的根节点为堆顶，底层靠右的节点为堆底

堆应用：

优先队列，出队入队为0（logn） 建队为0（n）

堆排序

获取最大的K个元素

在 Python 中，heapq 模块提供了对小顶堆的支持（默认实现）。但为了实现大顶堆，可以通过“将元素取负”来颠倒堆的大小关系。

堆的实现

• 堆的存储与表示

用数组来存储堆，节点指针通过索引映射公式来进行表示

def left(self, i: int) -> int:
    """获取左子节点的索引"""
    return 2 * i + 1

def right(self, i: int) -> int:
    """获取右子节点的索引"""
    return 2 * i + 2

def parent(self, i: int) -> int:
    """获取父节点的索引"""
    return (i - 1) // 2  # 向下整除

• 访问堆顶元素 （二叉树的根节点，也是列表的首个元素）

  def peek(self) -> int:
      """访问堆顶元素"""
      return self.max_heap[0] 

• 元素入堆

  val正常插入到堆底，维护堆的成立条件，修复从插入节点到根节点的路径上的各个节点 ——> 堆化

  逐个比较插入节点和父节点的值，交换两个节点的值 ——> 直到越过根节点

  def push(self,value):
      self.max_heap.append(value) #添加节点
      self.sift_up(self.size()-1) #从底部到顶部堆化
      
  def sift_up(self,index):
      #从节点imdex开始，从底部向上堆化
      while True:
          parent = self.parent(index)
          if parent <0 or self.max_heap[parent] >= self.max_heap[index]:
              break
          self.swap(parent,index)  #交换值
          index = parent  #更新下标

  while True 是一个无限循环，直到遇到break。

  while parent >= 0 and self.max_heap[parent] < self.max_heap[index] 等同逻辑

• 栈顶元素出栈

  1. 交换栈顶元素和栈底元素（交换更节电和最右边节点）
  2. 交换完成之后直接删除最末尾元素
  3. 然后从根节点开始，从顶部往底部堆化

  def pop(self):
      if self.is_empty():
          raise IndexError("堆为空")
      self.sawp(0,self.size()-1)
      val = self.max_heap.pop()
      self.sift_down(0)
      return val 
  def sift_down(self,index):
      while True:
          left = self.left(index)
          right = self.right(index)
          largest = index
          if left < self.size() and self.max_heap[left] >self.max_heap[largest]:
              largest = left
          if right < self.size() and self.max_heap[right] > self.max_heap[largest]:
              largest = right
          if largest == index:
              break 
          self.swap(largest,index)   #交换节点
          index = largest    #更新下标

  在向下堆化的过程中，需要将index 与左右孩子进行比较，把大值换上去。直到左右孩子都小于自己。我们设置了一个临时最大值，初始假设为本节点

建堆操作

借助入堆操作实现

建立空堆，在底部入堆（树： logn），对该元素执行从底部至顶部的堆化。(nlogn). 由于节点是从顶到底依次被添加进二叉树的，因此堆是“自上而下”构建的。

借助遍历堆化

1. 将列表所有元素原封不动地添加到堆中，此时堆的性质尚未得到满足。

2. 倒序遍历堆（层序遍历的倒序），依次对每个非叶节点执行“从顶至底堆化”。

每当堆化一个节点后，以该节点为根节点的子树就形成一个合法的子堆。而由于是倒序遍历，因此堆是“自下而上”构建的 倒序遍历—— 保证当前节点下面都是合理的堆。

叶子节点无需堆化

def __init__(self,nums):
   self.max_heap = nums
   for i in range(self.size()-1,-1,-1):
       self.down(i)

top-k 问题

给定长度为 n 的无序数组，返回数组中最大的 k个元素。

• 遍历k 次

  每次都取出当前最大元素

• 排序

  而后返回K个元素

• 堆

  1. 初始化一个小顶堆，其堆顶元素最小。
  2. 先将数组的前 k 个元素依次入堆。
  3. 从第 k+1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
  4. 遍历完成后，堆中保存的就是最大的 k 个元素

  import heapq
  def top_heap(nums,k):
      heap = []
      for i in range(k):
          heap.append(nums[i])
  
      for i in range(k,len(nums)):
          if nums[i] > heap[0]:
              heapq.heappop(heap)
              heapq.heappush(heap,nums[i])
      """for num in nums:
          if len(heap) <k:
              heapq.heappush(heap,num)            
          else:    
              if num > heap[0]:
                  heapq.heappop(heap)
                  heapq.heappush(heap,num) """
      return heap
                  

图

术语

图的表示

• 邻接矩阵

  图的顶点数量为 n ，邻接矩阵（adjacency matrix）使用一个 n×n 大小的矩阵来表示图。每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

  

以邻接矩阵作为图的表示,我们进行增删查改的操作效率会提高,但是空间复杂度也会提高

• 邻接表

  对于一个图.用n 个链表来表示图,链表的节点表示顶点,第i个链表对应顶点i,其中储存该顶点的所有邻接顶点.

  

邻接表与哈希表中的链式结构相似

图的基本操作

对邻接矩阵的操作

• 添加或删除边：直接在邻接矩阵中修改指定的边即可，使用 O(1) 时间。而由于是无向图，因此需要同时更新两个方向的边。
• 添加顶点：在邻接矩阵的尾部添加一行一列，并全部填 0 即可，使用 O(n) 时间。
• 删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将 (n−1)**2 个元素“向左上移动”，从而使用 O(n2) 时间。
• 初始化：传入 n 个顶点，初始化长度为 n 的顶点列表 vertices ，使用 O(n) 时间；初始化 n×n 大小的邻接矩阵 adjMat ，使用 O(n2) 时间。

class GraphAdjMat:
    def __init__(self,vertices:list,edges:list[list]):
        #每个边有两个顶点的索引组成。[0,1]，代表这两个顶点之间有一条边。
        self.vertices = []  #顶点列表，索引-->顶点索引。 值--> 顶点值
        self.adj_mat = [] #邻接矩阵，里面是每一行的元素
        
        #添加顶点
        for vertice in vertices:
            self.add_vertex(vertice)
        
        #添加边 
        for e in edges:
            self.add_edge(e[0],e[1])
        
    def size(self):
        return len(self.vertices)
    
    def add_vertex (self,val):
        n = self.size()
        #添加新顶点
        self.vertices.append(val)
        new_row = [0]*n 
        #添加新行
        self.adj_mat.append(new_row)
        #添加新列
        for row in self.adj_mat:
            row.append(0)
        
    def remove_vertex(self,index):
        if index > self.size()-1 :
            raise ValueError('顶点索引越界')
        #删除顶点
        self.vertices.pop(index)
        #删除行
        self.adj_mat.pop(index)
        #删除列
        for row in self.adj_mat:
            row.pop(index)
            
    def add_edge(self,i,j):
        if i < 0 or j <0 or i >= self.size()-1 or j >= self.size()-1 or i == j:
            raise ValueError('顶点索引越界')
        self.adj_mat[i][j] = 1
        self.adj_mat[j][i] = 1
    def remove_edge(self,i,j):
        if i < 0 or j <0 or i >= self.size()-1 or j >= self.size()-1 or i ==j :
            raise ValueError('顶点索引越界')
        self.adj_mat[i][j] = 0
        self.adj_mat[j][i] = 0
    def print(self):
        print("顶点：",self.vertices)
        print("邻接矩阵：")
        for row in self.adj_mat:
            print(row)
            

对邻接表的实现

• 添加边：在顶点对应链表的末尾添加边即可，使用 O(1) 时间。因为是无向图，所以需要同时添加两个方向的边。
• 删除边：在顶点对应链表中查找并删除指定边，使用 O(m) 时间。在无向图中，需要同时删除两个方向的边。
• 添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用 O(1) 时间。
• 删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用 O(n+m) 时间。
• 初始化：在邻接表中创建 n 个顶点和 2m 条边，使用 O(n+m) 时间。

列表来代替链表，哈希表来储存邻接表，键——> 顶点 值——>

与该顶点相连的所有顶点

class GraphAdjList:
    """基于邻接表实现的图"""
    
    def __init__(self,edges):
        self.adj_list = dict()
        
    def size(self):
        return len(self.adj_list)
    def add_edge(self,v1,v2):
        if v1 not in self.adj_list or v2 not in self.adj_list or v1 == v2:
            raise ValueError('顶点不存在/不能自环')
        self.adj_list[v1].append(v2)
        self.adj_list[v2].append(v1)
    def remove_edge(self,v1,v2):
        if v1 not in self.adj_list or v2 not in self.adj_list or v1 == v2:
            raise ValueError('顶点不存在')
        self.adj_list[v1].remove(v2)
        self.adj_list[v2].remove(v1)
        
    def add_vertex(self,v):
        if v in self.adj_list:
            raise ValueError("顶点已存在")
        self.adj_list[v] = []
    def remove_vertex(self,v):
        if v not in self.adj_list:
            raise ValueError("顶点不存在")
        self.adj_list.pop(v)
        #遍历其他顶点链表，删除所有包含vet 的边
        for key in self.adj_list:
            if v in self.adj_list[key]:
                self.adj_list[key].remove(v)
    def print(self):
        print("邻接表：")
        for key in self.adj_list:
            print(key,self.adj_list[key])
            

图的遍历

排序

评价维度

• 运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。

• 就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。

• 稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。

稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格，第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能导致输入数据的有序性丧失
自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。

任何需要转换或者以排序顺序保存的数据都将涉及项目的比较。

字符串按照ascll 码来进行排序
类中的比较，需要覆盖重写 __eq__ __gt__(相等，大于)函数

python 内置排序函数

sorted 函数

• 不会更改原有的可迭代对象（比如列表/字符串），而是生成一个新的列表/字符串/

  字符串仍然按照ascll 码
  sort 函数

• 仅仅对列表有用，会更改原有列表

排序

假设元素都是储存在类数组中，储存地址的是连续的，address = start+index也就是说里面的元素可以通过索引直接访问。
这个操作的复杂度为O(1) 可以用来实现 快速，归并，堆，插入等排序

选择排序

原理：
设数组的长度为 n ，选择排序的算法流程如下图所示。

1. 初始状态下，所有元素未排序，即未排序（索引）区间为 [0, n-1] 。
2. 选取区间 [0, n-1] 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
3. 选取区间 [1, n-1] 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
4. 以此类推。经过 n - 1 轮选择与交换后，数组前 n - 1 个元素已排序。
5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

def selection_sort(nums: list[int]):
    """选择排序"""
    n = len(nums)
    # 外循环：未排序区间为 [i, n-1]
    for i in range(n - 1):
        # 内循环：找到未排序区间内的最小元素 [i+1,n-1]
        k = i    
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j  # 记录最小元素的索引
        # 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[k] = nums[k], nums[i]

注意这里外层循环不考虑最后一个元素！！！只是循环不考虑，但是未排序的区间仍然是不变的
因为当排序进行到最后一步的时候，最后一个元素一定是最大的。 但是内层循环组要考虑，毕竟是从未排序的区间中找到最小的。
内层循环从i+1 开始的原因 ： 因为当前未排序区间的第一个元素已经是当前区间的最小值，不需要再次比较。

另外一种思路是

def selection_sort(values):
	  unsorted_len = len(values)
	  while unsorted_len >1:
        unsorted = values[:unsorted_len]
        largest = max(unsorted)
        index_largest = unsorted.index(largetst)
        swap2_compact(values,index_largest,unsorted_len-1)
        unsorted_len -=1
def swap2_compact(values,i,j):
    values[i],values[j] = values[j],values[i]

算法特性

时间复杂度为O(n**2)，非自适应排序
空间复杂度为O(1),原地排序
非稳定型排序

冒泡排序

通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

设数组的长度为 n ，冒泡排序的步骤如下图所示。

1. 首先，对 n 个元素执行“冒泡”，将数组的最大元素交换至正确位置。
2. 接下来，对剩余 n - 1 个元素执行“冒泡”，将第二大元素交换至正确位置。
3. 以此类推，经过 n - 1 轮“冒泡”后，前 n - 1 大的元素都被交换至正确位置。
4. 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。

def bubble_sort(nums: list[int]):
  """冒泡排序"""
  n = len(nums)
  #外循环：未排序区间为 [0, i]
  for i in range(n - 1, 0, -1):
      # 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端[0,i-1] 中找最大的，将其与 [i] 进行交换
      for j in range(i):
          if nums[j] > nums[j + 1]:
              # 交换 nums[j] 与 nums[j + 1]
              nums[j], nums[j + 1] = nums[j + 1], nums[j]

外层循环从len(nums)- 1 开始的原因是，当进行到最后一步的时候，一定是最小的元素被剩余下来。
与选择排序不同的是，在内层循环中没有用一个变量来记录最大值，因为冒泡排序只是牵涉相邻元素的交换。
内层循环不包括当前未排序区间的最后一位，因为当前未排序区间的最后一个元素已经是当前区间的最大值，不需要再次比较。

效率优化

设置一个标志位flag 来进行检测，如果某轮冒泡排序没有进行任何交换操作，说明该数组已经完成排序，可以直接返回结果。

def dubble_sort_with_flag(nums:list[int]):
    n = len(nums)
    #外循环：未进行排序的区间为[0，i]
    for i in range(n-1,0,-1):
        flag = False
        # 内循环： 将未排序的区间中[0,i]中的最大元素交换到该区间的最右边
        for j in range(i):
            if nums[j] > num[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
                flag = true
            if not flag:
            	  break

算法特性

时间复杂度为O(n**2)
空间复杂度为O(1)，原地排序
稳定排序： 在冒泡中遇到相同元素不进行交换。

插入排序

工作原理与手动整理一副牌的过程相似。
也就是在未排序区间中选择一个基准元素，将该元素与其左侧已排序区间的元素注意比较大小，并将该元素插入到正确的位置。
设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。

1.初始状态下，数组的第 1 个元素已完成排序。 2.选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。 3.选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。 4.以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。

def insertion_sort(nums: list[int]):
  """插入排序"""
  # 外循环：已排序区间为 [0, i-1]
  for i in range(1, len(nums)):
      base = nums[i]
      j = i - 1
      # 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
      while j >= 0 and nums[j] > base:
          nums[j + 1] = nums[j]  # 将 nums[j] 向右移动一位
          j -= 1
      nums[j + 1] = base  # 将 base 赋值到正确位置

与选择排序，冒泡排序不同的是，插入排序更加关注已经排序的区间是多少。[0:i-1]
外层循环从1 开始的原因是，第一个元素时已经排好序的。
然后需要从前面暂时排好序的开始进行与基准情况进行比较（找到适合他的位置）

算法特性

时间复杂度O(n**2)
空间复杂度 原地排序
稳定排序

快速排序

是一种根据分治策略的排序算法。快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧

回溯

穷举所有可能性，遇到正解将其记录。

称之为回溯：在搜索的时候会采取 尝试 与回退 往前走不动的时候会撤销上一步的操作，退回到之前的状态。

二分查找

是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

需要注意的是，first 和last 都是int 类型，i+j 可能会超出int 类型的取值范围。所以mid = （i+（j-i））//2

有两种方法，一个使用循环，一个使用递归

def binary_search(nums: list[int], target: int) -> int:
  """二分查找（双闭区间）"""
  # 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
  i, j = 0, len(nums) - 1
  # 循环，当搜索区间为空时跳出（当 i > j 时为空）
  while i <= j:
      # 理论上 Python 的数字可以无限大（取决于内存大小），无须考虑大数越界问题
      m = (i + j) // 2  # 计算中点索引 m
      if nums[m] < target:
          i = m + 1  # 此情况说明 target 在区间 [m+1, j] 中
      elif nums[m] > target:
          j = m - 1  # 此情况说明 target 在区间 [i, m-1] 中
      else:
          return m  # 找到目标元素，返回其索引
  return -1  # 未找到目标元素，返回 -1

递归写法

def binary_search(nums,first,last,target):
    index = 0
    if first > last :
        return -1
    mid = (first + last)//2
    else: 
        mid = (first + last)//2
        if target > mid
            index = binary_search(nums,mid+1,last,target)
        elif target < mid :
            index = binary_search(nums,first,mid-1,target)
        else:
            return index = mid
    return index

局限性
仅仅适用于有序数组，在小数据中可以考虑新型查找。

二分查找插入点

二分查找不仅可用于搜索目标元素，还可用于解决许多变种问题，比如搜索目标元素的插入位置

无重复元素的情况

给定一个长度为 n的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引

• 问题一：当数组中包含 target 时，插入点的索引是否是该元素的索引？

题目要求将 target 插入到相等元素的左边，这意味着新插入的 target 替换了原来 target 的位置。也就是说，当数组包含 target 时，插入点的索引就是该 target 的索引。

• 问题二：当数组中不存在 target 时，插入点是哪个元素的索引？

进一步思考二分查找过程：当 nums[m] < target 时 ,first移动，这意味着指针first在向大于等于 target 的元素靠近。同理，指针last始终在向小于等于 target 的元素靠近。因此二分结束时一定有：first指向首个大于 target 的元素，last指向首个小于target 的元素。易得当数组不包含 target 时，插入索引为 first。

def binary_search_insertion_simple(nums: list[int], target: int) -> int:
  """二分查找插入点（无重复元素）"""
  i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
  while i <= j:
      m = (i + j) // 2  # 计算中点索引 m
      if nums[m] < target:
          i = m + 1  # target 在区间 [m+1, j] 中
      elif nums[m] > target:
          j = m - 1  # target 在区间 [i, m-1] 中
      else:
          return m  # 找到 target ，返回插入点 m
  # 未找到 target ，返回插入点 i
  return i

代码的思路很简单，也就是如果我们找到目标值，返回他的索引，如果没有找到，返回first （第一个大于目标索引的位置）的索引作为插入的位置

存在重复元素的情况

在上一题的基础上，规定数组包含重复元素

假设数组中存在多个 target ，则普通二分查找只能返回其中一个 target 的索引，而无法确定该元素的左边和右边还有多少 target。
题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个 target 的索引

考虑拓展二分查找的代码，整体的流程不变

• 当num[mid] < target 或者 num[mid] > target 的时候，操作不改变
  让first 和 last 往taregt 的方向靠近

• 当num[mid] == target 说明小于target 的元素在区间[first,m-1]中，因此采用j=m-1 来进行缩小去边，使得last 向小于target 的元素靠近。

• 在实际的代码中，当target < nums[mid] 的操作与 target == nums[mid] 的操作相同，可以合成。

循环完成之后，first 会指向最左边的target ，j 指向首个小于target 的元素。first 就是插入点

def binary_search_insertion(nums: list[int], target: int) -> int:
  """二分查找插入点（存在重复元素）"""
  i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
  while i <= j:
      m = (i + j) // 2  # 计算中点索引 m
      if nums[m] < target:
          i = m + 1  # target 在区间 [m+1, j] 中
      elif nums[m] > target:
          j = m - 1  # target 在区间 [i, m-1] 中
      else:
          j = m - 1  # 首个小于 target 的元素在区间 [i, m-1] 中
  # 返回插入点 i
  return i

代码的逻辑也是很清晰，当我们找到一个target 的时候是不会返回索引，而是缩减区间，继续向左边界搜索，直到最后，first 指向最左边的目标元素的位置。

二分查找边界

给定一个长度为n 的有序数组nums ，其中可能包含重复元素。请返回数组最左边一个元素target 的索引。若数组中不包含该元素，则返回-1

查找左边界

查找左边界实际上就是查找最左边的一个目标的索引，也就是我们可以使用上面寻找插入点的函数实现左边界。

但是需要注意的是，寻找插入点的时候，我们不管她有没有这个元素，都会返回一个适合她的索引。而这一题要求的是，当没有给元素的时候要返回-1

没有该元素的时候会有两种情况：

• 插入点的索引越界

• 元素nums[i] 与target 不相等

  def binary_search_left_edge(nums: list[int], target: int) -> int:
    """二分查找最左一个 target"""
    # 等价于查找 target 的插入点
    i = binary_search_insertion(nums, target)
    # 未找到 target ，返回 -1
    if i == len(nums) or nums[i] != target:
        return -1
    # 找到 target ，返回索引 i
    return i

寻找右边界

最直接的办法是修改寻找插入点 函数代码中 当num[mid] == target 的时候的边界缩减的方向。

• 可以将其转化为查找最左边的数值为target+1 的索引。这个时候last 所指向小于等于目标元素的位置，所以最后结果返回last

def binary_search_right_edge(nums: list[int], target: int) -> int:
  """二分查找最右一个 target"""
  # 转化为查找最左一个 target + 1
  i = binary_search_insertion(nums, target + 1)
  # j 指向最右一个 target ，i 指向首个大于 target 的元素
  j = i - 1
  # 未找到 target ，返回 -1
  if j == -1 or nums[j] != target:
      return -1
  # 找到 target ，返回索引 j
  return j

当目标元素不存在的时候，first 和 last 分别会指向首个大于，小于 该目标元素的元素

• 转化为查找元素
  查找最左一个 target ：可以转化为查找 target - 0.5 ，并返回指针 first

查找最右一个 target ：可以转化为查找 target + 0.5 ，并返回指针 last