算法题常见解题套路总结


很多事情做多了都能总结出一些通用的规律,算法题就有一些套路在里面,特定类型的题目有特定的解法和思路。

先大概总结一下:

  • 直接暴力,如果是没见过的类型,也不涉及复杂度等外的限制,先尝试暴力法解决
  • 从简单情况开始寻找规律
  • 动态规划,动态规划就是寻找最优子结构,并最大化减少递归计算中重复计算子问题的情况。用动态规划时,若一时没有思路,可以先暴力,然后寻找分析暴力中哪些子问题被重复计算了,对于发现的重复计算的问题,用动态规划的方式去消除它。
  • 贪心算法,若一个题具有明显的贪心倾向,可以先用贪心算法试一下
  • 递归,递归在某些问题上会是问题思路更加清晰,也会大大减少某些题的难度,递归问题一般使用迭代也能实现
  • 分治,分治主要是减少问题的规模,分治的主要难点在于合并两个子问题的结果。
  • 位运算,对于一些没有太好思路的题,位运算或许能收获到意想不到的后果。

参考别人总结的规律

  • 如果问最短,最少,BFS(Breadth-first Search )
  • 如果问连通性,静态就是 DFS(Depth-first Search),BFS,动态就 UF
  • 如果问依赖性就 topo sort
  • DAG 的问题就 dfs+memo
  • 矩阵和 Array 通常都是 DP(Dynamic Programming)
  • 问数量的通常都是 DP
  • 问是否可以,也很有可能 DP
  • 求所有解的,基本 backtracking
  • 排序总是可以想一想的
  • 万事总可以想 HashMap
  • 找规律试试 Stack

来自 Leetcode 总结

Copyright © jverson.com 2019 all right reserved,powered by Gitbook 21:32:30

results matching ""

    No results matching ""