Python算法与数据结构

《Python服务端工程师面试宝典-PegasusWang》学习笔记,第二章:内置算法与数据结构、数据结构题目解析
305阅读 · 2020-5-25 20:21发布

内置算法与数据结构

常用的内置算法和数据结构有哪些?

  • sorted
  • dict/list/set/tuple...
数据结构/算法 语言内置 内置库
线性结构 list(列表) / tuple(元组) array(数组,不常用)/collections.namedtuple
链式结构 collections.deque(双端队列)
字典结构 dict(字典) collections.Counter(计数器)/OrderedDict(有序字典)
集合结构 set(集合)/frozenset(不可变集合)
排序算法 sorted
二分算法 bisect模块
堆算法 heapq模块
缓存算法 functools.lru_cache(Least Recent Used,python3)

collections模块常用扩展

  • namedtuple():通过名称访问tuple。
  • deque:双端队列。
  • Counter:计数器。
  • OrderedDict:有序字典。
  • defaultdict:有初始化的字典。

Python dict底层结构

  • 为了支持快速查找使用了哈希表作为底层结构。
  • 哈希表平均查找时间复杂度为O(1)
  • CPython解释器使用二次探查解决哈希冲突问题。
  • 哈希表如何解决哈希冲突:链接法、探查法
  • 哈希表是如何扩容的:当向容器添加元素的时候,会判断当前容器的元素个数,如果大于等于阈值---即当前数组的长度乘以加载因子的值的时候,就要需要扩容。扩容(resize)就是重新计算容量。

Python list/tuple区别

  • 都是线性结构,支持下标访问。
  • list是可变对象,tuple保存的引用不可变。
  • list没法作为字典的key,tuple可以(可变对象不可hash)

什么是LRUCache?

  • Least-Recently-Used替换掉最近最少使用的对象。
  • 缓存剔除策略,当缓存空间不够k用的时候需要一种方式剔除key。
  • 常用的策略是LRU(最近使用时间距今最久)、LFU(最近使用次数最少)等。
  • LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现。

如何实现LRUCache?

  • 使用dict做当做k/v键值对的缓存。
  • collections.OrderedDict实现更新最近访问的key。
  • 实现LRUCache,示例:

    from collections import OrderedDict
    
      class LRUCache:
          def __init__(self, capacity=128):  # 容量表示最多128个key/value存在
              self.od = OrderedDict()
              self.capacity = capacity
    
          def get(self,key):  # 获取元素,并把使用的元素放到最右边
              if key in self.od:
                  val = self.od[key]
                  self.od.move_to_end(key)  # 把获取的元素放到最右边
                  return val
              else:
                  return -1
    
          def put(self,key,value):  # 存放元素
              if key in self.od:
                  del self.od[key]
                  self.od[key] = value  # 默认放到最右
              else:
                  self.od[key] = value
                  if len(self.od) >= self.capacity:  # 判断容量是否已满
                      self.od.popitem(last=False)  # 剔除最早的元素
    

算法知识点

需要掌握的算法知识

  • 排序算法:冒泡排序、快速排序、归并排序、堆排序。
  • 线性查找、二分查找。
  • 独立实现代码(手写)、分析时间空间复杂度。

常用排序算法的时空复杂度

排序算法 最差时间分析 平均时间复杂度 稳定度 空间复杂度
冒泡排序 O(n^2) O(n^2) 稳定 O(1)
选择排序 O(n^2) O(n^2) 不稳定 O(1)
插入排序 O(n^2) O(n^2) 稳定 O(1)
快速排序 O(n^2) O(n*log2n) 不稳定 O(log2n)-O(n)
堆排序 O(n*log2n) O(n*log2n) 不稳定 O(1)

数据结构知识

常见的数据结构

  • 链表、队列、二叉树和堆。
  • 使用内置结构实现高级数据结构,比如内置的list/deque实现栈。

常见数据结构之链表

  • 链表有单链表、双链表、循环双端链表。
  • 实现插入节点、反转链表、合并多个链表等。
  • 反转链表。实现代码:

    class ListNode:
          def __init__(self,x):
              self.val = x
              self.next = None
    
      class Solution:
          def reverseList(self, head):
              pre = None
              cur = head
              while cur:
                  nextnode = cur.next
                  cur.next = pre
                  pre = cur
                  cur = nextnode
              return pre
    

常见数据结构之队列

  • 队列(queue)是先进先出结构。
  • 实现队列的apend和pop操作,做到先进先出。
  • 使用coolections.deque实现队列。实现代码:

    from collections import deque
      class Queue:
          def __init__(self):
              self.items = deque()
    
          def append(self,val):
              self.items.append(val)
    
          def pop(self):
              return self.items.popleft()
    
          def empty(self):
              return len(self.items) == 0
    
      def test_queue():
          q = Queue()
          q.append(0)
          q.append(1)
          q.append(2)
          print(q.pop())
          print(q.pop())
          print(q.pop())
    
      test_queue()
    

常见数据结构之栈

  • 栈(stack)是后进先出结构。
  • 实现栈的push和pop操作,做到后进先出。
  • 使用collections.deque实现栈。实现代码:

    from collections import deque
      class Stack:
          def __init__(self):
              self.items = deque()
    
          def push(self,val):
              self.items.append(val)
    
          def pop(self):
              return self.items.pop()
    
      def test_queue():
          q = Stack()
          q.push(0)
          q.push(1)
          q.push(2)
          print(q.pop())
          print(q.pop())
          print(q.pop())
    
      test_queue()
    

常见数据结构之字典与集合

  • Python dict/set 底层都是哈希表。
  • 哈希表的实现原理,底层其实就是一个数组。
  • 根据哈希函数快速定位一个元素,平均查找O(1),非常快。
  • 不断加入元素会引起哈希表重新开辟空间,拷贝之前元素到新数组。

哈希表如何解决冲突?

  • 链接法:元素key冲突之后使用一个链表填充相同key的元素。(数组里放链表)
  • 开放寻址法:冲突之后根据一种方式(二次探查)寻找下一个可用的槽。(例如x^2+y)
  • cpython使用的是二次探查。

常见数据结构之二叉树

  • 分为先序、中序、后序遍历。
  • 先(根)序:先处理根,之后是左子树,然后是右子树。
  • 中(根)序:先处理左子树,然后是根,然后是右子树。
  • 右(根)序:先处理左子树,然后是右子树,最后是根。
  • 先序遍历。实例代码:

    class BinTreeNode(object):
          def __init__(self,data,left=None,right=None):
              self.data,self.left,self.right = data,left,right
    
      class BinTree(object):
          def __init__(self,root):
              self.root = root
    
          """ 先(根)序遍历 """
          def preorder_trav(self,subtree):
              if subtree is not None:
                  print(subtree.data)
                  self.preorder_trav(subtree.left)
                  self.preorder_trav(subtree.right)
    

常见数据结构之堆

  • 堆是完全二叉树,有最大堆和最小堆。
  • 最大堆:对于每个非叶子节点V,V的值都比它的两个孩子大。
  • 最大堆支持每次pop操作获取最大的元素,最小堆获取最小元素。
  • 获取前X个最大的元素。实例:

    import heapq
      class TopK:
          def __init__(self,iterable,k):
              self.minheap = []  # 最小堆
              self.capacity = k  # 获取前k个
              self.iterable = iterable
    
          def push(self,val):
              if len(self.minheap) >= self.capacity:
                  min_val = self.minheap[0]
                  if val > min_val:
                      heapq.heapreplace(self.minheap,val)  # 将val放入堆,并调整位置
              else:
                  heapq.heappush(self.minheap,val)
    
          def get_topk(self):
              for i in self.iterable:  # 该代码暂时放在这,重复调用get_topk会导致重复计算
                  self.push(i)  # 调用push方法计算堆
              return self.minheap
    
      def test():
          import random
          i = list(range(1000))
          random.shuffle(i)
          print(i)
          _ = TopK(i,10)
          print(_.get_topk())
    
      test()
    

数据结构题目解析

链表

  • 链表涉及指针操作。
  • 删除一个链表节点:将目标x的next的值替换掉x。

    class ListNode:
          def __init__(self,x):
              self.val = x
              self.next = None
    
      class Solution:
          def deleteNode(self,n):
              nextnode = n.next
              after_next_next = n.next.next
              n.val = nextnode.val
              n.next = after_next_next
    
  • 合并两个有序链表:使用两个指针进行比较。

    class ListNode:
          def __init__(self,x):
              self.val = x
              self.next = None
    
      class Solution:
          def mergeTwoLists(self,l1,l2):
              root = ListNode(None)
              cur = root
              while l1 and l2:
                  if l1.val < l2.val:
                      node = ListNode(l1.val)
                      l1 = l1.next
                  else:
                      node = ListNode(l2.val)
                      l2 = l2.next
                  cur.next = node
                  cur = node
              cur.next = l1 or l2
    
  • 反转链表:将next和pre前后调换,调换后将当前指针指向之前定义的next。示例:

    # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          def reverseList(self, head: ListNode) -> ListNode:
              cur,pre = head,None
              while cur:
                  cur.next,cur,pre=pre,cur.next,cur
                  # 等同于
                  #tmp = cur.next
                  #cur.next=pre
                  #pre=cur
                  #cur=tmp
              return pre
    

二叉树

  • 二叉树涉及到递归和指针操作。
  • 二叉树的镜像:如果左孩子和右孩子不为空则交换。

    class ListNode:
          def __init__(self,x):
              self.val = x
              self.next = None
    
      class Solution:
          def invertTree(self,root):
              if root:
                  root.left,root.right = root.right,root.left
                  self.invertTree(root.left)
                  self.invertTree(root.right)
              return root
    
  • 层序遍历二叉树(广度优先)

    class ListNode:
          def __init__(self,x):
              self.val = x
              self.next = None
    
      class Solution:
          def levelOrder(self,root):
              if not root:
                  return []
              res = []
              cur_nodes = [root]
              next_nodes = []
              res.append([i.val for i in cur_nodes])
              while cur_nodes or next_nodes:
                  for node in cur_nodes:
                      if node.left:
                          next_nodes.append(node.left)
                      if node.right:
                          next_nodes.append(node.right)
                  if next_nodes:
                      res.append([i.val for i in next_nodes])
                  cur_nodes = next_nodes
                  next_nodes = []
              return res
    

栈与队列

  • 后进先出和先进先出。
  • 用栈实现队列:

    from collections import deque
    
      class Stack:
          def __init__(self):
              self.items = deque()
    
          def push(self,val):
              return self.items.append(val)
    
          def pop(self):
              return self.items.pop()
    
          def top(self):
              return self.items[-1]
    
          def empty(self):
              return len(self.items) == 0
    
      class MyQueue:
    
          def __init__(self):
              self.s1 = Stack()
              self.s2 = Stack()
    
          def push(self,x):
              self.s1.push(x)
    
          def pop(self):
              if not self.s2.empty():
                  return self.s2.pop()
              while not self.s1.empty():
                  val = self.s1.pop()
                  self.s2.push(val)
              return self.s2.pop()
    
          def peek(self):
              if not self.s2.empty():
                  return self.s2.top()
              while not self.s1.empty():
                  val = self.s1.pop()
                  self.s2.push(val)
              return self.s2.pop()
    
          def empty(self):
              return self.s1.empty() and self.s2.empty()
    
      def test():
          q = MyQueue()
          q.push(1)
          q.push(2)
          q.push(3)
          print(q.pop())
          print(q.pop())
          print(q.pop())
    
      test()
    

  • 堆常用在合并多个有序(数组/链表)。
  • 堆是完全二叉树,有最大堆和最小堆。
  • 使用python内置的heapq模块实现堆操作。
  • 合并k个有序链表:

    from heapq import heapify, heappop  # 用于构造最小堆
      class ListNode:
          def __init__(self,x):
              self.val = x
              self.next = None
    
      class Solution:
          def mergeKLists(self,lists):
              h = []
              for node in lists:
                  while node:
                      h.append(node.val)
                      node = node.next
                  heapify(h)
              if not h:
                  return None
              # 构造一个最小堆
              heapify(h)
    
              #构造链表
              root = ListNode(heappop(h))
              curnode = root
              while h:
                  nextnode = ListNode(heappop(h))
                  curnode.next = nextnode
                  curnode = nextnode
              return root
    
      import random
      test_1 = ListNode(1)
      cur = test_1
      print(cur.val,end="->")
      for i in range(3):
          nextnode = ListNode(random.randint(1,10))
          print(nextnode.val,end="->")
          cur.next = nextnode
          cur = nextnode
      print()
    
      test_2 = ListNode(1)
      cur = test_2
      print(cur.val,end="->")
      for i in range(3):
          nextnode = ListNode(random.randint(1,10))
          print(nextnode.val,end="->")
          cur.next = nextnode
          cur = nextnode
      print()
    
      test_3 = ListNode(2)
      cur = test_3
      print(cur.val,end="->")
      for i in range(3):
          nextnode = ListNode(random.randint(1,10))
          print(nextnode.val,end="->")
          cur.next = nextnode
          cur = nextnode
      print()
    
      s = Solution()
      result = s.mergeKLists([test_1,test_2,test_3])
      cur = result
      print("----------")
      while cur:
          print(cur.val,end="->")
          cur = cur.next
    

字符串

  • Python内置很多字符串操作,比如split、replace等。
  • 反转一个字符串(原地址修改):

    class Solution:
          def reverseString(self,s):
              beg = 0
              end = len(s) - 1
              while beg < end:
                  s[beg],s[end] = s[end],s[beg]
                  beg += 1
                  end -= 1
    
  • 判断一个数字是否是回文数:

    class Solution:
          def isPalindrome(self,x):
              if x <= 0:
                  return False
              s = str(x)
              beg,end = 0,len(s)-1
              while beg<end:
                  if s[beg] != s[end]:
                      return False
                  beg += 1
                  end -= 1
              return True
    
      def test():
          s = Solution()
          assert s.isPalindrome(121) is True
          assert s.isPalindrome(-1) is False
          assert s.isPalindrome(0) is False