python内置数据结构算法常考

常用的内置算法和数据结构

• sorted排序函数
• dict/list/set/tuple

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

算法常考题

排序+查找，重中之重

• 常考排序算法：冒泡排序、快速排序、归并排序、堆排序
• 线性查找，二分查找
• 能独立实现代码（手写），能够分析时间空间复杂度

排序算法中的稳定性

什么是排序算法的文档性

• 相同大小的元素在排序之后依然保持相对位置不变，就是稳定的
• r[i] = r[j] 且r[i]在r[j]之前，排序之后r[i]依然在r[j]之前
• 稳定性对于排序一个复杂结构，并且需要保持原有排序才有意义

快排

• 选择基准分割数组为两个子数组，小于基准和大于基准的
• 对两个子数组分别快排
• 合并结果

def quicksort(arr):
  if len(arr) < 2:
    return arr
  else:
    pivot_index = 0
    pivot = arr[pivot_index]
    less_part = [
      i for i in arr[pivot_index+1:] if i <= pivot
    ]
    great_part = [
      i for i in arr[pivot_index+1:] if i > pivot
    ]
  return quicksort(less_part) + [pivot]+ quicksort(great_part)

归并排序

合并两个有序数组

def merge_sorted_list(sorted_a, sorted_b):
  length_a ,length_b = len(sorted_a), len(sorted_b)
  a = b = 0
  new_sorted_seq = []

  while a< length_a and b < length_b:
    if sorted_a[a] < sorted_b[b]:
      new_sorted_seq.append(sorted_a[a])
      a += 1
    else:
      new_sorted_seq.append(sorted_b[b])
      b += 1
  if a<length_a:
    new_sorted_seq.extend(sorted_a[a:])
  else:
    new_sorted_seq.extend(sorted_b[b:])
  return new_sorted_seq

实现归并排序

def mergesort(arr):
  #递归出口
  if len(arr) <= 1:
    return arr
  else:
    mid = int(len(arr)/2)
    left_half = mergesort(arr[:mid])
    right_half = mergesort(arr[mid:])
    return merge_sorted_list(left_half, right_half)

实现堆排序

def heapsort_use_heapq(iterable):
  from heapq import heappush, heappop
  items = []
  for value in iterable:
    heappush(items, value)
  return [heappop(items for i in range(len(items)]

二分查找

def binary_search(sorted_array, val):
  if not sorted_array:
    return -1
  beg = 0
  end = len(sorted_array) - 1
  while beg <= end:
    mid = int((beg + end) / 2)
    if sorted_array[mid] == val:
      return mid
    elif sorted_array[mid] > val:
      end = mid - 1
    else:
      beg = mid + 1
  return -1 

python 数据结构常考题

python web后端常考数据结构

• 常见的数据结构链表、队列、栈、二叉树、堆
• 使用内置结构实现高级数据结构，比如内置的list/deque实现栈
• leetcode或者《剑指offer》上的常见题

数据结构链表

链表有单链表、双链表、循环双端链表

• 如何使用python来表示链表结构
• 实现链表常见操作，比如插入节点，反转链表，合并多个链表等
• leetcode练习常见链表题目

"""
反转链表
"""
class ListNode:
   def __init__(self, x):
    self.val = x
    self.next = None


class Solution:
  def reverseList(self, head):
    pre = None
    cur = head
    while cur:
      nextcode = cur.next
      cur.next = pre
      pre = cur
      cur = nextcode
    return pre

常考数据结构队列

队列先进先出结构

• 如何使用python实现队列
• 实现队列的append和pop操作，如何做到先进先出
• 使用python list 或者collections.deque实现队列

from collections import deque

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

  def append(self, val):
    return self.items.append(val)

  def pop(self):
    return self.items.popleft()

  def empty(self):
    return len(self.items) == 0

常考数据结构栈

栈是后进先出结构

• 如何实现python实现栈
• 实现栈的push和pop操作，如何做到后进先出
• 同样可以用Python list或者 collections.deque实现栈

from collections import deque

class Stack(object):
  def __init__(self):
    self.deque = deque()

  def push(self, value):
    self.deque.append(value)

  def pop(self):
    return self.deque.pop()

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

python dict/set底层都是哈希表

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

哈希表如何解决冲突

链接法和开发寻址法

• 元素key冲突之后使用一个链表填充相同key元素
• 开放寻址法是冲突之后根据一种方式（二次探查）寻找下一个可用的槽
• cpython实现二次探查

常考数据结构二叉树

先序、后序、后序遍历

• 先序：先处理根，之后是左子树，然后是右子树
• 中序：先处理左子树，然后是根，然后是右子树
• 后序：先处理左子树，然后是右子树，最后是根

树的遍历方式

先序遍历，其实很简单，递归代码里先处理根就好了

class BinTreeNode():
  def __init__(self,  data, left=None, right=None):
    self.data, self.left, self.right = data, left, right

class BinTree():
  def __init__(self, root = None):
    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操作获取最大的元素，最小堆获取最小元素
• 常见问题：用堆来完成topk问题，从海量数字中寻找最大的k个

import heapq

class TopK:
  """
  获取大量元素 topk 大个元素，固定内存
  思路：
  1、先放入元素前k个建立一个最小堆
  2、迭代剩余元素： 
    如果当前元素小于堆顶元素，跳过该元素
    否则替换堆顶元素为当前元素，并重新调整堆
  """
  def __init__(self, iterable, k):
    self.minheap = []
    self.capacity = k
    self.iterable = iterable

  def push(self, val):
    if len(self.minheap)>= self.capacity:
      min_val = self.minheap[0]
      if val < min_val:
        pass
      else:
        heapq.heapreplace(self.minheap, val)
    else:
      heapq.heappush(self.minheap, val)

  def get_topk(self):
    for val in self.iterable:
      self.push(val)
    return self.minheap