编程能力 算法框架python版 V1

算法通用模板整理

Posted by SunQH on September 3, 2021

算法模板总结

二分查找

二分查找框架

  • 基本原理:根据目标值所处的位置共分为三种查找情况,分别是:找任意位置、找左边界和找右边界。
  • 出题形式: 有序数组、$log(n)$复杂度。
  • 基本步骤
    1. 定义左右指针为数组两端。
    2. 当左指针小于右指针时,遍历:
      1. 中间指针为(l+r)//2
      2. 如果中间指针处数值小于目标值,收缩搜索区间为右半部分,
      3. 如果中间指针处数值大于目标值,收缩搜索区间为左半部分。
      4. 如果中间指针处数值等于目标值,返回当前位置。
  • 找中间模板
1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums:List[int], target:int):
  l, r = 0, len(nums)-1
  while l <= r:
    mid = (l+r)//2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    elif nums[mid] == target:
      return l
  return -1
  • 找左边界模板
1
2
3
4
5
6
7
8
9
10
11
12
13
def left_bound(nums:List[int], target:int):
  l, r = 0, len(nums)-1
  while l <= r:
    mid = (l+r)//2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    elif nums[mid] == target:
      r = mid - 1
  if l > len(nums)-1 or nums[l] != target:
	  return -1
  return l
  • 找右边界模板
1
2
3
4
5
6
7
8
9
10
11
12
13
def right_bound(nums:List[int], target:int):
  l, r = 0, len(nums)-1
  while l <= r:
    mid = (l+r)//2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    elif nums[mid] == target:
      l = mid + 1
  if r < 0 or nums[r] != target:
	  return -1
  return r

动态规划

动态规划框架

  • 基本原理:使用自底向上使用DP表来消除重叠子问题,从而优化时间复杂度。
  • 出题形式: 一般形式就是求最值,存在“重叠子问题”或存在“最优子结构”(比如求最⻓递增子序列、最小编辑距离等)
  • 基本步骤:
    1. 确定问题的 base case(最简单的情况)
    2. 确定问题的 状态 (原问题和子问题中的变量)
    3. 确定问题的 选择 (导致状态发生变化的行为)
    4. 确定 动态转移方程 的定义 (状态和选择的关系)
  • 算法框架
1
2
3
4
5
6
7
8
9
dp = [[0] * len(s2) for _ in range(len(s1))]  # 注意:是先j后i
# 确定 base case
dp[0][0][...] = base case 
# 确定 状态
for 状态1 in 状态1的取值:
	for 状态2 in 状态2的取值:
    # 确定 选择
    # 确定 状态转移方程
    dp[状态1][状态2][...] = 求最值(选择1,选择2,...)

二叉树

二叉树遍历框架

  • 基本原理: 明确一个节点要做的事情,然后剩下的事抛给框架。
  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
def traverse(root) :
    if not root: return None
	  # 节点 需要做什么在这里做, 其他的交给框架
    # 你的任务
    # 前序遍历位置
    traverse(root.left)
    # 中序遍历位置
    traverse(root.right)
    # 后序遍历位置
/* 基本的二叉树节点 */ 
class TreeNode {     
  int val;     
  TreeNode left, right; 
} 

void traverse(TreeNode root) {     
    // 前序遍历位置    
    traverse(root.left)     
    // 中序遍历位置    
    traverse(root.right)     
    // 后序遍历位置
}

二叉数的dfs遍历示例

  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def binaryTreePaths(self, root: TreeNode) -> List[str]:
  if not root: return []
  ans = []
  path = ''

  def dfs(root, path):
    if root: 
      # do sth
      path+=str(root.val)
      # 满足条件
      if not(root.left or root.right): 
        ans.append(path)
      # 不满足继续循环
      else:
        path += '->'
        dfs(root.left, path)
        dfs(root.right, path)

    dfs(root,path)
    return ans

二叉搜索树遍历框架

  • 基本原理:二叉搜索树(Binary Search Tree)中,任意节点的值要大于等于左子树所有节点的值, 且要小于等于右边子树的所有节点的值。 image-20210116112419058
  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
def BST(root:TreeNode, target:int):
  if root.val == target:
    # do something
  if root.val > target:
    BST(root.left, target)
  if root.val < target:
    BST(root.right, target)
  • 算法框架-C++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 基本的二叉树节点 */ 
class TreeNode {     
  int val;     
  TreeNode left, right; 
} 

void BST(TreeNode root, int target) {     
  if (root.val == target)         
    // 找到目标,做点什么    
  if (root.val < target)         
    BST(root.right, target);     
  if (root.val > target)         
    BST(root.left, target); 
} 

N 叉树遍历框架

  • 基本原理:二叉树框架可以扩展为 N 叉树的遍历框架:
  • 遍历框架
1
2
3
4
5
6
7
8
class TreeNode:
  def __init__(self, val, children):
    self.val = val
    self.children = chrildren
    
def traverse(root:TreeNode):
  for child in root.children:
    traverse(child)
/* 基本的 N 叉树节点 */ 
class TreeNode {     
  int val;     
  TreeNode[] children; 
} 

void traverse(TreeNode root) {     
  for (TreeNode child : root.children)         
    traverse(child) 
}

图遍历框架

  • 基本原理:N 叉树的遍历可以扩展为图的遍历, 因为图就是多个N叉棵树的结合体, 用布尔数组 visited 标记以防止重复访问。

链表

链表遍历框架

  • 算法框架-迭代遍历+递归
1
2
3
4
5
6
7
8
9
10
11
12
class ListNode:    
  def __init__(self, val=0, next=None):        
    self.val = val        
    self.next = next
  def traverse(head):		
    p = head    
    while p:            	
      # 迭代访问 p.val           	
      p = p.next
    def traverse(head):    
      # 递归访问 head.val         
      traverse(head.next)
  • 算法框架-迭代遍历+递归-C++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 基本的单链表节点 */ 
class ListNode {     
    int val;     
    ListNode next; 
} 
void traverse(ListNode head) {     
    for (ListNode p = head; p != null; p = p.next) {         
        // 迭代访问 p.val     
    } 
} 
void traverse(ListNode head) {     
    // 递归访问 head.val     
    traverse(head.next)
}

深度优先DFS

  • 基本原理:在for循环里进行递归,在递归调用之前做选择,在调用之后撤销选择。
  • 基本步骤
    1. 路径:已经做的选择
    2. 选择列表:当前可做的选择
    3. 结束条件:到达决策树底层,无法再做选择的条件

深度优先遍历框架

  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def backtrack(选择列表, path):
	if 满足结束条件:
    result.add(path)
    return 
  
  for 选择 in 选择列表:
    path.append(选择)
    backtrack(选择列表, path)
    path.pop()

result = []
path = []
backtrack(选择列表, path)
return result

带有visited 的 深度优先遍历框架

  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def DFS(选择列表, path):
	if 满足结束条件:
    result.add(path)
    return 
  
  visited.add(start)
  for 选择 in 选择列表:
    path.append(选择)
    backtrack(选择列表, path)
    path.pop()
  visited.remove(start)

visited = set()
result = []
path = []
DFS(选择列表, path)
return result

二叉树的 深度优先遍历示例

  • 基本原理:此时的选择只有左子树和右子树,而且无需用 visited 标记是否访问。
  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def dfs(root, targetSum):        
    if not root:
        return   # 注意 return  
    
    path.append(root.val)  # 添加路径
    
    targetSum -= root.val
    if not root.left and not root.right and targetSum == 0: # 如果满足条件
        res.append(path[:])        
    
    dfs(root.left, targetSum)
    dfs(root.right, targetSum)
    
    path.pop()  						# 注意要 去掉路径

res = []
path = []
dfs(root,targetSum)
return res

宽度优先BFS

宽度优先遍历框架

  • 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def BFS(start, target):
  q = []
  visited = {}
  
  q.append(start)  # 队列queue
  visited.add(start)  # 像二叉树一样的结构,没有子节点到父节点的指针,不会走回头路,就不需要visited
  step = 0
  
  while q:
    for _ in range(len(queue)):
      cur = q.pop(0)  # Notice is 0
      if cur is target:
        return step
      for x in cur.adj():  # 将 cur 的相邻节点加⼊队列
        if x not in visited:
          q.append(x)
          visited.add(x)
    step += 1  # 遍历完一层后step++
      
  • 算法框架-C++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q;  // 核⼼数据结构
    Set<Node> visited;  // 避免⾛回头路

    q.offer(start);  // 将起点加⼊队列
    visited.add(start);
    int step = 0;  // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点:这⾥判断是否到达终点 */
            if (cur is target) 
                return step; 
            /* 将 cur 的相邻节点加⼊队列 */ 
            for (Node x : cur.adj()) 
                if (x not in visited) { 
                    q.offer(x); 
                    visited.add(x); 
                } 
        }
        /* 划重点:更新步数在这⾥ */ 
        step++; 
    } 
}

双指针

快慢指针框架

  • 基本原理
  • 出题形式
    1. 判断是否有环
    2. 寻找环的起始节点
  • 基本步骤
    1. 找到相遇节点
    2. 让slow指向head
    3. slow和fast都一次一步
    4. 相遇节点即为起始节点(又走了k-m步)
  • 算法框架
1
2
3
4
5
6
slow = fast = head
while fast and fast.next:
  slow = slow.next
  fast = fast.next.next
  if fast == slow:
    return True

滑动窗口框架

  • 基本原理:使用滑动窗口的方式将枚举的时间复杂度从 $O(N^2)$ 减少至 $O(N)$。

    为什么是 O(N) 呢?这是因为在枚举的过程每一步中,「左指针」会向右移动一个位置(也就是题目中的 b),而「右指针」会向左移动若干个位置,这个与数组的元素有关,但我们知道它一共会移动的位置数为 O(N),均摊下来,每次也向左移动一个位置,因此时间复杂度为 O(N)。

    参考链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/

  • 出题形式:当我们需要枚举数组中的两个元素时,如果我们发现随着第一个元素的递增,第二个元素是递减的,那么就可以使用双指针的方法。

  • 算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def slidingWindow(s:str, t:str):
  need = set(c)
  window = set()
  
  left, right = 0, 0
  valid = 0  # 注意

  while right < len(s):
    # 增大窗口
    c = s[right]
    window.add(s[right])
    right += 1
    print("window:", left, right)
    while ...:  # window needs shrink
      # 缩小窗口
		  d = s[left]
      window.remove(s[left])
      left += 1

排序算法

  • 基本原理

    • 冒泡排序:逐个比较,最大的后移
    • 选择排序:遍历选择最小的,放到最前
    • 插入排序:发现小数字,向前交换(样本小且基本有序时,效率较高,效果好)
    • 希尔排序:改进的插入排序,间隔由大到小排序
    • 归并排序:最坏情况效果最好
    • 快速排序:速度快,效果好

    20190624173156.jpg

  • 出题形式:需要重点掌握快速排序、归并排序、插入排序和冒泡排序。

冒泡排序框架

  • 算法框架
1
2
3
4
5
6
def bubbleSort(nums):
    for i in range(len(nums)):
        # Last i elements are already in place
        for j in range(len(nums)-i-1):
 							if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

插入排序框架

  • 算法框架
1
2
3
4
5
6
7
8
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for ind in range(1,len(nums)):
            i = ind
            while i > 0 and nums[i] < nums[i-1]:
                nums[i], nums[i-1] = nums[i-1], nums[i]
                i -= 1
        return nums

堆排序框架

  • 基本原理: 先将待排序的序列建成大顶堆,使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素,我们将其与末尾元素交换,使末尾元素为最大值,然后再调整堆顶元素使得剩下的 n-1个元素仍为大根堆,再重复执行以上操作我们即能得到一个有序的序列。
  • 算法框架
1
2
3
4
5
6
7
8
9
10
# 使用heapq返回topk个数示例
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = collections.Counter(nums)
        h = []
        for key, val in counter.items():
            heapq.heappush(h, (val, key))
            if len(h) > k:
                heapq.heappop(h)
        return [x[1] for x in h]

heapq库使用参考链接:https://blog.csdn.net/brucewong0516/article/details/79042839

  • heappush(heap,n)数据堆入

    1
    2
    3
    4
    5
    
    #定义heap列表
    In [6]: heap = []
    #使用heapq库的heappush函数将数据堆入
    In [7]: for i in data:
       ...:     hq.heappush(heap,i)
    
  • heappop(heap)将数组堆中的最小元素弹出

    1
    2
    3
    4
    5
    
    In [11]: hq.heappop(heap)
    Out[11]: 0
      
    In [12]: hq.heappop(heap)
    Out[12]: 0.5
    
  • heapify(heap) 将heap属性强制应用到任意一个列表

    heapify 函数将使用任意列表作为参数,并且尽可能少的移位操作,,将其转化为合法的堆。如果没有建立堆,那么在使用heappush和heappop前应该使用该函数。

    1
    2
    3
    4
    5
    6
    
    In [13]: heap = [5,8,0,3,6,7,9,1,4,2]
      
    In [14]: hq.heapify(heap)
      
    In [15]: heap
    Out[15]: [0, 1, 5, 3, 2, 7, 9, 8, 4, 6]
    
  • heapreplace(heap,n)弹出最小的元素被n替代

    1
    2
    3
    4
    5
    
    In [17]: hq.heapreplace(heap,0.5)
    Out[17]: 0
      
    In [18]: heap
    Out[18]: [0.5, 1, 5, 3, 2, 7, 9, 8, 4, 6]
    
  • nlargest(n,iter)、nsmallest(n,iter)

    heapq中剩下的两个函数nlargest(n.iter)和nsmallest(n.iter)分别用来寻找任何可迭代的对象iter中第n大或者第n小的元素。可以通过使用排序(sorted函数)和分片进行完成。

    1
    2
    3
    4
    5
    6
    
    #返回第一个最大的数
    In [19]: hq.nlargest(1,heap)
    Out[19]: [9]
    #返回第一个最小的数
    In [20]: hq.nsmallest(1,heap)
    Out[20]: [0.5]
    

归并排序

  • 基本原理:归并排序利用了分治的思想来对序列进行排序。对一个长为 n的待排序的序列:
  • 基本步骤
    1. 我们将其分解成两个长度为 $\frac{n}{2}$的子序列。
    2. 每次先递归调用函数使两个子序列有序,
    3. 然后我们再线性合并两个有序的子序列使整个序列有序。

fig4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def merge_sort(self, nums, l, r):
        if l == r:
            return
        mid = (l + r) // 2
        self.merge_sort(nums, l, mid)
        self.merge_sort(nums, mid + 1, r)
        # 两个有序列表的归并
        tmp = []
        i, j = l, mid + 1
        while i <= mid or j <= r:
            if i > mid or (j <= r and nums[j] < nums[i]):  
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1
        nums[l: r + 1] = tmp

    def sortArray(self, nums: List[int]) -> List[int]:
        self.merge_sort(nums, 0, len(nums) - 1)
        return nums

算法解释:定义 mergeSort(nums, l, r) 函数表示对 nums 数组里 [l,r] 的部分进行排序,整个函数流程如下:

  1. 递归调用函数 mergeSort(nums, l, mid) 对 nums 数组里 [l,mid] 部分进行排序。
  2. 递归调用函数 mergeSort(nums, mid + 1, r) 对 nums 数组里 [mid+1,r] 部分进行排序。
  3. 此时 nums 数组里 [l,mid] 和 [mid+1,r] 两个区间已经有序,我们对两个有序区间线性归并即可使 nums 数组里[l,r] 的部分有序。
    1. 线性归并的过程并不难理解,由于两个区间均有序,所以我们维护两个指针 i 和 j 表示当前考虑到 [l,mid] 里的第 i个位置和 [mid+1,r] 的第 j个位置。
    2. 如果 nums[i] <= nums[j] ,那么我们就将nums[i] 放入临时数组 tmp 中并让 i += 1 ,即指针往后移。 否则我们就将 nums[j] 放入临时数组 tmp 中并让 j += 1 。
    3. 如果有一个指针已经移到了区间的末尾,那么就把另一个区间里的数按顺序加入 tmp 数组中即可。
    4. 这样能保证我们每次都是让两个区间中较小的数加入临时数组里,那么整个归并过程结束后 [l,r] 即为有序的。
  4. 函数递归调用的入口为 mergeSort(nums, 0, nums.length - 1),递归结束当且仅当 l >= r

时间复杂度:$O(nlogn)$。由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用,然后再合并两个有序的子序列,而每次合并两个有序的子序列需要 O(n) 的时间复杂度,合并次数为$log(n)$次,所以我们可以列出归并排序运行时间 $T(n)$ 的递归表达式:$T(n)=2T(2/n)+O(n)$。

空间复杂度:$O(n)$。我们需要额外 $O(n)$ 空间的 tmp 数组,且归并排序递归调用的层数最深为nlogn,所以我们还需要额外的 $O(logn)$ 的栈空间,所需的空间复杂度即为$O(n+logn)=O(n)$.

快速排序

  • 基本原理:快速排序算法其实很简单,采用分治策略。使用分治法来把一个串(list)分为两个子串(sub-lists), 其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
  • 算法步骤
    1. 从数列中挑出一个元素,称为 “基准”(pivot);
    2. 分区(partition)操作: 重新排序数列, 比pivot小的放到pivot左边,比pivot大的放到pivot右边。在这个分区退出之后,该基准就处于数列的中间位置。
    3. 递归地(recursive) 把小于基准值元素的子数列和大于基准值元素的子数列排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def partition(nums, left_bound, right_bound):
          	# 随机算法加上这两步
          	# pivot = random.randint(left_bound, right_bound)  
            # nums[pivot], nums[right_bound] = nums[right_bound], nums[pivot]
            pivot = nums[right_bound]
            l,r = left_bound, right_bound - 1
            while l <= r:
                while l <= r and nums[l] <= pivot:
                    l += 1
                while l <= r and nums[r] > pivot:
                    r -= 1
                if l < r:
                    nums[l], nums[r] = nums[r], nums[l]
            # 注意要把轴放在中间, 因为最后一次循环一定是走的l++,即当前l和r指向的是大值,互换l和锚点
            nums[l], nums[right_bound] = nums[right_bound], nums[l]
            return l  
        def quick_sort(nums, left_bound, right_bound):
            if left_bound>=right_bound: 
                return
            mid = partition(nums, left_bound, right_bound)
            quick_sort(nums, left_bound, mid - 1)
            quick_sort(nums, mid + 1, right_bound) # 注意是mid+1

        quick_sort(nums, 0, len(nums)-1)
        return nums

最坏情况:当划分产生的两个子问题分别包含 n-1 和 0 个元素时,最坏情况发生。划分操作的时间复杂度为Θ(𝑛),𝑇(0)=O(1),这时算法运行时间的递归式为 $𝑇(𝑛)=𝑇(𝑛−1)+𝑇(0)+O(𝑛)=𝑇(𝑛−1)+O(𝑛)$,解为$𝑇(𝑛)=O(𝑛^2)T(n)=O(n^2)$。

最好情况:当划分产生的两个子问题分别包含⌊𝑛/2⌋和⌈𝑛/2⌉−1个元素时,最好情况发生。算法运行时间递归式为$𝑇(𝑛)=2𝑇(𝑛/2)+O(𝑛)$,解为$𝑇(𝑛)=O(𝑛lg𝑛)$。

时间复杂度:平均情况下快速排序的时间复杂度是$O(nlogn)$,最坏情况是$O(n^2)$,但通过随机算法可以避免最坏情况

空间复杂度:快排的空间复杂度$O(logn)$。因为快排的实现是递归调用的, 而且每次函数调用中只使用了常数的空间,因此空间复杂度等于递归深度$O(logn)$。