图解算法笔记 - Pursue wisdom love fun

前言

最近，想了一下，好像有一年没刷题了，回顾去年刷的题和笔记，感觉忘的都差不多。于是找了本图解算法重新回顾一下，然后再去刷些题。这里记录一下笔记。

O

O(log n) 表示操作数，算法的运行时间不是以秒为单位，是以增速的角度度量的。

二分

class Solution:
    def search(self, nums, target):
        low = 0
        high = len(nums) - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                high = mid -1
            else:
                low = mid + 1
        return -1

选择

数组：在内存中，元素是连在一起的，一般预留位置，如果再加元素超过位置，就要重新申请内存。链表：元素可以存在任何地方，因为链表的每个元素都存储了下一个元素的地址。读取，插入，删除： O(1) O(n), O(n) O(1), O(n) O(1)

# O(n * 1/2 * n) => O(n * n)
def find_smallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def select_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))
    return new_arr

递归

递归(函数自身调用自己)一定要有基线条件，避免无限循环调用栈(先进后出)

快排

# O(nlog n) ~ O(n * n) 每层O(n) 共(O(log n) ~ O(n))层
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        mid = arr[0]
        left = [i for i in arr[1:] if i <= mid]
        right = [i for i in arr[1:] if i > mid]
        return quick_sort(left) + [mid] + quick_sort(right)

广度优先

解决1: A=>B 有路径吗 2:A=>B 哪条路径最短图由节点和边组成

# O(V+E) V顶点 E边数
from collections import deque
graph = {} # 图可以用字典表示，key表示节点，value表示邻居
graph['you'] = ['w', 'c', 'g']
graph['bob'] = ['tom', 'anuj']
graph['tom'] = []

def search(name):
    search_queue = deque()
    search_queue += graph['you'] # 先把我所有邻居加入队列
    searched = [] # 记录检查过的人，避免无限循环
    while search_queue: # 只要队列不为空
        person = search_queue.popleft() # 从第一个开始, 取出第一个
        if not person in searched:
            if person_is_seller(person): # 是, 返回成功
                print('{} is a seller'.format(person))
                return True
            else: # 否则, 将person的朋友加入队列尾部
                search_queue += graph[person]
                searched.append(person)
    return False

def person_is_seller(name):
    return name[-1] == 'm'

狄克思特拉

找出加权图中前往x的最短路径，找出到达的最快路径，只适用有向无环图，不适用包含负权边的图，包含负权边的可以用贝尔曼-福德算法关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径

# 需要3个字典，分别保存Graph, costs, parents
graph = {} # 保存节点的邻居和权重
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['fin'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5

graph['fin'] = {}

costs = {} # 保存节点的开销，从起点到该节点需要多长时间
costs['a'] = 6
costs['b'] = 2
costs['fin'] = float('inf') # 终点不确定，用无穷大表示

parents = {} # 保存节点的父节点
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None

processed = [] # 保存处理过的节点

node = find_lowest_cost_node(costs) # 找出花费最小的节点
while node is not None:
    cost = costs[node] # 花费
    neighbors = graph[node] # 邻居
    for n in neighbors.keys(): # 遍历邻居
        new_cost = cost + neighbors[n] # 更新邻居节点从我经过的花费
        if costs[n] > new_cost: # 和原来比较，如果大，就更新
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

def find_lowest_cost_node(costs):
    loweset_cost = float('inf')
    loweset_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < loweset_cost and node not in processed:
            loweset_cost = cost
            loweset_cost_node = node
    return loweset_cost_node

贪婪

每一步都采取最优的做法，最终得到的是全局最优解，但并非任何情况下都行之有效。 NP完全问题：计算所有的解，并从中选出最小/最短的那个，如旅行商问题和集合覆盖问题，采用近似算法

动态规划

动态规划先解决子问题，再逐步解决大问题，动态问题都是从一个表格开始的, 如背包问题、最长公共子串 https://blog.itswcg.com/2018-04/python-dynamic.html

K最近邻(KNN)

分类和回归垃圾邮件过滤器 -朴素贝叶斯分类器

其他

二叉查找树(左边的值小，右边大，查找类似二分(O(log n))) B树是一种特殊的二叉树分布式算法 MapReduce 布隆过滤器，是一种概率型数据结构，提供的答案不一定对，优点占用存储空间少所有的图算法都可以用线性规划来实现，Simplex算法

参考

https://github.com/itswcg/Books/blob/master/%E7%AE%97%E6%B3%95%E5%9B%BE%E8%A7%A3.pdf>