labuladong 的算法秘籍-读书笔记-我的刷题心得

一、算法的本质：穷举

数学算法：用数学角度和思维设计算法。

计算机算法：用计算机角度和思维设计算法。

穷举难点

1.1、无遗漏

遗漏，会直接导致答案出错

1.2、无冗余

冗余，会拖慢算法的运行速度

1、如何穷举？即无遗漏地穷举所有可能解。

2、如何聪明地穷举？即避免所有冗余的计算，消耗尽可能少的资源求出答案。

先想出解法，然后在优化

什么算法的难点在「如何穷举」呢？一般是递归类问题，最典型的就是动态规划系列问题。

什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。

主要时间花在想出解法上，由多余的时间采取想如何优化。优化的事情是大佬们干的事情。

二、数组/单链表系列算法

单链表常考的技巧就是双指针

数组常用的技巧有很大一部分还是双指针相关的技巧，说白了是教你如何聪明地进行穷举

3.1、二分搜索技巧

需要数组是有序的

3.2、滑动窗口算法技巧

明确的知道什么时候应该扩大窗口，什么时候该收缩窗口

3.3、回文串相关技巧

3.4、前缀和技巧

前缀和技巧预计算一个 preSum 数组，就可以避免循环

3.5、差分数组技巧

差分数组技巧维护一个 diff 数组，也可以避免循环

三、二叉树系列算法

二叉树模型几乎是所有高级算法的基础

二叉树题目的递归解法可以分两类思路，

第一类是遍历一遍二叉树得出答案：回溯算法核心框架

第二类是通过分解问题计算出答案：动态规划核心框架

子问题的优化一般可以通过创建一个缓存或者说备忘录来缓存之前的数据。提高效率