解题常用trick

• 总体：
  • 简单方法想不出来就先想复杂方法，再优化。
  • 用一个small case来设计算法、初步验证算法正确性
• 回溯：
  • 当一个题目，存在各种满足条件的组合，并且需要把它们全部列出来时，就可以考虑backtracking了。 当然，backtracking在一定程度上属于穷举，所以当数据特别大的时候，不合适。而对于那些题目，可能就需要通过动态规划来完成。
• DP：
  • DP由4部分组成
    • 初始值设置
    • 子问题定义：DP数组的意义？
    • 状态转换关系：DP递推式
  • 解决一个DP问题分四步：
    • 由递归回溯解开始思考
    • 用记忆表优化
    • 去掉递归
• 二叉树：
  • 要想到dp方法
  • 要与递归结合起来
  • 平衡二叉树要想到中序遍历
• 图：
  • 要与DFS、BFS结合起来
• 链表：
  • 考虑翻转
• 搜索：
  • 多次二分
• 双指针方法减少时间复杂度
• hash方法减少时间复杂度
• 字符串翻转也常用
• 数组注意越界（边界）情况
• 遇到二进制要想到位运算