需要烂熟于心的算法模板（快排，二分查找，树先序，中序，层序遍历）

1.快排

def partition(arr,low,high): povit = arr[low] while(low<high): while(low<high and arr[high]>=povit): high = high-1 if (low<high): arr[low]=arr[high] low=low+1 while(low<high and arr[low]<povit): low = low+1 if (low<high): arr[high]=arr[low] high=high-1 arr[low]=povit return low def quick_sort(arr,low,high): if (low<high): location = partition(arr,low,high) quick_sort(arr,low,location-1) quick_sort(arr,location+1,high) else: return

2.前K个最小值

def partition(arr,low,high): povit = arr[low] while(low<high): while(low<high and arr[high]>=povit): high = high-1 if (low<high): arr[low]=arr[high] low=low+1 while(low<high and arr[low]<povit): low = low+1 if (low<high): arr[high]=arr[low] high=high-1 arr[low]=povit return low def k_least_val (arr,k): if arr is None or k<=0 or k>len(arr): return start = 0 end = len(arr)-1 index = partition(arr, start, end) while index!=(k-1): #因为是前K个，所以只要0到第k-1个有序即可 if k<index: index = partition(arr,start,index-1) elif k>index: index = partition(arr,index+1,end) return arr[:k]

3.二叉树先序遍历

class tree_node(object): def __init__(self,val): self.val = val self.left = None self.right = None def preorder(root): if root is None: return [] p = root stack = [] result = [] while p or len(stack)>0: while p: stack.append(p) result.append(p.val) p=p.left p = stack.pop() p = p.right return result

4.二叉树中序遍历

class tree_node(object): def __init__(self,val): self.val = val self.left = None self.right = None def preorder(root): if root is None: return [] p = root stack = [] result = [] while p or len(stack)>0: while p: stack.append(p) p=p.left p = stack.pop() result.append(p.val) p = p.right return result

5.二叉树后序遍历

6.二叉树层次遍历

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def levelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if root is None: return [] stack = [] stack.append(root) res = [] while stack: tmp_res = [] tmp_st = [] for node in stack: if node.left: tmp_st.append(node.left) if node.right: tmp_st.append(node.right) tmp_res.append(node.val) res.append(tmp_res) stack = tmp_st return res

7.二分查找

def binary_search(arr,k): start,end = 0,len(arr)-1 while (start<=end): mid = start + (end-start)//2 //小心越界，所以不用 (start+end)//2 if (arr[mid]<k): start =mid+1 elif (arr[mid]>k): end = mid-1 else: return mid