前言：
刷leetcode的时候发现，基础的算法不清楚的话，就很难实现工程。
还是打基础。
1. 数据结构：
栈 Stack
队列 Queue
链表 Linked List
数组 Array
哈希表 Hash Table
二叉树 Binary Tree
堆 Heap
并查集 Union Find
字典树 Trie
2. 算法：
2.1 算法列表
二分搜索 Binary Search
分治 Divide Conquer
宽度优先搜索 Breadth First Search
深度优先搜索 Depth First Search
回溯法 Backtracking
双指针 Two Pointers
动态规划 Dynamic Programming
扫描线 Scan-line algorithm
快排 Quick Sort
2.2 整理基础算法逻辑：
二分查找：有序数据，一步步从一半的位置判断：
def binary_search(list,item):
low=0
high=len(list)-1
### 开始二分查找：
while low<=high:
mid=int((low+high)/2)
guess=list[mid]
if guess==item:
return mid
elif guess>item:
high=mid-1
elif guess<itime:
low=mid+1
else :
print('next')
return None
时间复杂度计算：
[图片上传中...(image.png-93f478-1617875460466-0)]
image.png
递归：递归只是让解决方案更清晰，并没有性能上的优势
def quicksort(Array):
if len(Array)<2:
return Array
else:
pivot=Array[0]
print pivot
### 这里的小于等于主要是因为如果出现重复数值，要全部包含进来。
less=[i for i in Array[1:] if i<=pivot]
greater=[i for i in Array[1:] if i>pivot]
return quicksort(less)+[pivot]+quicksort(greater)
广度搜索
def search(name):
flag = 0
search_queue = deque() #创建一个队列
search_queue += graph["A"] # 将起点的一度关系结点加入队列
searched = [] # 记录检查过的人
string = "A" # 记录路径
while search_queue:
node = search_queue.popleft() # 取出队首第一个元素
if node not in searched: # 只在没有检查的时候看
if node == name:
string += "-->" + node
flag = 1
print(string)
return True
else:
string += "-->" + node
search_queue += graph[node] # 不是G，将该节点的一度关系结点加
入队列末尾
searched.append(node)
if flag == 1:
print(string)
else :
print(name,"not in graph")
from collections import deque
graph = {}
graph["A"] = ["B","C","D"]
graph["B"] = ["F"]
graph["C"] = ["G"]
graph["D"] = ["E"]
graph["E"] = []
graph["F"] = ["G"]
graph["G"] = []
search("G")
增加了class的代码，还是有点有趣的：
from collections import deque # 线性表的模块
# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
def __init__(self, *args, **kwargs):
self.order = [] # visited order
self.neighbor = {}
def add_node(self, node):
key, val = node
if not isinstance(val, list):
print('节点输入时应该为一个线性表') # 避免不正确的输入
self.neighbor[key] = val
# 宽度优先算法的实现
def BFS(self, root):
#首先判断根节点是否为空节点
if root != None:
search_queue = deque()
search_queue.append(root)
visited = []
else:
print('root is None')
return -1
while search_queue:
person = search_queue.popleft()
self.order.append(person)
if (not person in visited) and (person in self.neighbor.keys()):
search_queue += self.neighbor[person]
visited.append(person)
# 深度优先算法的实现
def DFS(self, root):
# 首先判断根节点是否为空节点
if root != None:
search_queue = deque()
search_queue.append(root)
visited = []
else:
print('root is None')
return -1
while search_queue:
person = search_queue.popleft()
self.order.append(person)
if (not person in visited) and (person in self.neighbor.keys()):
tmp = self.neighbor[person]
tmp.reverse()
for index in tmp:
search_queue.appendleft(index)
visited.append(person)
def clear(self):
self.order = []
def node_print(self):
for index in self.order:
print(index, end=' ')
if __name__ == '__main__':
# 创建一个二叉树图
g = Graph()
g.add_node(('A', ['B', 'C']))
g.add_node(('B', ['D', 'E']))
g.add_node(('C', ['F']))
# 进行宽度优先搜索
g.BFS('A')
print('宽度优先搜索:')
print(' ', end=' ')
g.node_print()
g.clear()
# 进行深度优先搜索
print('\n\n深度优先搜索:')
print(' ', end=' ')
g.DFS('A')
g.node_print()
print()
动态规划
动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。这意味着使用动态规划算法解决不了去巴黎玩的问题。
线性规划:
python里面的向量乘除法：
网友评论