堆、堆排序、基数排序、暴力递归、哈希结构

堆

堆通常是一个可以被看做一棵完全二叉树的数组对象。优先级队列结构，就是堆结构。

性质

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

heap insert

# 当前位置i与其父位置int((i-1)/2)进行交换，若大于其父位置则交换
# 某个数现处在index位置
def heap_insert(arr, index):
    p_index = int((index-1)/2)
    while arr[index] > arr[p_index]:
        arr[index], arr[p_index] = arr[p_index], arr[index]
        index = p_index

heapify

# 某个数在index位置
def heapify(arr, index, heapsize):
    left = index * 2 + 1 # 左孩子位置
    while left < heapsize:
        # 两个孩子中，谁的值大，把下标给largest
        if (left + 1) < heapsize and arr[left+1] > arr[left]:
            largest = left + 1
        else:
            largest = left
        # 父和孩子之间，谁的值大把下标给largest
        if arr[index] > arr[largest]:
            largest = index
        if largest == index:
            break
        arr[index], arr[largest] = arr[largest], arr[index]
        index = largest
        left = index * 2 + 1

堆排序

def heapsort(arr):
    if arr == [] or len(arr) < 2:
        return 
    # 将arr数组中的数字从0-len(arr)进行len(arr)次heapinsert
    for i in range(len(arr)):
        heap_insert(arr, i)
    heapsize = len(arr)
    arr[0], arr[heapsize-1] = arr[heapsize-1], arr[0]
    heapsize -= 1
    while heapsize > 0:
        heapify(arr, 0, heapsize)
        arr[0], arr[heapsize-1] = arr[heapsize-1], arr[0]
        heapsize -= 1

heapinsert过程优化

def heapsort1(arr):
    if arr == [] or len(arr) < 2:
        return 
#     for i in range(len(arr)):
#         heap_insert(arr, i)
    # 将n部自顶向下的heapinset  改为  自底向上进行heapify过程  
    # 该步骤中的时间复杂度由O(NlogN)  变为O(N)   此过程将整个数组变为了大根堆
    for i in range(len(arr))[::-1]:
        heapify(arr, i, len(arr))
    heapsize = len(arr)
    arr[0], arr[heapsize-1] = arr[heapsize-1], arr[0]
    heapsize -= 1
    while heapsize > 0:
        heapify(arr, 0, heapsize)
        arr[0], arr[heapsize-1] = arr[heapsize-1], arr[0]
        heapsize -= 1

python中的堆结构heapq
Python 堆（Headp） - lwp-boy - 博客园 (cnblogs.com)

# 使用heappush向堆中追加元素
import heapq
heap = []
for item in [2,3,4,1]:
  heapq.heappush(heap, item)
print(heap)
# 根据链表构建一个堆 --- heapify
li = [2,3,1,4]
heapq.heapify(li)
print(li)
# 返回堆中最大的元素 --- nlargest
print(heapq.nlargest(li, 2))   # 输出[4,3]

系统提供的堆结构是一个黑盒，与其的交互就是，向堆结构中追加元素（heappush）和返回堆中的最大元素（nlargest）

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

例子:

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中,接下来将这些桶子中的数值重新串接起来得到新的数列
接着再进行一次分配，这次是根据十位数来分配，将这些桶子中的数值重新串接起来得到新的数列为已经排序完毕的的数列。

def get_digit(val, d):
    '''获取val第d位的数字'''
    for i in range(d):
        val /= 10
    return int(val%10)

def radix_sort(arr, digit):
    '''
    digit：排序的位数
    '''
    radix = 10
    bucket = [0] * len(arr)
    for d in range(digit):
        count = [0] * radix
        # 使用count数组计算第d位上0-9出现的次数
        for val in arr:
            j = get_digit(val, d)
            count[j] += 1
        # count数组记录第d位上小于等于val的数出现的次数
        for idx, val in enumerate(count[1:]):
            count[idx+1] = count[idx] + val
        # 根据count数组和第d位数字计算出该数字所在的位置，将其存储于bucket中，count中相应位置的数-1
        for val in arr[::-1]:
            j = get_digit(val, d)
            bucket[count[j]-1] = val
            count[j] -= 1
        for idx, val in enumerate(bucket):
            arr[idx] = val
    return arr    
        
if __name__ == '__main__':
    arr = [13,21,11,52,64]
    a = radix_sort(arr, 2)
    print(a)

暴力递归

打印一个字符串的全部子序列，包括空字符串

# 当前来到i位置，要和不要2条路
# 之前的选择形成的结果是arr
def process(arr, i, res):
  if i == len(arr):
    print(res)
    return 
  process(arr, i+1, res) # 当前位置不加入结果中
  process(arr, i+1, res+arr[i])  # 当前位置加入结果中

if __name__ == '__main__':
  arr = 'abc'
  process(arr, 0, '')

2.打印一个字符串的全部排列，要求不要出现重复的排列

def process(arr, i):
  if i == len(arr):
    print(''.join(arr))
    return
  visited = [0] * 26
  for j in range(i, len(arr)):
    if !visited[arr[j] - 'a']:
      arr[i], arr[j] = arr[j], arr[i]
      process(arr, i+1)
      arr[i], arr[j] = arr[j], arr[i]

1. 先手函数

if l == r return arr[l]

先手拿走左边纸牌
arr[l] + (l+1,r)上的后手
先手拿走右边纸牌
arr[r] + (l, r-1)上的后手
从2者中选择最大值

2. 后手函数

l == r return 0

若先手拿走l位置，则
(l+1,r)上的先手
若先手拿走r位置，则
（l, r-1)上的先手
从2者中选择最小值，因为是后手别人会留下差的牌

# 先手函数
def f(arr, l, r):
  if l == r:
    return arr[l]
  return max(arr[l] + s(arr, l+1, r), arr[r]+s(arr, l, r-1))

# 后手函数
def s(arr, l, r):
  if l == r:
    return 0
  return min(f(arr, l+1, r), f(arr, l, r-1))

def win(arr):
  if not arr or len(arr) == 0:
    return None
  return  max(f(arr, 0, len(arr)-1), s(arr, 0, len(arr)-1))

给你一个栈，逆序这个栈，不能申请额外的数据结构，只能使用递归函数

def f(stack):
  res = stack.pop()
  if not stack:
    return res
  else:
    last = f(stack)
    stack.append(res)
    return last

def reverse(stack):
  if not stack:
    return
  val = f(stack)
  reverse(stack)
  stack.append(val)

 if __name__ == '__main__':
    l = [1,2,3]
    reverse(l)
    print(l)

5.规定1和A对应，2和B对应，3和C对应...
那么一个数字字符串比如“111”，就可以转化为"AAA","KA","AK"。
给定一个只有数字字符串组成的字符串str,返回有多少种转化结果。

# i之前的位置，如何转化已经做过决定了
# i...有多少种转化的结果
def process(str, i):
  if i == len(str):
    return 1
  if str[i] == '0':
    return 0
  if str[i] == '1':
    res = process(str, i+1)  # i作为单独的部分，后续有多少方法
    if i+1 < len(str):
      res += process(str, i+2) # i和i+1作为单独的部分，后续有多少方法
  if str[i] == '2':
    res = process(str, i+1)
    if i+1 < len(str) and '0' <= str[i+1] <= '6':
      res += process(str, i+2) 
  # str[i] == '3' ~ '9'
  return process(str, i+1)

N皇后问题
是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上。给定一个整数n，返回n皇后的摆法有多少种。
n=1，返回1。
n=2或3，无论怎么摆都不行，返回0。
n=8，返回92.

# N皇后
def num(n):
  if n < 1:
    return 0
  record = [0] * n # 第i行的皇后，放在了第几列
  print(record)
  return process(0, record, n)

# n=1，返回1。
# n=2或3，无论怎么摆都不行，返回0。
# n=8，返回92.
def process(r, record, n):
  # 之前做的选择全在record里面，每点一个皇后，要保证与record与之前每一个皇后不共列，不共行，不共斜线
  if r == n:
    return 1
  res = 0
  # 来到第i行，在0-n-1列上去尝试
  for c in range(n):
    print(is_valid(record, r, c))
    print(record)
    if is_valid(record, r, c):
      record[r] = c # 第r行中，第c列点上皇后
      
      res += process(r+1, record, n)
      print(res)
  return res

# 0-r-1上已经点了皇后，
# 返回i行皇后放在了j列是否有效
def is_valid(reocrd, r, c):
  for i in range(r):
    # 0-r-1已点皇后，r行尝试点的皇后是否与以前的共列或者
    if reocrd[i] == c or abs(reocrd[i] - c) == abs(r - i):
      return False
  return True



if __name__ == '__main__':
  n = 8
  print(num(n))

某一行点一个皇后之后，得到一个列限制，一个左斜线限制，一个右斜线限制，求或之后得到总的限制，未限制位置可以尝试点皇后

# 不要超过32皇后问题
def num2(n):
  if n<1 or n>32:
    return 0
  if n==32:
    limit = -1
  else:
    limit = (1<<n) - 1
  return process2(limit, 0, 0, 0) 

def process2(limit, col_lim, leftdia_lim, rightdia_lim):
  if col_lim == limit:
    return 1
  pos = limit & (~(col_lim | leftdia_lim | rightdia_lim))
#  res = 0
  while pos != 0:
    # 提取最右侧的1
    most_right_one = pos & (~pos + 1)
    pos -= most_right_one
    res += process2(limit, col_lim | most_right_one, 
    (leftdia_lim | most_right_one) << 1,
    (rightdia_lim | most_right_one) >> 1)
  return res

与哈希函数有关的结构

哈希函数

均匀性
哈希冲突
same in same out

MD5: $0-2 ^{ 64} - 1$
SHA1: $0-2^{128}-1$

应用1：

一个大文件有40亿个无符号数(0~ $2^{32}-1$ ),1G内存，输出出现次数最多的数字？

分析：

使用字典，key,value均采用整数，则至少占用8字节，若40亿个数均不同，则占用320字节，即32G的空间

使用hash函数改进方法：

将40亿个数，通过哈希函数得到一个值，然后对得到的哈希值对100求模，相同的数会分到相同的文件，不同的数由于哈希函数的均匀性，最终得到的100个文件的规模大小差不多，然后用字典统计每一个文件的出现次数最多的数字，此时占用内存为32/100G<1G。从100个文件中得到100个出现次数最多的数，在从这100个数中选出出现次数最多的数字。

哈希表的实现
扩容，哈希表采用拉链表的方式实现，链表长度大于一定值后就扩容。
假设链表为2就扩容，则扩容次数的复杂度为O(logN)，实际链表长度会大于2,但是扩容次数的复杂度也是O(logN)级别的。扩容的代价为O(N)，扩容后每一个值都要重新计算哈希值，所以扩容代价为O(NlogN),加了N个字符串，总的代价为O(NlogN)，单次扩容代价为O(logN)。

2. 设计RandomPool结构

import random

def insert(key_index, index_key, key,size):
  if key not in key_index:
    key_index[key] =size
    index_key[size] = key
    size += 1

def get_random(index_key, size):
  if size == 0:
    return None
  random_idx = int(random.random()*size)
  return index_key[random_idx]
  
def delete(key_index, index_key, key,size):
  if key in key_index:
    delete_idx = index_key[key]
    last_key = index_key[size-1]
    key_index[last_key] = delete_idx
    index_key[delete_idx] = last_key
    del key_index[key]
    del index_key[size-1]
    
if __name__ == '__main__':
  key_index = {}
  index_key = {}
  size = 0

详解布隆过滤器

一个集合，元素有加入和查询，没有删除。bit类型的数组

可以使用基础类型的数组，通过操作可以是实现位图的效果。

位图bit map

int[] arr = new int[10]; // 表示10*32bits
// 想获取第178个bit的状态
int i = 178;
int num_index = i/32; // 178bit在第几个数中
int bit_index = i % 32; // 178bit在第几位中
// 拿到178位的状态
int s = (arr[num_index] >> bit_index) && 1;
// 修改178位的状态为1
arr[num_index] = arr[num_index] | (1 << bit_index);
// 修改178位的状态为0
arr[num_index] = arr[num_index] & (~(1 << bit_index));

布隆过滤器

定义1个m个长度的位图

对一个元素，经过k个哈希函数，得到的k个值，分别对m取模，将其在位图中的索引值标为1。最终得到所有的元素在位图中的位置。加入过程
查询过程：对元素，通过哈希函数和取模运算，得到的值如果位图中的值均为1，说明元素在位图中。

image

n 样本量，p 失误率

布隆过滤器要点

不允许删除的集合。 2. 允许有失误率